power of 2

[raghu]

is it possible to write a code using bitwise operators for checking
whether a number is power of 2 or in general power of n
(n=2,3,4,...)??

Thanks a lot.

Regards,
Raghu

 

[Richard Heathfield]

raghu said:

is it possible to write a code using bitwise operators for checking
whether a number is power of 2
Yes.

or in general power of n
(n=2,3,4,...)??

Yes.

 

[Frederick Gotham]

raghu posted:

is it possible to write a code using bitwise operators for checking
whether a number is power of 2

There's a recent thread which counts the number of set bits in an integer
which would work for you, e.g.:

#define IS_POW_TWO(x) (1==QUANT_BITS((x)))

or in general power of n
(n=2,3,4,...)??

#define IS_POW_X(x,pow) (!((x)%(pow)))

 

[Snis Pilbor]

raghu posted:



#define IS_POW_X(x,pow) (!((x)%(pow)))

No, this will check whether x is a multiple of pow. For example,
!(6%2) is true even though 6 is certainly not a power of 2.

 

[Richard Heathfield]

Frederick Gotham said:

raghu posted:



There's a recent thread which counts the number of set bits in an integer
which would work for you, e.g.:

#define IS_POW_TWO(x) (1==QUANT_BITS((x)))

There's an easier way.

#define IS_POW_X(x,pow) (!((x)%(pow)))

It doesn't use bitwise operators and doesn't check whether a number is a
power of n. Oops.

 

[pete]

is it possible to write a code using bitwise operators for checking
whether a number is power of 2 or in general power of n
(n=2,3,4,...)??

int n_is_Power_of_two(long unsigned n)
{
return (n & n - 1) == 0 && n != 0;
}

int n_is_Power_of_four(long unsigned n)
{
return (n & n - 1) == 0 && n % 3 == 1;
}

int n_is_Power_of_eight(long unsigned n)
{
return (n & n - 1) == 0 && n % 7 == 1;
}

 

[dcorbit]

In general, for bit twiddling:
http://graphics.stanford.edu/~seander/bithacks.html

Which has this (for instance):
http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

Which is Pete's solution.

Another good source for interesting things like this is hackmem:
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html