0

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.

  • Is there a size limit for the numbers? It would be easy if it's bounded with say 32 or 64 bit, but if the size could be arbitrarily large bitwise operations would maybe become more difficult to use. – thorsten müller Nov 8 '14 at 14:18
  • 1
    Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question. – gnat Nov 8 '14 at 14:53
  • 5
    Doesn't "an even power of 2" just mean "a power of 4" ... right off the top of my head, that might not be right – Rob Nov 8 '14 at 15:44
17

Lets start off with the statement 'bitwise operations on unbounded integers is meaningless'. You're not going to be testing if the number 2128 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 2n, when written in binary has exactly one 1 in it:

20 = 0...0001
21 = 0...0010
22 = 0...0100
23 = 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 22 + 20 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 52 is 0101 with the odd values as 0, while 102 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 & (20 + 22 + 24 + 26 + ... + 230) which again, gives us the answer we are after.

5

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
2

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.

1

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;
}
  • 2
    That runs O(n) time. It can be done in O(1) with the bitwise and. – user40980 Nov 10 '14 at 8:46
  • @MichaelT I'm not entirely sure on what's big oh of shifting, but from what I know it's very fast (do you happen to know what's big oh of it?). For the while loop, actually it's executing in log(n) time. So if shifting is negligible, the method should take around log(n). But yes, it's slower than bitwise – Phuong Nguyen Nov 10 '14 at 8:58
  • @PhuongNguyen no operation can be lower than O(1). If we assume that bit shifting is O(1) (which it is), you'd still have to do it O(n) times (because you're looping), making it O(n) by definition. – Martijn Nov 10 '14 at 13:17
  • +1 While, in general, masking with 0x55555... is simpler, this method works for any size value, even > 64 bits, such as a Java BigInteger. If speed were an issue, one could do a hybrid approach: Mask with 0xFFFFFFFF, if non-zero do the 0x55555555 trick, else right shift by 32 and try again. – user949300 Nov 10 '14 at 16:21
  • @user949300 in Java'as BigInteger, one would call getLowestSetBit and handle that rather than shifting (which caches the value in the BigInteger for use in other methods (grepcode))... and bitCount would also return the same value for a number 2^n. Might be interesting to dig into which one is faster for this case... – user40980 Nov 10 '14 at 19:18
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.