A faster next-power-of-two algorithm

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

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.