Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# 64-bit power of 2 calculation

Posted on 2007-11-25
Medium Priority
1,080 Views
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
Question by:chsalvia
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 55

Expert Comment

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

ID: 20347886
That doesn't seem to work.

For example, that yields 0 for the value 100
0

LVL 55

Accepted Solution

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

Author Comment

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

LVL 84

Expert Comment

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

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

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
###### Suggested Courses
Course of the Month11 days, 11 hours left to enroll