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.
Read more about this topic: Power Of Two
Famous quotes containing the word power:
“A physicians physiology has much the same relation to his power of healing as a clerics divinity has to his power of influencing conduct.”
—Samuel Butler (18351902)