From: Daniel Martin <martin@...>
Date: 2006-08-08T06:07:01+09:00
Subject: Re: nextPowerOf2(n)

Daniel Martin <martin@snowplow.org> writes:

> Others have already given you floating point solutions to this, but
> I've found that at least for numbers under 2**64, this is faster (uses
> only integer arithmetic).  This method is also easily translateable
> into extremely fast C, if that becomes necessary:

(code snipped)

I should note that the algorithm I used - which could, I suppose, be
viewed as simply clever loop unrolling after doing quick 32-bit shifts
to get into the ballpark, was cribbed from some assembly in the C
header file longlong.h, which includes the macro count_leading_zeros
that counts the number of zeros in the front of a long long variable.
Any C implementation would probably be advised to make good use of
that macro, which may, depending on your processor, be implemented as
a single assembly language instruction. (See the BSR instruction on
x86, for example)

Also, since someone was saying that all the integer math
implementations were essentially equivalent in speed, being all
O(log(n)), here's a O(log(log(n))) implementation.  I shudder to think
though how big an input you'd need before this beats my earlier code:

def nextPowerOf2(n)
  return n if (n-1)&n == 0
  return 1 if n < 2
  n <<= 1
  t = [2]
  t.unshift(t[0]*t[0]) while t[0] < n
  t.shift
  ret = 1
  t.each {|s|
    if (s <= n) then
      ret *= s
      n /= s
    end
  }
  ret
end