尝试查找满足 n + x = n ^ x 的 x 数失败，并超时

algorithm java xor bit-manipulation java-stream

2022-09-02 01:35:07

我正在尝试使用Java 8的新功能（例如s）从Hacker Rank站点的Bit Manipulation部分解决以下问题。Stream

问题描述：

给定一个整数 n，找到每个 x，使得：

0 <= x <= n

n + x = n ^ x

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

约束

0 <= n <= 10¹⁵

样品输入： 5

示例输出：2

解释：

对于 n = 5，x 值 0 和 2 满足以下条件：

5 + 0 = 5 ^ 0 = 5

5 + 2 = 5 ^ 2 = 7

因此，我们打印 2 作为我们的答案。

样品输入：10

示例输出：4

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

10 + 0 = 10 ^ 0 = 10

10 + 1 = 10 ^ 1 = 11

10 + 4 = 10 ^ 4 = 14

10 + 5 = 10 ^ 5 = 15

因此，我们打印4作为我们的答案。

我的代码如下：

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

问题是此代码未通过所有测试用例。

它适用于的小值，但适用于较大的值，例如由于超时而失败。n1000000000000000

我想知道是否无法处理这么多元素的s。LongStreamStream

答案 1

代码的问题在于它的效率非常低下。对于的情况，您的管道正在执行加法和 XOR 运算，这需要很长时间。测试 0 到 n 之间的每个数字是否需要很长时间，即使使用 for 循环而不是 s。n==1000000000000000Stream1,000,000,000,000,000n + x == n ^ xStream

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

让我们考虑一下 .该大数的二进制表示形式为n==1000000000000000

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

为了等于，必须在所有位中具有与位对应的值（用上面标记），并且在位中具有与位相对应的值（用上面标记）。这不包括前导 s（用上面标记），因为 x 必须是 <= ，因此中的任何前导 s 也必须在中具有值。n + xn ^ xx01n=010n-0~n0n0x

这意味着 x 的总数为 2 是
^{n 中 0的数目，不包括前导 0秒}。n + x == n ^ x

在的情况下，有这样的位，所以满足要求的总数是 2³⁰。n = 1000000000000000300x

以下是计算的总数的一种方法：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)

答案 2

我得出了相同的结果，但通过不同的解释，所以我想我可能会在这里发布它。

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

假设我们的数字是

101010100

所以它有5个零。

您需要以下所有可能的组合：

单个零
两个零
三个零
四个零
五个零

这实际上是：

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

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

pow（2，n） // 其中 n 在我们的例子中是五

从那里开始，解决方案是显而易见的...