XOR编程拼图建议

Question

给定long int x,计算满足以下条件的a的值的数量:

一个 XOR X > X
0 < 一 < X

其中a和x是长整数,XOR是按位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

IDEOne 代码链接

尝试解释逻辑（使用示例 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。

在你的值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，是答案）