• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1091

# 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;
}
0
chsalvia
1 Solution

Software ArchitectCommented:
the order is important, it should be:

n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
n++;
0

Author Commented:
That doesn't seem to work.

For example, that yields 0 for the value 100
0

Software ArchitectCommented:
Using my calculator:

n--;    // gives 99
n |= n >> 1;   // gives 115
n |= n >> 2;   // gives 127
n |= n >> 4;   // gives 127
n |= n >> 8;   // gives 127
n |= n >> 16;   // gives 127
n |= n >> 32;   // gives 127
n++;  // gives 128

so, it works perfectly with 100

0

Author Commented:
You're right.  I was screwing up the return value.  Thanks.
0

Commented:
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
0

Commented:
>> The order is not important

Indeed. You just needed to add :

n |= n >> 32;

to make it 64bit integer compatible.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.