韩槑槑

剑指offer 二进制中1的个数

字数统计: 208阅读时长: 1 min
2019/01/07 Share

题目

解法一

1
2
3
4
5
6
7
8
9
10
// 在按位与当中
0 & 1 = 0
0 & 0 = 0
1 & 1 = 1

88 = 0101 1000

66 = 0100 0010

& = 0100 0000

由此题可设 m = 1 (0000 0001),则

1
n & m = 1 或 0(取决于 n 的最后一位是 1 还是 0)

判断结果并记数 count
接着将 n 向左位移 n << 1 = 0000 0010,此时

1
n & m = 1 或 0(取决于 n 的倒数第二位是 1 还是 0)

依次类推,判断 m 的每一位是否为 1

解法二

假设 n = 88 (0101 1000)
n-1 = 87 (0101 0111)

n - 1 会将 n 二进制最右侧的 1 变为 0, 并将其右侧所有 0 变为 1
此时 (n - 1) & n = 0101 0000,通过上述步骤就将 n 最右侧的 1 给剔除掉了

重复上述步骤直到 n = 0 为止

CATALOG
  1. 1. 题目
  2. 2. 解法一
  3. 3. 解法二