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