Nicolas Malebranche's questions

给定一个无符号的 64 位整数y，有没有一种有效的方法来找到所有无符号的 64 位整数，x使得 (x & (x + y)) == 0？

以下是一些小例子y：

• y=0：唯一可能的解决方案x=0
• y=1x=(1<<n)-1：对于某些 n>=0，所有解都具有以下形式
• y=2x=(1<<n)-2：对于某些 n>=1，所有解都属于以下形式
• y=3：要么x=(1<<n)-3，n>=2，要么x=(1<<n)-2，n>=1

一般来说，要考虑的案例数量取决于的位表示中 1 和 0 的运行次数y。

问题的解决方案可能是使用迭代器函数，找到下一个有效的x，如下所示：

uint64 next(uint64 x, uint64 y) {
    x++;
    while (x & (x+y)) x++;
    return x;
}

由于标准(x & (x + y)) == 0相当简单，这可能是一个已知问题，有比上述更有效的解决方案。