刷题

二进制中 1 的个数

scorlw 发布于

二进制中 1 的个数

关键词：位运算

题目描述

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例2：

1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

思路

思路一：

按位判断

这是最直观的方式，依次判断整数的每一位是否为 1 。

判断第 1 位：n & 1

判断第 2 位：n & (1 << 1)

……

判断第32位：n & (1 << 31)

思路二：

N & (N - 1)

使用这个方法，基于这样一个事实：

一个数 n 与一个比它小 1 的数（n−1）进行与运算（&）之后，得到的结果会消除 n 中最低位的 1.

我们看两个例子：

1
2
3
4
5
6
7
8
9
示例1: 7 & 6
00111
      &   =》 00110
00110

示例2: 8 & 7
01000
      &   =》 00000
00111

可以看到，n&(n−1) 得到的结果，就是将 n 最低位 1，换成 0 之后的值。

根据这个，编码思路就是，每次都使用该运算法则消去 1 ，每运算一次计数器 +1，直至 n 为 0 .

代码

思路一：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        for (int i = 0; i < 32; i ++) {
            if (n & (1 << i)) {
                ret ++;
            }
        }
        return ret;
    }
};

思路二：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n != 0) {
            n &= n-1;
            ret ++;
        }
        return ret;
    }
};

知识点

  1. 位运算