Evaluate if integer is POT (Power Of Two)

Question

Possible Duplicates:
Query about working out whether number is a power of 2
How to check if a number is a power of 2

I require a function body for this prototype:

bool isPOT(int x);

So it would return eg isPOT(3) = FALSE, but isPOT(8) = TRUE

What is the most pretty/concise algorithm? And what is the most efficient?

PS: I am amazed that I cannot find this question on SO, so I am fully expecting someone to detect some duplicate.

PPS: can someone please create POT, NPOT, Power-Of-Two tags?

Yes, there are numerous duplicates, e.g. [Query about working out whether number is a power of 2](http://stackoverflow.com/questions/666647/query-about-working-out-whether-number-is-a-power-of-2) — Paul R, Mar 05 '11 at 07:46
Strange that I didn't see a match from typing the title, I guess maybe because I used 'two' instead of '2' — P i, Mar 05 '11 at 08:04
@user470379: for low-level work / optimisation (especially graphics) POT and NPOT are commonly used acronyms — P i, Mar 05 '11 at 08:06

score 12 · Accepted Answer · answered Mar 05 '11 at 07:48

12

bool IsPOT(int x)
{
    return (x > 0) && ((x & (x - 1)) == 0);
}

answered Mar 05 '11 at 07:48

Paul R

1

One might want to rewrite this in macro form, so that it works on any type of integer #define ISPOW2(x) ( (x)>0 && !( (x) & ((x) - 1) ) ) – datenwolf Mar 05 '11 at 11:57
3

@datenwolf: except you then get all the usual problems with macros - it's probably better just to keep as an int function, which will handle char, short and int, and then do an additional version if you need to handle anything wider than an int. – Paul R Mar 05 '11 at 14:54

score 6 · Answer 2 · answered Mar 05 '11 at 07:45

6

Not sure if this exact question occurred, but the check is easy

x & (x - 1) == 0

answered Mar 05 '11 at 07:45

Nikita Rybak

3

Almost - you also need to check for x > 0, otherwise you get an incorrect result when `x = 0`. – Paul R Mar 05 '11 at 07:47

2 Answers2