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

Question

I want to find if the number entered by the user has a force of two or not.

My code is not working.

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 I can find the strength of two numbers.
For example, 8 is power 2.
22 not with a power of 2, etc.

Answer 1

You can check if a positive integer n power 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 really a power of 2, then in binary, it will look like this:

 10000000... 

therefore n - 1 looks like

 01111111... 

and when bitwise and them:

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

Now, if n not a power of 2, then its binary representation will contain several other 1s in addition to the leading 1, which means that both n and n - 1 will have the same leading 1 bit (since subtraction 1 cannot disable this bit, if there is one more in the binary representation). Therefore, the & operation cannot produce 0 if n not a power of 2, since & with two leading bits n and n - 1 will produce 1 by itself. This, of course, suggests that n positive.

This is also explained in the “Quick algorithm to check if a positive number is a power of two” on Wikipedia.

---

Quick health check:

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

 one
 2
 four
 8
 16
 32
 64

Answer 2

You can use bitwise AND (&) operator :

 return (num & -num) == num 

Why does it work?

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

 0000 0000 0000 0000 0000 0000 0000 1000 

Now let's see how -8 is presented? ^one

 1111 1111 1111 1111 1111 1111 1111 1000 

Finally, let me 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, say 7 , which does not matter.

 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 @arshajii already mentioned, think about what happens if num is zero. I will leave a solution for you :)

¹ A good way to remember how to calculate this: Start with the rightmost bit, for every 0 you see, don’t change it when you see 1, leave it and continue, but from now on, invert all the bits. I tried to explain it more here .

Answer 3

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

Keep dividing by 2 until you reach 1 or an odd number. If it reaches 1, it has a power of 2, otherwise it is not.

Answer 4

A simple 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-cheating solutions (which are really pretty smart), but it is very easy to see how it works and check if it works in your head.

To enter 4 we get:

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

For an invalid input, for example 5 , we get:

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

Answer 5

  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; } 

Answer 6

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")