Using bit manipulation to calculate the mean value of two number?

Question

I find this code :

int mid = (l & r) + ((l ^ r) >> 1)

which is the same as mid=(l+r)/2

but i can't figure why?

Any help? Thanks!

Answer 1

It's not quite the same, the point of it is not being the same. It is mostly the same, but without overflow trouble: if you input two positive numbers, the result will never be negative. That is not true of mid = (l + r) / 2, if you have for example l = 0x7fffffff, r = 1 then the true midpoint is 0x40000000 but the naive midpoint calculation says it is 0xc0000000, a large negative number.

Addition can be decomposed into:

x + y = (x ^ y) + ((x & y) << 1)

That's just a simple "calculate per-digit sum, then apply the carries separately" decomposition. Then shift the whole thing right by 1 while restoring the bits that "fell off the end" by just not shifting left to begin with and shifting the other thing to the right,

x + y = ((x ^ y) >> 1) + (x & y)

Which is that midpoint calculation. Note that it rounds down, not towards zero, which matters for negative results. I would not call the result wrong, it's still halfway in between the endpoints, but it does not match the result from a normal signed division by 2 (usually rounds towards zero, though opinions about how it should round differ).

You can change it to work for all unsigned integers by using an unsigned right shift:

// unsigned midpoint without wrapping/overflow
int mid = (l & r) + ((l ^ r) >>> 1);

Of course being the unsigned midpoint, negative inputs are implicitly treated as very large positive numbers, that's the point.

If you're working with signed-but-non-negative numbers (as is usually the case for midpoint calculation), you can use the significantly simpler

int mid = (x + y) >>> 1