c++ - 异或编程难题建议

Question

给定一个 long int x，计算 a 满足以下条件的值的个数:

a XOR x> x
0 <一个 <x

其中 a 和 x 是长整数，XOR 是按位异或运算符

你会如何完成这个问题？

我还应该提到输入 x 可以大到 10^10

我已经设法通过迭代 0 到 x 检查条件并增加计数值来获得蛮力解决方案。但这不是最佳解决方案......

这是我试过的蛮力。它有效，但对于大的 x 值非常慢。

 for(int i =0; i < x; i++)
 {
      if((0 < i && i < x) && (i ^ x) > x)
          count++;    
 }

Answer 1

long long NumberOfA(long long x)
{
    long long t = x <<1;
    while(t^(t&-t)) t ^= (t&-t);
    return t-++x;
}


long long x = 10000000000;
printf("%lld ==> %lld\n", 10LL, NumberOfA(10LL) ); 
printf("%lld ==> %lld\n", x, NumberOfA(x) ); 

输出

10 ==> 5
10000000000 ==> 7179869183

Link to IDEOne Code

---

尝试解释逻辑(使用示例 10，或 1010b)

• 将 x 向左移动 1。(值 20 或 10100b)
• 关闭所有低位，只留下高位(值 16 或 10000b)
• 减去 x+1 ( 16 - 11 == 5 )

---

试图解释
(虽然不容易)

你的规则是a ^ x必须大于 x , 但你不能向 a 添加额外的位或 x .
(如果以4位值开头，则只能使用4位)

N 位数字的最大可能值为 2^n -1 .
(例如 4 位数，2^4-1 == 15)
我们称这个号码为 B。

在你的值(value)之间x和B(含)，则有B- x可能的值。
(回到我的示例，10。在 15 到 10 之间，有 5 个可能的值:11、12、13、14、15)

在我的代码中，t是x << 1 ，然后关闭所有低位。
( 10 << 1 是 20 ; 关闭所有低位得到 16 )

然后 16 - 1是 B，B - x 是您的答案:
( t - 1 - x, 与 t - ++x 相同，是答案)