?
Solved

64-bit power of 2 calculation

Posted on 2007-11-25
6
Medium Priority
?
1,088 Views
Last Modified: 2012-08-13
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
Comment
Question by:chsalvia
6 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 20347861
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 Comment

by:chsalvia
ID: 20347886
That doesn't seem to work.

For example, that yields 0 for the value 100
0
 
LVL 55

Accepted Solution

by:
Jaime Olivares earned 500 total points
ID: 20347942
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
Evaluating UTMs? Here's what you need to know!

Evaluating a UTM appliance and vendor can prove to be an overwhelming exercise.  How can you make sure that you're getting the security that your organization needs without breaking the bank? Check out our UTM Buyer's Guide for more information on what you should be looking for!

 

Author Comment

by:chsalvia
ID: 20347974
You're right.  I was screwing up the return value.  Thanks.
0
 
LVL 85

Expert Comment

by:ozo
ID: 20348480
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 20349257
>> The order is not important

Indeed. You just needed to add :

       n |= n >> 32;

to make it 64bit integer compatible.
0

Featured Post

Easily manage email signatures in Office 365

Managing email signatures in Office 365 can be a challenging task if you don't have the right tool. CodeTwo Email Signatures for Office 365 will help you implement a unified email signature look, no matter what email client is used by users. Test it for free!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
There's never been a better time to become a computer scientist. Employment growth in the field is expected to reach 22% overall by 2020, and if you want to get in on the action, it’s a good idea to think about at least minoring in computer science …
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

589 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question