java - 舒适性:舒适

在进行检查时，这是任务之一(我无法解决):

如果将两个数字都转换为二进制数时，B中所有数字为1的位置必须在A中的相同位置中另外一个1，则他们说数字A为另一个数字B感到“舒适”。

例:

B = 101
A = 111

在这种情况下，数字A“安慰”到B

B = 101
A = 011

不满足舒适条件。

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

预期的最坏情况时间复杂度为O(对数(A)+对数(B)+对数(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

{
公共无效测试(int A，int B，int C)
{
long timeStart，timeEnd；
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毫秒

最佳答案

以@alain的答案为基础，comf(A) = 2^(number of zero bits in 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^(number of zero bits in A|B)，因为当且仅当数字X在A或B都具有1的所有位中都具有1时，才使A和B都舒适。

同样，comf(A and B and C) = 2^(number of zero bits in A|B|C)。

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