Find if a number is a power of two without math function or log function

Question

I want to find if a user entered number is a power of two or not.

My code doesn't work.

public class power_of_two
{  
    public static void main(String args[])  
    {  

        Scanner in=new Scanner(System.in);
        System.out.println("Enter the number : ");
        int num = in.nextInt();

        int other = 1;  
        if(((~num) & 1) == 1)  
        {  
            System.out.println("The number is a power of two");  
        }  
        else  
        {
            System.out.println("The number is a  NOT A power of two");  
        }
    }  
}

Let me know how can I find the power of two number.
For example 8 is a power of 2.
22 is not a power of 2, etc..

I don't think this question was rightfully closed. The linked "duplicate questions" are about two different languages (C# and PHP, respectively). Sure, the semantics are the same, but this is specifically a *Java* question. For reference, see http://meta.stackexchange.com/questions/189850/how-should-duplicates-of-language-independent-questions-be-handled. — arshajii, Oct 15 '13 at 22:14

arshajii · Accepted Answer · 2014-01-04T16:12:10.513

You can test if a positive integer n is a power of 2 with something like

(n & (n - 1)) == 0

If n can be non-positive (i.e. negative or zero) you should use

(n > 0) && ((n & (n - 1)) == 0)

If n is truly a power of 2, then in binary it will look like:

10000000...

so n - 1 looks like

01111111...

and when we bitwise-AND them:

  10000000...
& 01111111...
  -----------
  00000000...

Now, if n isn't a power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both n and n - 1 will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the & operation cannot produce 0 if n is not a power of 2, since &ing the two leading bits of n and n - 1 will produce 1 in and of itself. This of course assumes that n is positive.

This is also explained in "Fast algorithm to check if a positive number is a power of two" on Wikipedia.

Quick sanity check:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

I recently found out about this alternative approach, which works based on the same principle and is a lot more modular(?): `Integer.bitCount(n) == 1` — Andres Stadelmann, Apr 27 '16 at 10:25

Maroun · Answer 2 · 2016-02-06T09:21:23.453

97

You can use the bitwise AND (&) operator:

return (num & -num) == num

Why this works?

Consider the number 8, what it is in binary (assuming 32-bits)?

0000 0000 0000 0000 0000 0000 0000 1000

Now let's see how -8 is represented? ¹

1111 1111 1111 1111 1111 1111 1111 1000

Finally.. let's calculate 8 & -8:

0000 0000 0000 0000 0000 0000 0000 1000   8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &
1111 1111 1111 1111 1111 1111 1111 1000  -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000   8    ¯\_(ツ)_/¯

Now let's take another example, let's say 7, which is not power of two.

0000 0000 0000 0000 0000 0000 0000 0111   7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &                       
1111 1111 1111 1111 1111 1111 1111 1001  -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  != 7  ¯\_(ة_ة)_/¯

As mentioned by @arshajii, think what will happen if num is zero.. I'll leave the solution for you :)

¹ A good way to remember how to calculate that: Begin from the rightmost bit, for each 0 you see, don't change it, when you see 1, leave it and proceed, but from now on, invert all bits. I tried to explain this more here.

edited Feb 06 '16 at 09:21

answered Oct 15 '13 at 14:05

Maroun

94,125
30
188
241

4

May not be obvious as to why that is -8. Perhaps where that came from (http://en.wikipedia.org/wiki/Two's_complement) would be helpful. – Cruncher Oct 15 '13 at 14:16
2

I think you need a `num != 0 && ...` in there (if `num` can be `0`). Otherwise +1 – arshajii Oct 15 '13 at 14:28
2

If the `num` < 0 e.g. -8 then this would fail. I guess you need to check that it is the absolute value of num, but +1 anyway – Harrison Oct 15 '13 at 19:27
Why `if (cond) { return true; }` instead of `return cond;` ? – TemplateRex May 21 '15 at 05:57
The check against zero can be done like `(num & - num) > (num - 1)` – TemplateRex May 21 '15 at 06:33
@TemplateRex that will return `true` for 0, which is *not* a power of 2. – Maroun May 21 '15 at 09:43
at least in C++ [it works](http://coliru.stacked-crooked.com/a/116119eb5337ce78), did you try this in Java? – TemplateRex May 21 '15 at 10:29

Jeroen Vannevel · Answer 3 · 2013-10-15T18:07:18.767

7

double input = 22;

while(((input != 2) && input % 2 == 0) || input == 1) {
 input = input /2;
}

return input == 2;

Keep dividing it by 2 until you reach 1 or an odd number. If it reaches 1 it's a power of 2, otherwise it isn't.

edited Oct 15 '13 at 18:07

answered Oct 15 '13 at 14:06

Jeroen Vannevel

43,651
22
107
170

2

I agree. If the OP is looking for readability this is the approach he should take, but performance wise the other algorithms are much better. – Troubleshoot Oct 15 '13 at 14:11
Don't forget to re assign `input`.. For now this loop is infinite. – Maroun Oct 15 '13 at 14:22
1

Not the fastest solution, but one that needs less knowledge of 2-er complements and bit hacking. Like Bubblesort for sorting which is a bad solution but one easy to understand – AlexWien Oct 15 '13 at 14:38
Not only is this less readable but the title of the question says "without math function" which I would assume means not using the division operator. – Eterm Oct 15 '13 at 17:33
@Eterm: the way I interpreted the question was that he couldn't use `Math` functions, otherwise he would've specified that it would be bitwise. – Jeroen Vannevel Oct 15 '13 at 17:39
This code doesn't work for `input=1`. Maybe you should replace `input/2` by `input` in all conditions. In addition, it might be good to avoid an infinite loop for `input=0`. – anatolyg Oct 15 '13 at 17:40
Also, does the `%` operator work with `double` type? (I am not familiar with Java) – anatolyg Oct 15 '13 at 17:42
why would this not work for `input=1`? the first condition so there is no loop and it will return false (as it should). I agree though that `input=0` will loop infinitely – Jeroen Vannevel Oct 15 '13 at 17:44
@JeroenVannevel 1 is a power of 2, it is 2^0. – Eterm Oct 15 '13 at 17:46

crazy2be · Answer 4 · 2013-10-21T06:03:15.107

The straightforward solution:

bool isPowerOfTwo(int n) {
    // All values < 1 cannot be (positive, at least) powers of two.
    if (n < 1) return false;

    // Keep shifting bits.
    while (n > 1) {
        // Since n > 1, the low bit set means at least two bits must
        // be set, making n no longer a power of two.
        if (n & 0x1) return false;
        // Throw away the bottom (zero) bit.
        n >>= 1;
    }
    // Only one bit was set, therefore, n is a power of two.
    return true;
}

Of course, this is not as optimal as some of the other bit-trickery solutions (which are indeed quite clever), but it's very easy to see how it works, and verify it works in your head.

For the input 4, we get:

n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true

For an invalid input, like 5, we get:

n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)

score 0 · Answer 5 · edited Mar 08 '15 at 19:00

   public boolean isPowerOfTwo(int n){

            boolean isPower=false;
            int temp=n;

            while(temp>=2){
                if(temp%2==0){
                    isPower=true;

                }else{
                    isPower=false;
                    break;
                }
                temp=temp/2;
            }

            if(isPower){
                System.out.println("power of 2");
            }else{
                System.out.println("not power of 2");
            }

            return isPower;
        }

score -3 · Answer 6 · edited Nov 23 '15 at 08:49

-3

A very simple solution.

int n = 8; // any integer and you can take it from user also
for(;n>0;n++){
    if(n%2 != 0) {
        System.out.println("not a power of two")
        return;
    } // if ends here
    n = n/2;
}// for ends here
System.out.println("power of two")

edited Nov 23 '15 at 08:49

jiaweizhang

809
1
11
28

answered Dec 11 '13 at 08:33

Pankaj Goyal

950
9
15

You can't do `n++` in this case and the expression must be `n >=2 `. – karlphillip Jun 07 '16 at 22:22

Find if a number is a power of two without math function or log function

6 Answers6

Linked