Preface explains

Algorithm learning, daily brush problem record.

Subject to connect

4 power

The subject content

Given an integer, write a function to determine whether it is a power of 4. If so, return true; Otherwise, return false.

The integer n is a power of 4 if there is an integer x such that n == 4x

Example 1:

Enter n = 16

Output: true,

Example 2:

Enter n = 5

Output: false

Example 3:

Input: n = 1

Output: true,

Tip:

-2^31 <= n <= 2^31 – 1

Advanced:

Can you solve this problem without looping/recursion?

The analysis process

The solution to the power of two has been written earlier, see the article power of two

So, there’s a similarity between the solution for a power of four and a power of two.

Let’s look at the previous solution to the power of two:

Class Solution {public Boolean isPowerOfTwo(int n) {// the power of two must be greater than or equal to 1, and then the rightmost 1 bit of n must be 0 by using the &operation similar to the hamming distance. So if this 1 becomes 0, the result becomes 0, which is equal to 0 after the ampersand is a power of 2 return n >= 1 && (n & (n-1)) == 0; }}Copy the code

Since the power of 4 must be a power of 2, we can directly use the solution method of the power of 2 first, and then select the power of 4 based on the power of 2.

If the first bit from the right is the 0th bit, we can see that the 1 of the power of 4 is in the even digit, so we just need to determine whether the even digit of n is 1.

For example, the binary value of 4 is 0100, and the binary value of 16 is 0001 0000.

Let’s construct a 32-bit binary number 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, and ampersand it with n, and if it’s a power of 4, the result is 0.

If it’s 4, 4 is a power of 4, and the binary value of 4 is 0100, then n & it’s 0000, which is just 0.

If it’s 2, 2 is not a power of 4, and the binary number of 2 is 0010, then n & it’s 0010, not 0.

So using this method, if it’s a power of four, it’s going to be zero.

Let’s say 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, which is 0xaaaaaaaa in hexadecimal notation.

To solve the code

If n&0xaaaaaaaa is equal to 0, then it is a power of 4, as follows:

Class Solution {public Boolean isPowerOfFour(int n) {// if the power of 2 is greater than or equal to 1, Because in addition to the other 2 power is only 1 bit is 1, so if this one becomes 0, the result will become zero, which is equal to zero after & operations is a power of 2 / / 4 power must be a power of 2, to judge by the method of judging a power of 2 is a power of 2, if right from the start bit 1 to 0, then a power of 1 are in even number 4, So just determine if the even digit of n is 1, construct the 32-bit binary number 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1010, and then amending n with it, if it's a power of 4, the result will be 0, for example, if the binary number of 4 is 0100, then amending n with it will be 0, So it's a power of 4, if it's a power of 2, then its binary is 0010, then n & it's 0010, not 0,2 is not a power of 4, so this method can be used to judge powers of 4. So 1010, 1010, 1010, 1010, 1010, Return n >= 1 && (n & (n-1)) == 0 && (n & 0xaaaaaaaa) == 0; return n >= 1 && (n & (n-1)) == 0 && (n & 0xaaaaaaaa) == 0; }}Copy the code

Submit the results

The execution time was 1ms, beating 100.00% of users in time, consuming 35.2MB of memory, and beating 97.32% of users in space.

The original link

A power of four