chsalvia
asked on
64-bit power of 2 calculation
I found online a nice algorithm for calculating the next highest power of 2. However, the algorithm takes a 32-bit integer. It seems to work just as well on 64-bit integers, but I'm not sure if it's guaranteed to always work. Will the following algorithm always return a 64-bit integer that is the next greatest power of 2?
uint64_t nextp2(uint64_t n)
{
--n;
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
++n;
return n;
}
uint64_t nextp2(uint64_t n)
{
--n;
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
++n;
return n;
}
ASKER
That doesn't seem to work.
For example, that yields 0 for the value 100
For example, that yields 0 for the value 100
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
You're right. I was screwing up the return value. Thanks.
The order is not important
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
n |= n >> 32;
works just as well
but if the number is already a power of two, you get the same number back, not the "next" power of two
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
n |= n >> 32;
works just as well
but if the number is already a power of two, you get the same number back, not the "next" power of two
>> The order is not important
Indeed. You just needed to add :
n |= n >> 32;
to make it 64bit integer compatible.
Indeed. You just needed to add :
n |= n >> 32;
to make it 64bit integer compatible.
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
n++;