欢迎光临
我们一直在努力

LeetCode 191. 位1的个数(Hamming Weight)——三种解法详解(C语言)

一、题目描述

给定一个正整数 n,编写一个函数,返回该整数的二进制表示中 1 的个数,也称为 汉明重量(Hamming Weight)。

示例:

示例1:
输入:n = 11
输出:3
解释:二进制为 1011,共有 3 个 1

示例2:
输入:n = 128
输出:1
解释:二进制为 10000000

示例3:
输入:n = 2147483645
输出:30

提示:

1 <= n <= 2^31 – 1


二、解题思路

题目的核心就是:

统计一个整数的二进制中有多少个 1。

常见解法主要有三种:

  • 逐位判断法

  • Brian Kernighan 位运算法(最经典)

  • 查表法(多次调用最优)

  • 下面分别进行讲解。


    三、解法一:逐位判断法

    思路

    通过位运算不断检查整数的 最低位。

    判断方法:

    n & 1

    含义:

    • 如果结果为 1,说明最低位是 1

    • 如果结果为 0,说明最低位是 0

    然后将 n 右移一位:

    n >> 1

    不断重复这个过程,直到 n == 0。


    示例演示

    n = 11

    二进制:1011

    1011 -> 1
    0101 -> 1
    0010 -> 0
    0001 -> 1
    0000 -> 结束

    统计得到:

    1 的个数 = 3


    C语言代码实现

    int hammingWeight(int n) {
    int count = 0;

    while(n) {
    if(n & 1) {
    count++;
    }
    n = n >> 1;
    }

    return count;
    }


    复杂度分析

    时间复杂度:

    O(32)

    因为一个整数最多只有 32 位。

    空间复杂度:

    O(1)


    四、解法二:Brian Kernighan 算法(推荐)

    这是 位运算中的经典技巧,在面试中非常常见。

    核心公式

    n & (n – 1)

    作用:

    删除二进制中最右侧的一个 1


    举例说明

    n = 101100

    n – 1 = 101011

    n & (n – 1)

    101100
    &101011
    ——-
    101000

    可以看到:

    最右边的1被消掉了


    算法思路

    每执行一次:

    n = n & (n – 1)

    就会消除一个 1。

    因此:

    循环次数 = 二进制中1的个数


    C语言实现

    int hammingWeight(int n) {
    int count = 0;

    while(n) {
    n = n & (n – 1);
    count++;
    }

    return count;
    }


    复杂度分析

    时间复杂度:

    O(k)

    其中:

    k = 二进制中1的数量

    最坏情况下:

    k = 32

    但在实际情况中通常 远小于 32,因此效率更高。


    五、解法三:查表法(适合多次调用)

    如果这个函数 需要被频繁调用,可以采用 查表法 来提高效率。

    思路

    一个整数共有 32 位,可以拆成 4 个字节:

    8 + 8 + 8 + 8

    我们可以提前计算:

    0 ~ 255 每个数字的1的个数

    存入数组中。

    这样就可以通过查表快速得到结果。


    C语言实现

    int table[256];

    void init() {
    for(int i = 0; i < 256; i++) {
    int count = 0;
    int x = i;

    while(x) {
    x &= (x – 1);
    count++;
    }

    table[i] = count;
    }
    }

    int hammingWeight(int n) {
    return table[n & 0xff] +
    table[(n >> 8) & 0xff] +
    table[(n >> 16) & 0xff] +
    table[(n >> 24) & 0xff];
    }


    复杂度分析

    时间复杂度:

    O(1)

    空间复杂度:

    O(256)

    适合 需要频繁调用函数的场景。


    六、三种解法对比

    方法思路时间复杂度推荐程度
    逐位判断 每次判断最低位 O(32) ⭐⭐⭐
    Kernighan算法 每次消除一个1 O(k) ⭐⭐⭐⭐⭐
    查表法 预处理查表 O(1) ⭐⭐⭐⭐

    面试中最推荐:

    Brian Kernighan 算法

    原因:

    • 代码简洁

    • 时间复杂度优秀

    • 位运算经典技巧


    七、位运算经典技巧总结

    1️⃣ 判断最低位

    n & 1

    2️⃣ 右移一位

    n >> 1

    3️⃣ 删除最低位的 1

    n & (n – 1)

    这个技巧非常重要,经常用于:

    • LeetCode 191 位1的个数

    • LeetCode 231 2的幂

    • LeetCode 338 比特位计数

    • LeetCode 136 只出现一次的数字


    八、总结

    本题的关键是理解 二进制位运算。

    推荐掌握的核心技巧:

    n & (n – 1)

    它可以 快速删除二进制中最右侧的1,是位运算中最经典的技巧之一。

    在实际面试中,这种写法往往是 最优解法。

    赞(0)
    未经允许不得转载:171主机测评 » LeetCode 191. 位1的个数(Hamming Weight)——三种解法详解(C语言)
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址