Given a number which is power of 2, check if it is even power or odd power

Question

I am given a number n , which is always a power of 2. I want to check whether n is odd power of 2 or even power of 2.

For example: n=4 , ans= even n=8, ans=odd (because 8 is 2^3) n=1024 , ans=even.

Can I do it using bitwise operations/ or some faster method.

Answer 1

Lets start off with the statement 'bitwise operations on unbounded integers is meaningless'. You're not going to be testing if the number 2¹²⁸ has an even exponent or not. The problem area is constrained to, lets say, unsigned 32 bits. This could also be 64 easily (the long data type), but its easier to type 32 bit numbers.

The number 2ⁿ, when written in binary has exactly one 1 in it:

2⁰ = 0...0001
2¹ = 0...0010
2² = 0...0100
2³ = 0...1000

and so forth. The question then is "what bitwise operation will have a value that is 0 or not 0 when done against such a number?"

The value would be 2² + 2⁰ which gives us 5. This pattern repeats itself for all of the even exponents.

So, the bitwise operation is & 5 (or & A). The value of 5₂ is 0101 with the odd values as 0, while 10₂ is 1010 with the even values as 0. This value is then done for each nyble (half a byte) in the number: the value we are interested in is 0101 0101 0101 0101 0101 0101 0101 0101 or 0x55555555

n & 0x55555555 will give a value of 0 when the power of 2 is odd and some other value when the power of 2 is even. n & 0xAAAAAAAA will do the opposite (0 when the power of 2 is even and some other value when it is odd).

n & 0x55555555 is in effect n & (2⁰ + 2² + 2⁴ + 2⁶ + ... + 2³⁰) which again, gives us the answer we are after.

Answer 2

Assuming n is a 32 bit integer:

If n and'ed with x55555555 > 0 then even else odd

Assuming n is a 64 bit integer:

If n and'ed with x5555555555555555 > 0 then even else odd

If you put the mask into hex calculator, that also shows binary, you will see that the mask has all even bits set:

0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 - 64 bits
or
0101 0101 0101 0101 0101 0101 0101 0101 - 32 bits

Answer 3

If it is known that n is indeed a power of 2, then only one bit in the integer can ever be lit.
If the index of that bit is even, then your answer is even (assuming bit indices are 0-based).

For negative numbers, you may want to use the absolute value.

And obviously, the assumption is that we are dealing with 32-bit or 64-bit integers, not floating point numbers.

Answer 4

Can use right shift instead of bitwise? something like this (no input checking for simplicity):

public bool IsEvenPower(int n)
{
    int count = 0;
    int remaining = n;
    do
    {
        remaining = remaining >> 1;     
        count++;        
    }
    while(remaining > 1);
    return count % 2 == 0;
}

Answer 5

I'll turn my comment into an answer, maybe I'll get a +1 or two.

The exponent of a power of 2 is even when the number is a power of 4.

That is, if the exponent is even, you can divide it by 2, so

2 ^ n = 2 ^ (2 * m) = 4 ^ m

So (pseudocode)

function isEvenExponent(int n)
    return (n % 4) == 0

...or if you like bitwise operations

function isEvenExponent(int n)
    return (n & 3) == 0

Answer 6

You can use following method:

public bool IsEvenPower(int n)
{
    int power = 0;
    power=(Math.log(n) / Math.log(2));
    if(power%2==0)
    {
        return true;

    }
    else
    {
        return false;   
    } 
}

power=(Math.log(n) / Math.log(2)); this line find the power of number when number is power of 2.when power is even function return true else function return false