Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

java

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..

like image 487
sam Avatar asked Oct 15 '13 14:10

sam


People also ask

How do you check if a number is the power of 2?

Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

How do you check if a number is a power of a number?

A simple solution is to repeatedly compute powers of x. If a power becomes equal to y, then y is a power, else not.

How do you know if a number is a power of 2 or not using Bitwise Operators?

If (x & (x-1)) is zero then the number is power of 2. For example, let x be 8 ( 1000 in binary); then x-1 = 7 ( 0111 ). This outputs the bit is power of 2 . This outputs the bit is not power of 2 .


1 Answers

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); } 
 1 2 4 8 16 32 64 
like image 58
arshajii Avatar answered Sep 28 '22 03:09

arshajii