0

Possible Duplicate:
How to check if a number is a power of 2

This question has been asked in an interview.

How to check if a number is in 2^n format {1, 2, 4, 8, 16, 32, ....}

without using *, /, +, -, % operators?

And you can't use loops also.

Community
  • 1
  • 1
Ashwini Agarwal
  • 4,828
  • 2
  • 42
  • 59

2 Answers2

15

Check if there is exactly one bit set in the binary representation.

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • 1
    aka "Is `N & (N-1)` zero" if one were actually aiming for efficiency and not random interview question requirements. – Amber Aug 06 '12 at 07:43
  • Amber: >without using *, /, +, -, % operators – Wug Aug 06 '12 at 07:44
  • 1
    @ both of you: I'm aware. I'm just pointing out the *efficient* way of doing it, hence why it's a *comment* and not an answer. – Amber Aug 06 '12 at 07:45
  • @Cicada the question is fairly nonsensical if it isn't. – Amber Aug 06 '12 at 07:45
  • 3
    @Cicada unless we're assuming integers, *any* number greater than or equal to zero is a power of 2. – Amber Aug 06 '12 at 07:47
  • 2
    There's an x86 assembly instruction that counts the number of set bits in an integer value. – Wug Aug 06 '12 at 07:48
  • @Amber What I meant is, the number could be a floating point. – user703016 Aug 06 '12 at 07:48
  • @Cicada I think what Amber means is that, e.g. 1.3 is two to the 0.37851162325373. If you're willing to work with non-integrals in general then everything positive is a power of two. – Tommy Aug 06 '12 at 08:09
  • 1
    While Amber's comment is correct for the real numbers, it's not correct for any type representable on a computer. For example, for floating point types, you could try the base-2 log rounded either up or down, but when you go back to exponentiate it, you'll raise an inexact exception even if the right result value does come out. Thus conceptually it's not a "power of two" even in the weirdness of the floating point number system. – R.. GitHub STOP HELPING ICE Aug 06 '12 at 10:01
9

Use the good old n & (n - 1) == 0, transformed in a way that does not use operator -.

int powerOfTwo(int number)
{
    int numberMinusOne = --number;
    ++number;

    if (number == 0)
        return 0;

    return (number & numberMinusOne) == 0;
}
user703016
  • 37,307
  • 8
  • 87
  • 112