Given an integer, how do I find the next largest power of two using bit-twiddling?

by

For 32-bit integers, this is a simple and straightforward route:

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

Here’s a more concrete example. Let’s take the number 221, which is 11011101 in binary:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2;   // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4;   // ...
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

There’s one bit in the ninth position, which represents 2^8, or 256, which is indeed the next largest power of 2. Each of the shifts overlaps all of the existing 1 bits in the number with some of the previously untouched zeroes, eventually producing a number of 1 bits equal to the number of bits in the original number. Adding one to that value produces a new power of 2.

Another example; we’ll use 131, which is 10000011 in binary:

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

And indeed, 256 is the next highest power of 2 from 131.

If the number of bits used to represent the integer is itself a power of 2, you can continue to extend this technique efficiently and indefinitely (for example, add a n >> 32 line for 64-bit integers).

More Related Contents:

  1. What are bitwise shift (bit-shift) operators and how do they work?
  2. How does XOR variable swapping work?
  3. Should a function have only one return statement?
  4. What is the difference between concurrency and parallelism?
  5. Can every recursion be converted into iteration?
  6. Why shouldn’t I use “Hungarian Notation”?
  7. Expression Versus Statement
  8. Prefer composition over inheritance?
  9. Singletons: good design or a crutch? [closed]
  10. Which, and why, do you prefer Exceptions or Return codes?
  11. How do I display the binary representation of a float or double?
  12. Buffered vs unbuffered IO
  13. Difference between parameter and argument [duplicate]
  14. What is the difference between Type and Class?
  15. Allen Holub wrote “You should never use get/set functions”, is he correct? [duplicate]
  16. What are the lesser known but useful data structures?
  17. Why is it recommended to have empty line in the end of a source file?
  18. What’s the best name for a non-mutating “add” method on an immutable collection? [closed]
  19. Are exceptions really for exceptional errors? [closed]
  20. What is a stack overflow?
  21. Generate colors between red and green for a power meter?
  22. Calculating a 2D Vector’s Cross Product
  23. Hash Code and Checksum – what’s the difference?
  24. How to name variables
  25. In what situations is octal base used?
  26. When should a method be static?
  27. Code Golf: Conway’s Game of Life
  28. Why would a language NOT use Short-circuit evaluation?
  29. Finding closest match in collection of numbers [closed]
  30. Is there a known implementation of an indexed linked list?

Leave a Comment