Power of Two - Algorithm To Round Up To Power of Two

Algorithm To Round Up To Power of Two

Sometimes it is desired to find the least power of two that is not less than a particular integer, n. The pseudocode for an algorithm to compute the next-higher power of two is as follows. If the input is a power of two it is returned unchanged.

n = n - 1; n = n | (n >> 1); n = n | (n >> 2); n = n | (n >> 4); n = n | (n >> 8); n = n | (n >> 16); ... n = n | (n >> (bitspace / 2)); n = n + 1;

Where | is a binary or operator, >> is the binary right-shift operator, and bitspace is the size (in bits) of the integer space represented by n. For most computer architectures, this value is either 8, 16, 32, or 64. This operator works by setting all bits on the right-hand side of the most significant flagged bit to 1, and then incrementing the entire value at the end so it "rolls over" to the nearest power of two. An example of each step of this algorithm for the number 2689 is as follows:

Binary representation	Decimal representation
0101010000001	2,689
0101010000000	2,688
0111111000000	4,032
0111111110000	4,080
0111111111111	4,095
1000000000000	4,096

As demonstrated above, the algorithm yields the correct value of 4,096. The nearest power to 2,689 happens to be 2,048; however, this algorithm is designed only to give the next highest power of two to a given number, not the nearest.