# Find whether a given number is a power of 4 or not

Given an integer n, find whether it is a power of 4 or not.

Example :

```Input : 16
Output : 16 is a power of 4

Input : 20
Output : 20 is not a power of 4
```

1. A simple method is to take log of the given number on base 4, and if we get an integer then number is power of 4.

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

## C++

 `// C++ program to find whether a given  ` `// number is a power of 4 or not ` `#include ` ` `  `using` `namespace` `std; ` `#define bool int ` ` `  `class` `GFG ` `{ ` `     `  `/* Function to check if x is power of 4*/` `public` `: ``bool` `isPowerOfFour(``int` `n) ` `{ ` `    ``if``(n == 0) ` `        ``return` `0; ` `    ``while``(n != 1) ` `    ``{  ` `        ``if``(n % 4 != 0) ` `            ``return` `0; ` `        ``n = n / 4;  ` `    ``} ` `    ``return` `1; ` `} ` `}; ` ` `  `/*Driver code*/` `int` `main() ` `{ ` `    ``GFG g; ` `    ``int` `test_no = 64; ` `    ``if``(g.isPowerOfFour(test_no)) ` `        ``cout << test_no << ``" is a power of 4"``; ` `    ``else` `        ``cout << test_no << ``"is not a power of 4"``; ` `    ``getchar``(); ` `} ` ` `  `// This code is contributed by SoM15242 `

## C

 `#include ` `#define bool int ` ` `  `/* Function to check if x is power of 4*/` `bool` `isPowerOfFour(``int` `n) ` `{ ` `  ``if``(n == 0) ` `    ``return` `0; ` `  ``while``(n != 1) ` `  ``{     ` `   ``if``(n % 4 != 0) ` `      ``return` `0; ` `    ``n = n / 4;       ` `  ``} ` `  ``return` `1; ` `}  ` ` `  `/*Driver program to test above function*/` `int` `main() ` `{ ` `  ``int` `test_no = 64; ` `  ``if``(isPowerOfFour(test_no)) ` `    ``printf``(``"%d is a power of 4"``, test_no); ` `  ``else` `    ``printf``(``"%d is not a power of 4"``, test_no); ` `  ``getchar``(); ` `} `

/div>

## Java

 `// Java code to check if given ` `// number is power of 4 or not ` ` `  `class` `GFG { ` ` `  `    ``// Function to check if  ` `    ``// x is power of 4 ` `    ``static` `int` `isPowerOfFour(``int` `n) ` `    ``{ ` `        ``if``(n == ``0``) ` `        ``return` `0``; ` `        ``while``(n != ``1``) ` `        ``{  ` `            ``if``(n % ``4` `!= ``0``) ` `            ``return` `0``; ` `            ``n = n / ``4``;      ` `        ``} ` `        ``return` `1``; ` `    ``}  ` ` `  `    ``// Driver program  ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `test_no = ``64``; ` `        ``if``(isPowerOfFour(test_no) == ``1``) ` `         ``System.out.println(test_no +  ` `                           ``" is a power of 4"``); ` `        ``else` `         ``System.out.println(test_no +  ` `                           ``"is not a power of 4"``); ` `    ``} ` `} ` ` `  `// This code is contributed ` `// by  prerna saini `

## Python3

 `# Python3 program to check if given ` `# number is power of 4 or not  ` ` `  `# Function to check if x is power of 4 ` `def` `isPowerOfFour(n): ` `    ``if` `(n ``=``=` `0``): ` `        ``return` `False` `    ``while` `(n !``=` `1``): ` `            ``if` `(n ``%` `4` `!``=` `0``): ` `                ``return` `False` `            ``n ``=` `n ``/``/` `4` `             `  `    ``return` `True` ` `  `# Driver code ` `test_no ``=` `64` `if``(isPowerOfFour(``64``)): ` `    ``print``(test_no, ``'is a power of 4'``) ` `else``: ` `    ``print``(test_no, ``'is not a power of 4'``) ` ` `  `# This code is contributed by Danish Raza `

## C#

 `// C# code to check if given ` `// number is power of 4 or not ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Function to check if ` `    ``// x is power of 4 ` `    ``static` `int` `isPowerOfFour(``int` `n) ` `    ``{ ` `        ``if` `(n == 0) ` `            ``return` `0; ` `        ``while` `(n != 1) { ` `            ``if` `(n % 4 != 0) ` `                ``return` `0; ` `            ``n = n / 4; ` `        ``} ` `        ``return` `1; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `test_no = 64; ` `        ``if` `(isPowerOfFour(test_no) == 1) ` `            ``Console.Write(test_no +  ` `                    ``" is a power of 4"``); ` `        ``else` `            ``Console.Write(test_no +  ` `                ``" is not a power of 4"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` `

Output :

```64 is a power of 4
```

3. A number n is a power of 4 if following conditions are met.
a) There is only one bit set in the binary representation of n (or n is a power of 2)
b) The count of zero bits before the (only) set bit is even.

For example: 16 (10000) is power of 4 because there is only one bit set and count of 0s before the set bit is 4 which is even.

Thanks to Geek4u for suggesting the approach and providing the code.

## C++

 `// C++ program to check  ` `// if given number is  ` `// power of 4 or not  ` `#include ` ` `  `using` `namespace` `std; ` ` `  `bool` `isPowerOfFour(unsigned ``int` `n) ` `{ ` `    ``int` `count = 0; ` ` `  `    ``/*Check if there is only one bit set in n*/` `    ``if` `( n && !(n&(n-1)) ) ` `    ``{ ` `        ``/* count 0 bits before set bit */` `        ``while``(n > 1) ` `        ``{ ` `            ``n >>= 1; ` `            ``count += 1; ` `        ``}  ` ` `  `        ``/*If count is even then  ` `        ``return true else false*/` `        ``return` `(count%2 == 0)? 1 :0; ` `    ``} ` ` `  `    ``/* If there are more than 1 bit set ` `    ``then n is not a power of 4*/` `    ``return` `0; ` `}  ` ` `  `/*Driver code*/` `int` `main() ` `{ ` `    ``int` `test_no = 64; ` `    ``if``(isPowerOfFour(test_no)) ` `        ``cout << test_no << ``" is a power of 4"` `; ` `    ``else` `        ``cout << test_no << ``" is not a power of 4"``; ` `} ` ` `  `// This code is contributed by Shivi_Aggarwal `

## C

 `#include ` `#define bool int ` ` `  `bool` `isPowerOfFour(unsigned ``int` `n) ` `{ ` `  ``int` `count = 0; ` ` `  `  ``/*Check if there is only one bit set in n*/` `  ``if` `( n && !(n&(n-1)) ) ` `  ``{ ` `     ``/* count 0 bits before set bit */` `     ``while``(n > 1) ` `     ``{ ` `       ``n  >>= 1; ` `       ``count += 1; ` `     ``}       ` ` `  `    ``/*If count is even then return true else false*/` `    ``return` `(count%2 == 0)? 1 :0; ` `  ``} ` ` `  `  ``/* If there are more than 1 bit set ` `    ``then n is not a power of 4*/` `  ``return` `0; ` `}     ` ` `  `/*Driver program to test above function*/` `int` `main() ` `{ ` `   ``int` `test_no = 64; ` `   ``if``(isPowerOfFour(test_no)) ` `     ``printf``(``"%d is a power of 4"``, test_no); ` `   ``else` `     ``printf``(``"%d is not a power of 4"``, test_no); ` `   ``getchar``(); ` `} `

## Java

 `// Java program to check  ` `// if given number is  ` `// power of 4 or not  ` `import` `java.io.*; ` `class` `GFG  ` `{ ` `    ``static` `int` `isPowerOfFour(``int` `n) ` `    ``{ ` `        ``int` `count = ``0``; ` `         `  `        ``/*Check if there is  ` `        ``only one bit set in n*/` `        ``int` `x = n & (n - ``1``); ` `         `  `        ``if` `( n > ``0` `&& x == ``0``) ` `        ``{ ` `            ``/* count 0 bits  ` `            ``before set bit */` `            ``while``(n > ``1``) ` `            ``{ ` `                ``n >>= ``1``; ` `                ``count += ``1``; ` `            ``}  ` `         `  `            ``/*If count is even  ` `            ``then return true ` `            ``else false*/` `            ``return` `(count % ``2` `== ``0``) ? ``1` `: ``0``; ` `        ``} ` `         `  `            ``/* If there are more than  ` `            ``1 bit set then n is not a ` `            ``power of 4*/` `        ``return` `0``; ` `    ``}  ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `test_no = ``64``; ` `         `  `        ``if``(isPowerOfFour(test_no)>``0``) ` `            ``System.out.println(test_no + ` `                               ``" is a power of 4"``); ` `        ``else` `            ``System.out.println(test_no + ` `                               ``" is not a power of 4"``); ` `    ``} ` `} ` ` `  `// This code is contributed by mits `

## Python3

 `# Python3 program to check if given ` `# number is power of 4 or not  ` ` `  `# Function to check if x is power of 4 ` `def` `isPowerOfFour(n): ` `     `  `    ``count ``=` `0` `     `  `    ``# Check if there is only one  ` `    ``# bit set in n ` `    ``if` `(n ``and` `(``not``(n & (n ``-` `1``)))): ` `         `  `        ``# count 0 bits before set bit  ` `        ``while``(n > ``1``): ` `            ``n >>``=` `1` `            ``count ``+``=` `1` `         `  `        ``# If count is even then return ` `        ``# true else false ` `        ``if``(count ``%` `2` `=``=` `0``): ` `            ``return` `True` `        ``else``: ` `            ``return` `False` ` `  `# Driver code ` `test_no ``=` `64` `if``(isPowerOfFour(``64``)): ` `    ``print``(test_no, ``'is a power of 4'``) ` `else``: ` `    ``print``(test_no, ``'is not a power of 4'``) ` ` `  `# This code is contribued by Danish Raza `

## C#

 `// C# program to check if given ` `// number is power of 4 or not  ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``static` `int` `isPowerOfFour(``int` `n) ` `    ``{ ` `        ``int` `count = 0; ` `         `  `        ``/*Check if there is only one bit ` `        ``set in n*/` `        ``int` `x = n & (n-1); ` `         `  `        ``if` `( n > 0 && x == 0) ` `        ``{ ` `            ``/* count 0 bits before set bit */` `            ``while``(n > 1) ` `            ``{ ` `                ``n >>= 1; ` `                ``count += 1; ` `            ``}  ` `         `  `            ``/*If count is even then return  ` `            ``true else false*/` `            ``return` `(count % 2 == 0) ? 1 : 0; ` `        ``} ` `         `  `            ``/* If there are more than 1 bit set ` `            ``then n is not a power of 4*/` `        ``return` `0; ` `    ``}  ` ` `  `    ``/*Driver program to test above function*/` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `test_no = 64; ` `         `  `        ``if``(isPowerOfFour(test_no)>0) ` `            ``Console.WriteLine(``"{0} is a power of 4"``, ` `                                          ``test_no); ` `        ``else` `            ``Console.WriteLine(``"{0} is not a power of 4"``, ` `                                             ``test_no); ` `    ``} ` `} ` ` `  `// This Code is Contributed by mits `

## PHP

 ` 1) ` `    ``{ ` `    ``\$n` `>>= 1; ` `    ``\$count` `+= 1; ` `    ``}      ` ` `  `    ``/*If count is even then return true else false*/` `    ``return` `(``\$count``%2 == 0)? 1 :0; ` `} ` ` `  `/* If there are more than 1 bit set ` `    ``then n is not a power of 4*/` `return` `0; ` `}  ` ` `  `/*Driver program to test above function*/` ` `  `    ``\$test_no` `= 64; ` `     `  `if``(isPowerOfFour(``\$test_no``)) ` ` `  `    ``echo` `\$test_no``, ``" is a power of 4"``; ` ` `  `else` ` `  `    ``echo` `\$test_no``, ``" not is a power of 4"``; ` `     `  ` `  `#This Code is Contributed by Ajit ` `?> `

Output:

```64 is a power of 4
```

4. A number n is a power of 4 if following conditions are met.
a) There is only one bit set in the binary representation of n (or n is a power of 2)
b) The bits don’t AND(&) any part of the pattern 0xAAAAAAAA

For example: 16 (10000) is power of 4 because there is only one bit set and 0x10 & 0xAAAAAAAA is zero.

Thanks to Sarthak Sahu for suggesting the approach.

## C++

 `// C++ program to check  ` `// if given number is  ` `// power of 4 or not  ` `#include ` ` `  `using` `namespace` `std; ` ` `  `bool` `isPowerOfFour(unsigned ``int` `n) ` `{ ` `    ``return` `n !=0 && ((n&(n-1)) == 0) && !(n & 0xAAAAAAAA); ` `}  ` ` `  `/*Driver code*/` `int` `main() ` `{ ` `    ``int` `test_no = 64; ` `    ``if``(isPowerOfFour(test_no)) ` `        ``cout << test_no << ``" is a power of 4"` `; ` `    ``else` `        ``cout << test_no << ``" is not a power of 4"``; ` `} `

## C

 `// C program to check  ` `// if given number is  ` `// power of 4 or not  ` `#include ` `#define bool int ` ` `  `bool` `isPowerOfFour(unsigned ``int` `n) ` `{ ` `  ``return` `n != 0 && ((n&(n-1)) == 0) && !(n & 0xAAAAAAAA); ` `}     ` ` `  `/*Driver program to test above function*/` `int` `main() { ` `   ``int` `test_no = 64; ` `   ``if``(isPowerOfFour(test_no)) ` `     ``printf``(``"%d is a power of 4"``, test_no); ` `   ``else` `     ``printf``(``"%d is not a power of 4"``, test_no); ` `   ``getchar``(); ` `} `

## Java

 `// Java program to check  ` `// if given number is  ` `// power of 4 or not  ` `import` `java.io.*; ` `class` `GFG { ` `    ``static` `boolean` `isPowerOfFour(``int` `n) { ` `        ``return` `n != ``0` `&& ((n&(n-``1``)) == ``0``) && (n & ``0xAAAAAAAA``) == ``0``; ` `    ``}  ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args) { ` `        ``int` `test_no = ``64``; ` `         `  `        ``if``(isPowerOfFour(test_no)) ` `            ``System.out.println(test_no + ` `                               ``" is a power of 4"``); ` `        ``else` `            ``System.out.println(test_no + ` `                               ``" is not a power of 4"``); ` `    ``} ` `} `

## C#

 `// C# program to check  ` `// if given number is  ` `// power of 4 or not  ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `bool` `isPowerOfFour(``int` `n) ` `    ``{ ` `        ``return` `n != 0 && ((n&(n-1)) == 0) && ` `                        ``(n & 0xAAAAAAAA) == 0; ` `    ``}  ` ` `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `test_no = 64; ` `         `  `        ``if``(isPowerOfFour(test_no)) ` `            ``Console.WriteLine(``"{0} is a power of 4"``, ` `                                        ``test_no); ` `        ``else` `            ``Console.WriteLine(``"{0} is not a power of 4"``, ` `                                            ``test_no); ` `    ``} ` `} ` ` `  `// This code is contributed by mohit kumar 29 `

Output:

```64 is a power of 4
```

Why 0xAAAAAAAA ? This is because the bit representation is of powers of 2 that are not of 4. Like 2, 8, 32 so on..
Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

## tags:

Bit Magic Mathematical Mathematical Bit Magic