A smattering of bitwisdom

I remember my epiphany about bit-twiddling. It was one small insight - the fact that 1 in binary is the equivalent of both 1 and 9 in decimal, but more often than not (to speak very facetiously) the latter. So 1111 is like 9999 in the sense that adding 1 to either will result in 10000, in the respective bases. Of course, binary 1 is equivalent to decimal 1 as well, because you add 1 to 9999 (or 1111) and get 10000. Also, subtracting 1 from 10000 has the predictably opposite effect of producing 1111 or 9999 as the base may be (pun intended).

Turning off bits and counting bits

This has several interesting consequences that are often used in bit-wise computations. For one, if the lowest n bits of x are 0, then x-1 would turn them into 1, and the n+1th bit, i.e. the lowest significant bit, to 0. What this in turn would mean is that x & (x-1) would simply turn off the lowest significant bit. We could use this successively on a number to turn off each of its significant bits, and count how many it takes till the number is reduced to zero - basically giving us a quick way to count set bits in a number.

Setting bits and bit ranges

Again, x+1 also does some stuff. Just as x-1 unsets the least significant bit, x+1 sets the lowest zero bit (and unsets all lower bits). So if the lowest n bits of x are set, and n+1th bit is 0, then x+1 unsets all these n bits, and sets the n+1th bit. This means repeated application of x |= (x+1) would set all its bits. But when does one stop? At some point all the bits of x up to its most significant bit are set. At this point, if we perform x & (x+1), we would get 0. So that should be the condition to check at each iteration.

The point of this post ... a leetcode medium problem

So far, I have repeated what is common knowledge. What's the point of this post then? I came across this leetcode problem - how to compute the bitwise-and of a continuous range of integers - could be the entire range of 32 bit positive signed integers.

I liked this problem because it didn't immediately fit a pattern, and I had to think about it. Now, it's useful to remember here that the nth power of two has a binary representation of 1 followed by n 0s. That means if we bitwise-and a range of numbers, the smallest of which is less than 2^n and the largest of which is greater than 2^n, then 2^n will occur in that range and nullify all the numbers resulting in 0 (think why). So only a range that lies entirely between two successive powers of 2 could yield a non-zero bitwise-and. At this point it's relatively straightforward to figure out the rest. Here is the logic:

If the range is [a, b], find the maximum power of 2 in the a and in b. If they aren't equal, the result would be 0, so return. Else, assuming that power is 2^n, set the n+1th bit in the result. Then repeat the process for a-2^n and b-2^n.