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
6
Medium Priority
?
1,080 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
[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
  • Learn & ask questions
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

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

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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.

730 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