判断2的幂次数 Power of Two

题目

判断给定的数字是不是二的幂次,如2^02^12^2

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

Input: 16
Output: true
Explanation: 24 = 16

Example 3:

Input: 218
Output: false

思路&题解

题干好简单,但是没有思路,直觉上感觉可以通过位移来比较,二进制与2的幂次真是蜜汁姐妹花。

如果把2的幂次数用二进制表示,会得到下面的数字:

二进制表示

其实十进制,也是这样,任何进制的满位,都是1打头,后面跟0.

然后呢?一下也想不出来,看了下答案,还是通过位运算,结合这个数字的形式规律,如果将他减一位,正好与原数子的二进制表示相反,0变1,1变0.

二进制表示

把这两个数做一个位的与运算,就是0

二进制表示

所以答案就来了:

public boolean isPowerOfTwo(int n) {
    return n >= 1 && (n&(n-1)) == 0;
}

知识点分析

仍然是位运算,&,需要能看出数字的规律,否则即使你想到位运算也想不到答案。

powered by Gitbook© 小文字 更新: 2019-05-05

results matching ""

    No results matching ""