# 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

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

CPU cycles
(full optimization,
lower values are better)

Assembler Output
``` roundUpToNextPowerOfTwo: compiler: VC 2008 in: ecx ← x out: eax → result temp: edx 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