From: Daniel Martin <martin@...>
Date: 2006-08-08T01:19:15+09:00
Subject: Re: nextPowerOf2(n)

Ch Skilbeck <ruby@skilbeck.com> writes:

> Can someone tell me if there's a better way to do this? It takes a 
> number and returns the next power of 2 up (or the original if it was 
> already a power of 2) Specifically, are there features of Ruby that I 
> should be using in this case?

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:

def nextPowerOf2(n)
  return n if (n-1)&n == 0
  pow=1
  while (n >= 0x100000000) do  pow += 32; n >>= 32; end
  if (n & 0xFFFF0000 > 0) then pow += 16; n >>= 16; end
  if (n & 0xFF00 > 0)     then pow += 8;  n >>= 8;  end
  if (n & 0xF0 > 0)       then pow += 4;  n >>= 4; end
  if (n & 0xC > 0)        then pow += 2;  n >>= 2; end
  if (n & 0x2 > 0)        then pow += 1;  n >>= 1; end
  1<<pow
end

It returns "0" when handed 0, when arguably it should return 1; on the
other hand, the log-based methods simply blow up when handed 0, so
this is an improvement.

Benchmark on the Math.log method, the originally posted code, and then
my code shows:

      user     system      total        real
  1.281000   0.000000   1.281000 (  1.281000)
  4.547000   0.000000   4.547000 (  4.547000)
  0.922000   0.000000   0.922000 (  0.922000)

Benchmark code was:

checkarray = Array.new(50000) {rand(1<<64)}
Benchmark.bm { |x|
 x.report { checkarray.each {|f| nextPowerOf2_log(f)}}
 x.report { checkarray.each {|f| nextPowerOf2_orig(f)}}
 x.report { checkarray.each {|f| nextPowerOf2(f)}}
}