A faster next-power-of-two algorithm

2 points by peripetylabs 13 years ago · 4 comments

Reader

I'm confused by this. Both the algorithms mentioned seem to give the wrong result when N is a power of 2.

For example, N=4. Set all the lower bits to 1, giving 7. Increment, giving 8, return 8. But the power of two no less than 4 is 4.

Am I missing something?

Also, the alleged faster solution is only faster for larger numbers (on a log scale). Sure, there are more of them, but what if your function is called more often for small numbers than large ones?

drostie 13 years ago
(Sorry, my first line was wrong.) You set all of the low bits to 1 for N - 1, not N. So 4 becomes 3 becomes 3 becomes 4; 5 becomes 4 becomes 7 becomes 8. In Haskell you'd write:
```
    nextPowerOf2 N = fill_bits (N - 1) + 1;
```
Mansour Moufid indeed gets the wrong answer when N is a power of 2. To rectify this, you'd replace the last assignment with the ternary `if w == N then w else (w << 1)`. You could then probably cook up an input where Moufid's algorithm is slower; if half the samples were powers of two and half weren't, a branch predictor would go nuts.
The real problem is that we're doing all of this in the context of primitive integers, not lists of integers making up a BigInt. Moufid might be on the right track for optimizing for such lists; rather than:
```
    nextPowerOf2 N = fill_bits (N - 1) + 1
```
which performs 3 operations which involve each element of the list of the BigInt, we're replacing it with:
```
    nextPowerOf2 N:Ns = if (powerOfTwo N) && (arrayOfZeros Ns) 
        then N:Ns else (onlyMSB N):[0 | n <- Ns]
```
This passes through the list once if the list is a power of two, and somewhere between once and twice if the list is not.
peripetylabsOP 13 years ago

To me, the next power of two after 4 is 8, not 4. If you prefer, you can add a line to simply return the input if it is already a power of two:
http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_...
(Edit: You forgot to subtract one before setting the lower bits and incrementing. If you omit that step, both these algorithms give the same result.)
Actually this algorithm is faster for smaller numbers too, because it always performs less operations in the loop -- one shift as opposed to a shift and a bitwise or.
- ColinWright 13 years ago
  > ... the next power of two after 4 is 8, not 4
  But he says the power of two not less than N. That's not the next power of two that's strictly greater than N.

Settings

A faster next-power-of-two algorithm

Keyboard Shortcuts