异或编程难题建议

Question

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

a XOR x > x
0 < a < 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.

在你的值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一样，就是答案)

Answer 2

一种看待这个问题的方法是考虑 x 中的每一位。

如果是 1，则翻转它会得到一个较小的数字。
如果它是 0，那么将它翻转会产生一个更大的数字，我们应该计算它 - 以及右边的所有位组合。这很方便地加起来就是掩码值。

long f(long const x)
{
    // only positive x can have non-zero result
    if (x <= 0) return 0;

    long count = 0;

    // Iterate from LSB to MSB
    for (long mask = 1;  mask < x;  mask <<= 1)
        count += x & mask
            ? 0
            : mask;

    return count;
}

我们可能怀疑这里有一个模式 - 看起来我们只是在复制 x 并翻转它的位。

让我们用一个最小的测试程序来确认一下：

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv)
        std::cout << *argv << " -> " << f(std::atol(*argv)) << std::endl;
}

0 -> 0
1 -> 0
2 -> 1
3 -> 0
4 -> 3
5 -> 2
6 -> 1
7 -> 0
8 -> 7
9 -> 6
10 -> 5
11 -> 4
12 -> 3
13 -> 2
14 -> 1
15 -> 0

所以我们所要做的就是 'smear' 设置最高有效位 1 之后的所有零位的值，然后与之异或：

long f(long const x)
{
    if (x <= 0) return 0;
    long mask = x;
    while (mask & (mask+1))
        mask |= mask+1;
    return mask ^ x;
}

这要快得多，而且仍然是 O(log n)。

异或编程难题建议

XOR programming puzzle advice

c++

xor

bits