java - 试图找到满足 n + x = n ^ x 的 x 的数量因超时而失败

Question

我正在尝试从 Hacker Rank site 的 位操作 部分解决以下问题使用 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 循环而不是 Stream 也会花费很长时间秒。

您应该尝试找出一种更好的方法来计算所需的 x 总数，而不是检查 0 和 n 之间的所有数字。这个问题出现在“位操作”部分的事实应该给你一个提示查看满足
n + x == n ^ x的数字位.

让我们考虑 n==1000000000000000 的情况.该大数的二进制表示是

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

为了 n + x等于n ^ x , x必须有 0与 1 对应的所有位中的值n 的位(上面标有 =)，以及 0或 1与 0 对应的位中的值n 的位(上面标有 -)。这不包括前导 0 s(上面标有 ~)，因为 x 必须 <= n , 所以任何前导 0在 n还必须有 0 x 中的值.

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

在 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)