2019-04-08
2019-04-08 本文已影响0人
ruicore
LeetCode 342. Power of Four.jpg
LeetCode 342. Power of Four
Description
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example 1:
Input: 16
Output: true
Example 2:
Input: 5
Output: false
Follow up: Could you solve it without loops/recursion?
描述
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
示例 1:
输入: 16
输出: true
示例 2:
输入: 5
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
思路
- 一个数若是 4 的幂次方，那么这个数的二进制表示只有 1 一个 1。
- 并且这个数的1 出现在（从右往左） 第 1，或 3，或 5 ，或 7 ... 位。
- 一个数 num 只有一个 1 那么，num 和 num -1 与运算结果为 0。
- 1 出现在奇数位，那么此数与 1010101010101010101010101010101 与运算为 num 本身。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-04-08 16:58:04
# @Last Modified by: 何睿
# @Last Modified time: 2019-04-08 17:11:49
class Solution:
def isPowerOfFour(self, num: 'int') -> 'bool':
# num 数字不为零
# num 的二级制只有一个 1
# num 中 1 的位置出现在第 1 位，或第 3 位，或第5 ... 位
return num != 0 and num & (
num - 1) == 0 and num & 0b1010101010101010101010101010101 == num
