试图找到满足n+x=n^x的x的数目，但由于超时而失败

Question

• 0<=x<=n
• n+x=n^x

其中^表示按位异或运算符。然后打印一个整数，表示满足上述条件的x的总数。

制约因素

null

null

示例输入：10

示例输出：4

说明：对于n=10，x值0、1、4和5满足以下条件：

null

public class SumVsXor 
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long count = LongStream.rangeClosed(0, n)
                               .filter(k -> k + n == (k ^ n))
                               .count();
        System.out.println(count);  
    }
}

Answer 1

您的代码的问题是效率很低。对于n==1000000000000000的情况，流管道执行1,000,000,000,000,000加法和异或操作，这需要很长时间。测试0到n之间的每个数字是否n+x==n^x将花费很长时间，即使您使用for循环而不是streams。

与其检查0到n之间的所有数字，不如尝试找出一种更好的方法来计算所需的x的总数。这个问题出现在“位操作”一节中，这应该会给您一个提示，让您了解满足
n+x==n^x的数字位。

让我们考虑n==1000000000000000的情况。这个大数字的二进制表示形式是

0000000000000011100011010111111010100100110001101000000000000000
              ===   == = ====== = =  =  ==   == =
                 ---  - -      - - -- --  ---  - ---------------
~~~~~~~~~~~~~~              

long n = 1000000000000000L;
int zeroBitsCount = 0;
while (n > 0) {
    if (n % 2 == 0) {
        zeroBitsCount++; // counts the number of non-leading 0 bits
    }
    n = n >> 1; // divide n by 2 in order to examine the next bit in the next iteration
}
long total = 1L << zeroBitsCount; // the total is 2^(the 0 bits count)