Round up to the next power of two
Each number − except for zero − has at least one bit set to 1. Let's consider only the highest bit which is set to 1:
If it is spread to all bit position on its right side, then we get a number which is just one below the next power of two.
00...001... → 00...001111 → increment by 1: 00...010000
A simple way to distribute this set bit is to create a sequence of right-shifted ORs.
Even better, a divide-and-conquer strategy can be implemented branchless.
Care must be taken when processing a power of 2 as it must map to itself.
By default, the algorithm would give the next power of 2, however, a simple decrement by 1 (line 3) neatly solves this problem.
• designed for 32 bits
• x must be positive and ≤ 231, else results are undefined
help me to pay
my server bills
• constant time, data independent
+ Intel® Pentium™ D:
• roundUpToNextPowerOfTwo: ≈ 13.5 cycles per number
+ Intel® Core™ 2:
• roundUpToNextPowerOfTwo: ≈ 15 cycles per number
+ Intel® Core™ i7:
• roundUpToNextPowerOfTwo: ≈ 14 cycles per number
lower values are better)
|Download||The full source code including a test program is available for download.|
|More Twiddled Bits||
... or go to the index