Explanation for computing the nearest power of two

2019-07-23 08:25发布

问题:

This is a well-known function to compute the next nearest power of two for positive arguments. However I don't have much experience in bit twiddling to grok the logic/theory behind it. Would you kindly explain why and how that works? Particularly, the choice of 1,2,4,8,16 for shifting and if the range of the argument was greater what would be used, for example, for a long? Why logical shift instead of arithmetic and finally, what does ORing shifted arg accomplish?

static int lowestPowerOfTwoGreaterThan(int arg) {
    arg |= (arg >>>  1);
    arg |= (arg >>>  2);
    arg |= (arg >>>  4);
    arg |= (arg >>>  8);
    arg |= (arg >>> 16);
    return ++arg;
}

回答1:

It's really simple if you track the changes to the value. A power of two has only one set bit e.g 100, 10000000, 10000000000, which means that a power of two, minus one, is a sequence of ones, e.g. 10000 - 1 = 1111. So what the function does is change any number to a sequence of ones (without moving its highest 1 bit) and then add one, e.g. it changes 10000001000111001 (66105) to 11111111111111111 (131071) and adds one to make 100000000000000000 (131072).

First, it ORs the value by itself shifted 1 bit to the right. This has the effect of lengthening all runs of 1 in the value.

   10000001000111001
OR 01000000100011100
   =================
   11000001100111101

You now notice that each run of zeroes is preceded by at least two ones, so instead of shifting by one again, we can speed up the process by shifting by two bits instead of one.

   11000001100111101
OR 00110000011001111
   =================
   11110001111111111

Now, each run of zeroes is preceded by at least four ones, so we shift by four this time, and OR the values again.

   11110001111111111
OR 00001111000111111
   =================
   11111111111111111

Repeating this logic, the next shift distance will be 8, then 16 (stop here for 32-bit values), then 32 (stop here for 64-bit values). For this example, the result remains unchanged for further shifts since it is already a sequence of ones.

This method changes any binary number to a sequence of ones. Adding 1 to this, as stated before, produces the next greatest power of two.