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

Question

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

问题描述:

给定一个整数n,找到每个x,使得:

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

其中^表示按位XOR运算符.然后打印一个整数,表示满足上述条件的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);  
    }
}

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

它适用于较小的值n,但对于较大的值,例如1000000000000000由于超时而失败.

我想知道是否LongStream无法处理Stream那么多元素.

Answer 1

您的代码存在的问题是效率非常低.对于这种情况n==1000000000000000,您的Stream管道正在执行1,000,000,000,000,000添加和XOR操作,这需要很长时间.测试0到n之间的每个数字是否n + x == n ^ x需要很长时间,即使使用for循环而不是Streams.

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

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

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

为了n + x为等于n ^ x,x必须有0在所有的位与对应的值1的位n(标有=以上),并且或者0或1与相应的位值0的位n(标有-上文).这不包括前导0s(用~上面标记),因为x必须是<= n,所以任何前导0s n必须也有一个0值x.

这意味着x的总数n + x == n ^ x是
2 ^{的0s 数n,不包括前导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)