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

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
Asked:
chsalvia
1 Solution
 
Jaime OlivaresSoftware 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
 
chsalviaAuthor Commented:
That doesn't seem to work.

For example, that yields 0 for the value 100
0
 
Jaime OlivaresSoftware 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
Creating Active Directory Users from a Text File

If your organization has a need to mass-create AD user accounts, watch this video to see how its done without the need for scripting or other unnecessary complexities.

 
chsalviaAuthor Commented:
You're right.  I was screwing up the return value.  Thanks.
0
 
ozoCommented:
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
 
Infinity08Commented:
>> 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.

Join & Write a Comment

Featured Post

Network Scalability - Handle Complex Environments

Monitor your entire network from a single platform. Free 30 Day Trial Now!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now