直接（不迭代地）最大化 (1 << n) 服从 (a & ~((1 << n) - 1)) >= b

Question

我试图找到满足这个不等式的最大1 << n（所有变量都是正整数）：

a & ~((1 << n) - 1) >= b

迭代解决这个问题很简单（是的，我知道你可以通过分而治之等方法获得更好的性能），但这不是我的问题。

我想知道是否有办法直接解决这个问题，比如通过某种位运算？

注1：假设你可以在一次操作中做到"round up/down to the closest power of 2"。
注2：如有必要，您可以假定二进制补码表示（但我怀疑这是否有帮助）。

如果有直接的方法，我可以使用什么技术来解决这个问题？如果没有，我能告诉你吗？

我已经尝试了很多东西，比如 XORing a 和 b，将结果四舍五入到 2 的下一个幂等，但我最终没有找到任何好的东西总是有效。

Answer 1

if (a < b) {
    oops();
} else if (a == b) {
    return ctz(a);
} else {
    // most significant mismatching bit - must be set to 1 in a and 0 in b
    int msmb = round_down_to_power_of_2(a ^ b);
    if (b & (msmb - 1)) {
        return ctz(msmb);
    } else {
        return ctz(b);
    }
}

我们有 4 个案例：

如果 a < b，则 n 的值无效。
如果 a == b，我们可以清除每一位，直到 a 的最低有效设置位。
如果 a > b 并且 b 设置了低于 a 和 b 之间最重要不匹配位的位，我们可以清除直到最重要不匹配位的所有位。
如果 a > b 并且 b 在 a 和 b 之间的最高有效不匹配位之下没有设置位，我们可以清除所有位，直到 b 的最低有效设置位。

直接（不迭代地）最大化 (1 << n) 服从 (a & ~((1 << n) - 1)) >= b

Directly (NOT iteratively) maximizing (1 << n) subject to (a & ~((1 << n) - 1)) >= b

c

binary

boolean-logic

bit-manipulation

maximize