Is there any faster way to check if a number is a integral power of 2 in c++

Question

I know this method and it is not efficient enough

(a/2)%2==0;

Depending on the size of a - you could do a single bit compare, checking for the values 2,4,8,16,32,64 etc. — Neil, Aug 10 '15 at 16:18
A division and a modulo, that's already pretty efficient! Have you benchmarked and determined this to be a bottleneck? — DarkDust, Aug 10 '15 at 16:18
actually I am getting Time Limit Exceeded in a competitive programming problem — g.i joe, Aug 10 '15 at 16:19
@SouravGhosh :Problem is to convert one number in minimum operations into another — g.i joe, Aug 10 '15 at 16:26
@g.ijoe he means [XY problem](http://meta.stackexchange.com/q/66377/230282). Btw your way to check power of 2 is completely incorrect. And that expression should easily optimize out by the compiler, so it shouldn't take much time. If it takes long time to run, measure or profile it — phuclv, Aug 10 '15 at 16:36

score 6 · Answer 1 · answered Aug 10 '15 at 16:20

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = (v & (v - 1)) == 0;

Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:

f = v && !(v & (v - 1));

RiaD · Accepted Answer · 2015-08-10T16:22:02.170

4

Your method does not check that. It will return true for 12 for example.(and will return false for 2)

To check you may use x != 0 && (x & (x - 1)) == 0

edited Aug 10 '15 at 16:22

answered Aug 10 '15 at 16:18

RiaD

Heh.. we came up with the same example... – Eugene Sh. Aug 10 '15 at 16:19
@EugenSh. it's smallest multiple of 4, which is not is power of two, so it's quite natural – RiaD Aug 10 '15 at 16:20

score 3 · Answer 3 · answered Aug 10 '15 at 16:25

3

If you're using gcc and x64 there's an intrinsic that lets you use the CPU instruction that counts bits:

int __builtin_popcount (unsigned int x)

answered Aug 10 '15 at 16:25

James

How can the population count be used to determine whether a number is to the power of 2? – DarkDust Aug 11 '15 at 06:54
@DarkDust values that are a power of 2 have only one bit set – James Aug 11 '15 at 07:26
Right. So obvious it hurts… – DarkDust Aug 11 '15 at 07:40

3 Answers3