试图找到满足 n + x = n ^ x 的 x 的数量失败并超时

Question

我正在尝试使用 Java 8 的新功能（例如 Streams.

问题描述：

Given an integer, n, find each x such that:

0 <= x <= n

n + x = n ^ x

where ^ denotes the bitwise XOR operator. Then print an integer denoting the total number of x's satisfying the criteria above.

Constraints

0 <= n <= 10¹⁵

Sample Input: 5

Sample Output: 2

Explanation:

For n = 5, the x values 0 and 2 satisfy the conditions:

5 + 0 = 5 ^ 0 = 5

5 + 2 = 5 ^ 2 = 7

Thus, we print 2 as our answer.

Sample Input: 10

Sample Output: 4

Explanation: For n = 10, the x values 0, 1, 4, and 5 satisfy the conditions:

10 + 0 = 10 ^ 0 = 10

10 + 1 = 10 ^ 1 = 11

10 + 4 = 10 ^ 4 = 14

10 + 5 = 10 ^ 5 = 15

Thus, we print 4 as our answer.

我的代码如下：

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);  
    }
}

问题是这段代码没有通过所有测试用例。

它适用于 n 的小值，但对于 1000000000000000 这样的大值，它会因超时而失败。

我想知道 LongStream 是否无法处理具有那么多元素的 Stream。

Answer 1

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

与其检查 0 到 n 之间的所有数字，不如尝试找出一种更好的方法来计算所需的 x 总数。这个问题出现在 "Bit Manipulation" 部分下的事实应该给你一个提示查看满足
n + x == n ^ x.

的数字位

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

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

为了使n + x等于n ^ x，x必须在与1位对应的所有位中具有0值n 的（上面用 = 标记），以及与 n 的 0 位相对应的位中的 0 或 1 值（上面标有 -）。这不包括前导 0s（上面标记为 ~），因为 x 必须 <= n，因此 [=24= 中的任何前导 0s ] 还必须在 x 中有一个 0 值。

这意味着n + x == n ^ x的x的总数是
2^{n中0的个数，不包括前导 0s}.

在n = 1000000000000000的情况下，有30个这样的0位，所以满足要求的x的总数是2³⁰.

这是计算 x 总数的一种方法：

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)

Answer 2

public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    long n = in.nextLong();
    long count = 1L << (64-Long.bitCount(n)-Long.numberOfLeadingZeros(n));
    System.out.println(count);
}

Answer 3

如果你对 XOR 了解不多，这道题很简单。我对java了解不多。但我可以在 python.

中解释

1.First 将数字转换为二进制。 2.Count 该二进制数中零的个数。 3.print 2 ^（零的数量）就是这样。

这是我的 python 代码。

n = int(input())
sum = 0
if n!=0:
    n=str(bin(n))
    for i in range(len(n)):
            if n[i]=='0':
           sum = sum + 1
    print(2**(sum-1))
else: print(1)

将总和减1的原因是，在python中它将数字转换为二进制格式。例如：0b'10101。

Answer 4

我得到了同样的结果，但是通过不同的解释，所以我想我可以 post 在这里。

Eran 的回答得出了与我相同的结论：修改初始数字的二进制表示中的零 - 这非常简单。

假设我们的号码是

101010100

所以它有 5 个零。

您需要所有可能的组合：

一个零
两个零
三个零
四个零
五个零

实际上是：

 comb(1,5) + comb(2,5) + comb(3,5) + comb(4,5) + comb (5,5)

这是一个众所周知的公式，等于：

pow(2,n) // where n is five in our case

从那里解决方案很明显...

试图找到满足 n + x = n ^ x 的 x 的数量失败并超时

Trying to find the number of x's that satisfies n + x = n ^ x fails with timeout

java

algorithm

bit-manipulation

xor

java-stream