After two days thinking your explanation, i have understand very well
now, thanks very much!
There are two point with my acquaintance:
1. "--x" at the first, it advoid next "power of two" is double with
the "power of two", like 1000(dec is 8), it will became 16.
2. "i<<=1" (doing i++ in the for loop), it is very very profound and
effective. I coat almost 2 hours about this.
2011/4/2 Hari Edo <hari....@gmail.com>:
>
> 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
--
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
