(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.
Comments
(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:
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:
which performs 3 operations which involve each element of the list of the BigInt, we're replacing it with: 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.