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

Question

I'm trying to find the largest 1 << n that satisfies this inequality (all variables are positive integers):

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

Solving this iteratively is trivial (and yes, I know you can get better performance through divide-and-conquer and the like), but that's not my question.

I'm wondering if there is a way this could be solved directly, like through bit-twiddling of some sort?

Note 1: Assume you can do "round up/down to the closest power of 2" in one operation.
Note 2: If necessary, you can assume a two's complement representation (but I doubt this helps).

What technique can I use to solve this, if there is a direct way? If there isn't, can I tell somehow?

I've tried lots of things like XORing a and b, rounding the result up to the next power of 2, etc. but I didn't end up finding anything nice that always works.

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);
    }
}

We have 4 cases:

1. If a < b, no value of n works.
2. If a == b, we can clear every bit up to the least significant set bit of a.
3. If a > b and b has set bits below the most significant mismatching bit between a and b, we can clear every bit up to the most significant mismatching bit.
4. If a > b and b has no set bits below the most significant mismatching bit between a and b, we can clear every bit up to the least significant set bit of b.