java - 编码性 : Condition in comfort

Question

在进行考试时，这是其中一项任务(我无法解决):

他们说数字 A 比另一个数字 B 更“舒服”，如果当你将两个数字都转换为二进制时，B 中所有数字 1 的位置必须是 A 中相同位置的另一个 1。

例子:

B = 101A = 111

在这种情况下，数字A“安慰”了B，然而

B = 101A = 011

不满足舒适条件。

他们给了我 3 个 30 位 A、B 和 C 的无符号数，介于 0 和 2^30 之间。我必须确定该范围内至少满足其中一个数字“舒适”条件的数字数量.

预期的最坏情况时间复杂度为O(log(A)+log(B)+log(C))；

我使用了以下代码，它花费的时间太长，主要是因为它检查二进制数作为数组并比较每个单元格。我假设必须有一些方法可以让它更快(一些数学运算或 idk :-( )。

public class Main {
public static void main(String[] args) 
{
    sol(905,5000,11111111); //I used any numbers
}

public static void sol(int A, int B, int C)
{

    int min=Math.min(A, Math.min(B, C)); 
    int max=(int) Math.pow(2, 30);

    String binA=Integer.toBinaryString(A); binA=fillBin(binA);
    String binB=Integer.toBinaryString(B); binB=fillBin(binB);
    String binC=Integer.toBinaryString(C); binC=fillBin(binC);

    String binMax=Integer.toBinaryString(max);

    int conta=0;

    for(int i=min;i<=max;i++)
    {
        String binT = Integer.toBinaryString(i);binT=fillBin(binT);

        boolean failA=false;
        boolean failB=false;
        boolean failC=false;

        for(int j=0;j<binT.length();j++)
        {
            if((binA.length()<j)&&(binB.length()<j)&&(binC.length()<j))
            {
                break;
            }

            if((!failA)||(!failB)||(!failC))
            {
                if((binA.length()<j)&&(binA.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failA=true;
                }
                if((binB.length()<j)&&(binB.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failB=true;
                }
                if((binC.length()<j)&&(binC.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failC=true;
                }
            }
            else
            {
                break;

            }
        }

        if((!failA)||(!failB)||(!failC))
        {
            conta++;
        }
    }

}

private static String fillBin(String binA) 
{
    String S=binA;
    for(int i=0;i<(31-binA.length());i++)
    {
        S="0"+S;
    }       
    return S;
}

如果你们中的任何人之前已经完成了这项任务并且发现有一些缺失的数据，请告诉我，请原谅我的英语(不是我的母语)。

非常感谢

编辑:这是在@Eran 的帮助下编写的代码:

public class BinaryTask 

{ 公共(public)无效测试(int A，int B，int C) { 长时间开始，时间结束； timeStart = System.currentTimeMillis();

    //Bunch of variables
    String binaryA = Integer.toBinaryString(A); int zerosA=0;
    String binaryB = Integer.toBinaryString(B); int zerosB=0;
    String binaryC = Integer.toBinaryString(C); int zerosC=0;

    String binaryAB =""; int zerosAB=0;
    String binaryBC =""; int zerosBC=0;
    String binaryAC =""; int zerosAC=0;

    String binaryABC=""; int zerosABC=0;

    //The long for the for
    int Max = Math.max(binaryA.length(), Math.max(binaryB.length(), binaryC.length()));

    //Creating: A|B, B|C, A|B and A|B|C that meet the confort condition
    for(int i=0;i<Max;i++)
    {
        //Creating A|B
        if((binaryA.length()>i)&&(binaryB.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryB.charAt(i)=='1'))
            {
                binaryAB="1"+binaryAB;
            }
            else //I also count this zero so i dont have the do another for later
            {
                binaryAB="0"+binaryAB; zerosAB++;
            }
        }
        //Creating B|C
        if((binaryB.length()>i)&&(binaryC.length()>i))
        {
            if((binaryB.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryBC="1"+binaryBC;
            }else{binaryBC="0"+binaryBC; zerosBC++;}
        }
        //Creating A|C
        if((binaryA.length()>i)&&(binaryC.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryAC="1"+binaryAC;
            }else{binaryAC="0"+binaryAC;zerosAC++;}
        }
        //Creating A|B|C
        if((binaryA.length()>i)&&(binaryB.length()>i)&&(binaryC.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryB.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryABC="1"+binaryABC;
            }else{binaryABC="0"+binaryABC; zerosABC++;}
        }
    }

    //Counting the other amount of zeros
    zerosA = countZeros(binaryA);
    zerosB = countZeros(binaryB);
    zerosC = countZeros(binaryC);

    long confortA = (long) Math.pow(2, zerosA);
    long confortB = (long) Math.pow(2, zerosB);
    long confortC = (long) Math.pow(2, zerosC);
    long confortAB = (long) Math.pow(2, zerosAB);
    long confortBC = (long) Math.pow(2, zerosBC);
    long confortAC = (long) Math.pow(2, zerosAC);
    long confortABC = (long) Math.pow(2, zerosABC);

    long totalConfort = confortA + confortB + confortC - confortAB - confortBC - confortAC + confortABC;
    timeEnd = System.currentTimeMillis();

    System.out.println("Total of confort for A "+A+" B "+B+" C "+C+" is " +totalConfort);
    System.out.println("the task has taken "+ ( timeEnd - timeStart ) +" milliseconds");    
}

private int countZeros(String binary) 
{
    int count=0;
    for(int i=0;i<binary.length();i++)
    {
        if(binary.charAt(i)=='0')
        {count++;}
    }
    return count;
}

为了进行测试，我这样做了:

    public static void main(String[] args) 
{
    BinaryTask T = new BinaryTask();

    int A = (int) Math.pow(2, 10);
    int B = (int) Math.pow(2, 15);
    int C = (int) Math.pow(2, 30);
    T.test(A, B, C);
}

这是输出:

A 1024 B 32768 C 1073741824 的总舒适度是 1073739776任务耗时 1 毫秒

Answer 1

基于@alain 的回答，comf(A) = 2^(A 中零位的数量) 是 A 的安慰数字的数量。

您需要 A、B 或 C 的安慰数字的数量。

这是 comf(A)+comf(B)+comf(C)-comf(A and B)-comf(B and C)-comf(A and C)+comf(A and B and C )。

其中 comf(A and B) 表示 A 和 B 的安慰数字的数量。comf(A and B and C) 表示所有 A、B 和 C 的安慰数的数量。

我们知道如何计算comf(A)、comf(B) 和comf(C)。

comf(A and B) = 2^(A|B 中零位的数量)，因为当且仅当数字 X 在所有位中都为 1 时，它才能同时满足 A 和 B A 或 B 都有。

类似地，comf(A and B and C) = 2^(A|B|C 中的零位数)。

由于所有的计算都是对A、B和C的位运算，所以运行时间就是的位长度A、B 和 C，即 O (log (A) + log (B) + log (C)) .