Nearest power of two greater than or equal to the given number

This question isn't an FAQ, but we are placing this here just because we think this is a very interesting code to explore and learn about bit-wise operators. The code is taken from from Bit Twiddling Hacks∞.

Looks intimidating. How does this work? Well the program actually employs a very simple logic. It just sets all the bits starting from the Most Significant Bit that is 1. After having done this it adds 1 to the number which would give you the nearest power of 2.

A few simple illustrations would clear the picture.

Let us suppose that the given number has a bit pattern 00010100 (20). The MSB that is 1 is the 4th bit starting from the beginning. The first 6 lines of code in the function getNearestPowerOf2 set all the bits starting from 4th bit till the 8th bit including those two bits to 1. So the bit pattern of num after these 6 lines have been executed would be 00011111(31). Now the last line num++ just increases this value by 1 which would give you the bit pattern 00100000(32) which is indeed the nearest power of 2 greater than 20.

Suppose the given bit pattern were 01011001 (89), then the bit pattern after the first 6 lines have been executed would be 01111111(127). Now in the last line when you add 1 to this number you would get 128 which is indeed the expected answer.

Now how does those 6 lines of code work? It would be very simple to understand if you take any random number and work out the bit pattern after each and every step. Trying out the program with 2 or 3 numbers would give you a clear picture. Good luck!!!