给定无符号64位整数y，如何高效找出满足(x & (x+y))==0的所有x？

给定无符号64位整数y，是否存在高效方法找出所有满足(x & (x + y)) == 0的无符号64位整数x？

小数值y的示例 #

• y=0：唯一解为x=0
• y=1：所有解形如x=(1<<n)-1，其中n≥0
• y=2：所有解形如x=(1<<n)-2，其中n≥1
• y=3：解为x=(1<<n)-3（n≥2）或x=(1<<n)-2（n≥1）

核心观察 #

通常需要考虑的情况数取决于y二进制表示中连续1和连续0的段数。

一种基础迭代解法 #

目前有一个用于找出下一个有效x的迭代函数示例：

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

由于判断条件(x & (x + y)) == 0本身较为简单，这可能是一个存在更高效解法的已知问题。

内容的提问来源于stack exchange，提问作者Nicolas Malebranche