On Apr 1, 11:16 pm, a a <harvey.a...@gmail.com> wrote:
> But i can't understand the following algorithm
>
> function nextHighestPowerOfTwo(x) {
> --x;
> for (var i = 1; i < 32; i <<= 1) {
> x = x | x >> i;
> }
> return x + 1;
>
> }
On the first loop, take the value and "smear" its bits
once rightward:
x was: 0000100101100001
x >> 1: 0000010010110000
x | x >> 1: 0000110111110001
On the second loop, you could "smear" the bits once
rightward again (doing i++ in the for loop), but that
would be a waste of time since there can be no more
single 1 bits. All the runs of 1 bits are now fatter.
So on the second loop, smear the bits TWICE rightward,
by doing (i <<= 1) in the for loop instead.
x was: 0000110111110001
x >> 2: 0000001101111100
x | x >> 2: 0000111111111101
On the third loop, smear the bits FOUR rightward,
since any 1 bit is now fatter.
x was: 0000111111111101
x >> 4: 0000000011111111
x | x >> 4: 0000111111111111
We're done in this example, but the loop here
also tries to smear by 8 and smear by 16.
We then add 1, to roll over to the next power of
two.
x was: 0000111111111111
next power: 0001000000000000
However, because you don't want to have the
nextHighestPowerOfTwo(2048) to return 4096,
the function starts with x-1 instead of x.
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to android-developers@googlegroups.com
To unsubscribe from this group, send email to
android-developers+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
