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

Question

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

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

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

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

注意 1:假设您可以在一次操作中执行“向上/向下舍入到最接近 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 个案例:

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