Round up to the next power of two

Code
01: unsigned int roundUpToNextPowerOfTwo(unsigned int x)
02: {
03:   x--;
04:   x |= x >> 1;  // handle  2 bit numbers
05:   x |= x >> 2;  // handle  4 bit numbers
06:   x |= x >> 4;  // handle  8 bit numbers
07:   x |= x >> 8;  // handle 16 bit numbers
08:   x |= x >> 16; // handle 32 bit numbers
09:   x++;
10:
11:   return x;
12: }
 bits.stephan-brumme.com

Explanation 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.

Restrictions • designed for 32 bits
• x must be positive and ≤ 231, else results are undefined

These ads
help me to pay
my server bills

Performance • 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
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
roundUpToNextPowerOfTwo:
01:   ; x--
02:   dec ecx
03:   ; x |= x >> 1
04:   mov eax, ecx
05:   shr eax, 1
06:   or  ecx, eax
07:   ; x |= x >> 2
08:   mov edx, ecx
09:   shr edx, 2
10:   or  ecx, edx
11:   ; x |= x >> 4
12:   mov eax, ecx
13:   shr eax, 4
14:   or  ecx, eax
15:   ; x |= x >> 8
16:   mov edx, ecx
17:   shr edx, 8
18:   or  ecx, edx
19:   ; x |= x >> 16
20:   mov eax, ecx
21:   shr eax, 16
22:   or  eax, ecx
23:   ; x++
24:   inc eax
 bits.stephan-brumme.com

Download The full source code including a test program is available for download.

References http://graphics.stanford.edu/~seander/bithacks.html

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index