主页 / coding / 问题 / 79313695
Accepted
Nicolas Malebranche
Asked: 2024-12-28 19:38:10 +0800 CST

查找所有满足 (x & (x+y)) == 0 的 x

  • 772

给定一个无符号的 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相当简单，这可能是一个已知问题，有比上述更有效的解决方案。

algorithm

1 个回答

  1. Best Answer

    对于任何给定的y，如果x是解，则 的每个后缀x，包括0，也是解。

    如果将 64 位整数排列成一棵树，使得每个节点的父节点都是通过关闭最高 1 位形成的后缀，则解决方案将对应于以 0 为根的子树，您可以通过遍历这棵树来枚举它们。

    从根开始，如果我们有一个解决方案x，那么我们需要找到可以设置的新的最高位，这些位也会产生有效的解决方案。这些恰好是大于的1位。这些可以有效地枚举，从而得到一个有效的递归解决方案。x+yx

    这是 Python 中的实现。如果你愿意，可以将其变成迭代器：

    def printSolutions(y, prevx=0, mask=0):
    print(prevx)
    bits = (prevx+y) & ~mask & ((1<<64)-1)
    while bits > 0:
        bit = bits & -bits
        bits -= bit
        x = prevx | bit
        printSolutions(y, x, bit | (bit-1))
    • 6

相关问题