342. Power of Four

  • 37.9%

https://leetcode.com/problems/power-of-four/#/description

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

1
2
Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?


以0x开始的数据表示16进制,计算机中每位的权为16,即(16进制)10 = (10进制)1×16

方法一:

Simplest C++ solution maybe?

2的幂 满足 num&(num-1) == 0

0x 是零和x,表示十六进制

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return !(num & (num - 1)) && (num & 0x55555555);
}
};

其他实现

O(1) one-line solution without loops

1
2
3
4
5
public class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
}
}

The basic idea is from power of 2, We can use “n&(n-1) == 0” to determine if n is power of 2. For power of 4, the additional restriction is that in binary form, the only “1” should always located at the odd position. For example, 4^0 = 1, 4^1 = 100, 4^2 = 10000. So we can use “num & 0x55555555==num” to check if “1” is located at the odd position.

方法二:

我的代码实现:

1
2
3
4
5
6
7
8
class Solution {
public:
bool isPowerOfFour(int num) {
// & == 优先级
// '==' > '!=' > '&' > '^' > '!'
return num>0 && (num&(num-1))==0 && (num-1)%3==0;
}
};
1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return ((num-1)&num)==0 && (num-1)%3==0;
}
};

It means that binary representation of 4, 16 etc. will be 4 = 0100, 16 = 00010000. If you subtract 1 from 4, 16, …. you will get something like 0011 for 4 and 00001111 for 16. Finally when you make & you check that all the right bits is zero(it is one of the properties of numbers that is power of four).


https://discuss.leetcode.com/topic/42914/1-line-c-solution-without-confusing-bit-manipulations

1 line C++ solution without confusing bit manipulations

1
2
3
bool isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;
}

https://discuss.leetcode.com/topic/42855/o-1-one-line-solution-without-loops

O(1) one-line solution without loops

1
2
3
4
5
public class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
}
}

The basic idea is from power of 2, We can use “n&(n-1) == 0” to determine if n is power of 2. For power of 4, the additional restriction is that in binary form, the only “1” should always located at the odd position. For example, 4^0 = 1, 4^1 = 100, 4^2 = 10000. So we can use “num & 0x55555555==num” to check if “1” is located at the odd position.


https://discuss.leetcode.com/topic/44430/simple-c-o-1-solution-without-0x55555555

Simple C++ O(1) solution without 0x55555555

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return ((num-1)&num)==0 && (num-1)%3==0;
}
};

https://discuss.leetcode.com/topic/43801/simplest-c-solution-maybe

Simplest C++ solution maybe?

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return !(num & (num - 1)) && (num & 0x55555555);
}
};

https://discuss.leetcode.com/topic/45946/c-simple-code-with-comments-no-loops-recursion

C++ simple code with comments (no loops/recursion)

Idea is simple. Powers of four are 1, 4, 16.. or in binary, 0x0001, 0x0100, etc. Only one bit is ever set, and it’s always an odd bit. So simply check for that…

This does not use any loops or recursion, is O(1) time and O(1) space.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
bool isPowerOfFour(int num) {
// first check only one bit is set:
if ((num & (num -1)) != 0) return false;
// next check if it's a bit in pos 1, 3, 5 ... 31
if (num & 0x55555555) return true;
return false;
}
};

https://discuss.leetcode.com/topic/42865/python-one-line-solution-with-explanations

Python one line solution with explanations

1
2
def isPowerOfFour(self, num):
return num != 0 and num &(num-1) == 0 and num & 1431655765== num

Consider the valid numbers within 32 bit, and turn them into binary form, they are:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
100
10000
1000000
100000000
10000000000
1000000000000
100000000000000
10000000000000000
1000000000000000000
100000000000000000000
10000000000000000000000
1000000000000000000000000
100000000000000000000000000
10000000000000000000000000000
1000000000000000000000000000000

Any other number not it the list should be considered as invalid.
So if you XOR them altogether, you will get a mask value, which is:

1
1010101010101010101010101010101 (1431655765)

Any number which is power of 4, it should be power of 2, I use num &(num-1) == 0 to make sure of that.
Obviously 0 is not power of 4, I have to check it.
and finally I need to check that if the number ‘AND’ the mask value is itself, to make sure it’s in the list above.

here comes the final code:

return num != 0 and num &(num-1) == 0 and num & 1431655765== num

谢谢你,可爱的朋友。