- 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 | Example: |

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 | class Solution { |

其他实现

O(1) one-line solution without loops

1 | public class Solution { |

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 | class Solution { |

1 | class Solution { |

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 | bool isPowerOfFour(int num) { |

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

O(1) one-line solution without loops

1 | public class Solution { |

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 | class Solution { |

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

Simplest C++ solution maybe?

1 | class Solution { |

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 | class Solution { |

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

Python one line solution with explanations

1 | def isPowerOfFour(self, num): |

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

1 | 1 |

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