2 的幂【简单】

231. 2 的幂

https://leetcode-cn.com/problems/power-of-two/

题目描述

给你一个整数 n，请你判断该整数是否是 2 的幂次方。

  • 如果是，返回 true ；
  • 否则，返回 false 。

如果存在一个整数 $x$ 使得 $n = 2^{x}$ ，则认为 $n$ 是 2 的幂次方。

输入：n = 1

输出：true

解释：$2^{0}=1$

输入：n = 8

输出：true

解释：$2^{3}=8$

输入：n = 5

输出：false

题解

位运算 参考题解：

若 $n = 2^{x}$ 且 $x$ 为自然数（即 $n$ 为 2 的幂），则一定满足一下条件：

  • 恒有 n & (n-1) == 0（& 表示与运算，两位同时为“1”，结果才为“1”，否则为 0）
  • 一定满足 n>0

因为 $n$ 二进制最高位为 1，其余所有位为 0；$n−1$ 二进制最高位为 0，其余所有位为 1

2x n n-1 n & (n-1)
20 0001 0000 0
21 0010 0001 0
22 0100 0011 0
… … … … 
1
2
3
4
5
6
7
def isPowerOfTwo(n):
    return n > 0 and n & (n - 1) == 0


if __name__ == '__main__':
    print(isPowerOfTwo(8))  # True
    print(isPowerOfTwo(19)) # False

4 的幂 【简单】

342. 4 的幂

https://leetcode-cn.com/problems/power-of-two/

题目描述

题目类似于 2 的幂。给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true；否则，返回 false 。

题解

如果 $n$ 是 4 的幂，那么 $n$ 一定也是 2 的幂。因此我们可以首先判断 $n$ 是否是 2 的幂，在此基础上再判断 $n$ 是否是 4 的幂。

如果 $n$ 是 4 的幂，那么 $n$ 的二进制表示中有且仅有一个 1 ，并且这个 1 出现在从低位开始的第偶数个二进制位上。

我们可以构造一个整数 $mask$，使它的所有偶数二进制位都是 0，所有奇数二进制位都是 1。我们将 $n$ 和 $mask$ 进行按位与运算，如果结果为 0，说明 $n$ 二进制表示中的 1 出现在偶数的位置，否则说明其出现在奇数的位置。

1
2
3
4
5
6
7
8
def isPowerOfFour(n):
    return n > 0 and n & (n - 1) == 0 and (n & 0xaaaaaaaa) == 0


if __name__ == '__main__':
    print(isPowerOfFour(4))  # True
    print(isPowerOfFour(16))  # True
    print(isPowerOfFour(19))  # False

位 1 的个数【简单】

191. 位1的个数

https://leetcode-cn.com/problems/number-of-1-bits/

题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

输入：00000000000000000000000000001011

输出：3

输入：00000000000000000000000010000000

输出：1

输入：11111111111111111111111111111101

输出：31

字符串题解

1
2
3
4
5
# python 骚操作
def hammingWeight(n):
    # bin() 返回一个整数 int 或者长整数 long int 的二进制表示。
    # print(bin(n))
    return bin(n).count('1')

位运算题解

在 Java 中 Integer.bitCount() 方法用于统计二进制中 1 的个数，其源码如下

1
2
3
4
5
6
7
8
9
public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}
  • >>> 表示无符号右移
  • & 与运算，当两位同时为“1”，结果才为“1”，否则为 0

代码中的十六进制数的二进制表示如下：

原文 二进制
0x55555555 01010101 01010101 01010101 01010101
0x33333333 00110011 00110011 00110011 00110011
0x0f0f0f0f 00001111 00001111 00001111 00001111
0x3f 00000000 00000000 00000000 11111111

如果把这些二进制序列看作一个循环的周期序列的话，那么：

  • 第一个序列的周期是 2，每个周期是 01；
  • 第二个序列的周期是 4，每个周期是 0011；
  • 第三个序列的周期是 8，每个周期是 00001111；
  • 第四个序列的周期是 16，每个周期是 11111111。

原理是：先两个两个一组，求二进制 1 的个数，并且用两位二进制存储在原处，然后四个四个一组，求二进制位 1 的个数，再把它存储以 4 位二进制到原处。以此类推直到计算完成。

算法原型：

1
2
3
4
5
6
7
8
public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

767 的二进制中的 1 的位数计算过程：

1
2
3
4
5
6
7
8
9
          二进制                       十进制
1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
 01     10     10     10     10       1 2  2  2  2
         \     /       \     /           \/    \/
 01       0100           0100         1   4    4
               \       /                   \  /
 01               1000                1      8
     \          /                       \   /
         1001                             9

如果以 0b11111111 为例可以看到每一步的变化

  • i = i - ((i >>> 1) & 0x55555555); 运算完后 i = 0b10101010 。
  • i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 运算完后 i = 0b01000100。
  • i = (i + (i >>> 4)) & 0x0f0f0f0f; 运算完后 i = 0b00001000。
  • i = i + (i >>> 8); 运算完后 i = 0b00001000。
  • i = i + (i >>> 16); 运算完后 i = 0b00001000。
  • i & 0x3f 返回 0b00001000 等于 8