From: benjohn@...
Date: 2006-08-08T18:02:35+09:00
Subject: Re: nextPowerOf2(n)

The following integer implementation runs in log(log(n)) time (in non
mathematical speak, that's "fast" :) ).

[In a language like c, for a fixed length word, unroll the loop and
loose the descision logic so that it only deals with the word size
you're interested in].

class Integer
  def next_power_of_two
    mask_of_all_bits_below_top_bit + 1
  end

  def mask_of_all_bits_below_top_bit
    mask = self
    shift = 1
    while ((shifted_mask = mask >> shift) > 0) do
      mask = mask | shifted_mask
      shift = shift << 1
    end
    mask
  end
end