231.2的幂

发表于 更新于 分类于 ，

题目

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

1
2
3
输入: 1
输出: true
解释: 20 = 1

示例 2:

1
2
3
输入: 16
输出: true
解释: 24 = 16

示例 3:

1
2
输入: 218
输出: false

思路

这一题可真是个神仙题目,如果会解那就非常简洁,如果不会解那就得暴力判断.

一个神奇而优雅的解法是,由于2的幂次方(1,2,4,8...)的二进制数都有一个奇特的特点:

1 : 0001 , 0 : 0000 2 : 0010 , 1 : 0001 4 : 0100 , 3 : 0011 8 : 1000 , 7 : 0111

他们都只有一位为1,并且他们减去一之后都只有一位为0.

所以将他们相与,结果刚好就为0.

代码

1
2
3
4
public bool IsPowerOfTwo(int n)
{
    return n > 0 && (n & (n - 1)) == 0;//n与n-1相与,每一个0和1相与结果都为0.
}