Skip to content

Latest commit

 

History

History
170 lines (125 loc) · 4.24 KB

191.number-of-1-bits.md

File metadata and controls

170 lines (125 loc) · 4.24 KB
Raw

题目地址(191. 位 1 的个数)

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

题目描述

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

 

示例 1：

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

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

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
 

进阶:
如果多次调用这个函数，你将如何优化你的算法？

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • apple
  • microsoft

思路

这个题目的大意是： 给定一个无符号的整数， 返回其用二进制表式的时候的 1 的个数。

这里用一个 trick， 可以轻松求出。 就是n & (n - 1) 可以消除 n 最后的一个 1 的原理。

为什么能消除最后一个 1， 其实也比较简单，大家自己想一下

这样我们可以不断进行n = n & (n - 1)直到 n === 0 ， 说明没有一个 1 了。 这个时候我们消除了多少1变成一个1都没有了， 就说明n有多少个1了。

关键点解析

  1. n & (n - 1) 可以消除 n 最后的一个 1 的原理 简化操作

  2. bit 运算

代码

语言支持：JS, C++，Python

JavaScript Code:

/*
 * @lc app=leetcode id=191 lang=javascript
 *
 */
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1);
    count++;
  }

  return count;
};

C++ code:

class Solution {
public:
    int hammingWeight(uint32_t v) {
        auto count = 0;
        while (v != 0) {
            v &= (v - 1);
            ++count;
        }
        return count;
    }
};

Python Code:

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

复杂度分析

  • 时间复杂度：$O(logN)$
  • 空间复杂度：$O(N)$

扩展

可以使用位操作来达到目的。例如 8 位的整数 21:

number-of-1-bits

C++ Code：

const uint32_t ODD_BIT_MASK = 0xAAAAAAAA;
const uint32_t EVEN_BIT_MASK = 0x55555555;
const uint32_t ODD_2BIT_MASK = 0xCCCCCCCC;
const uint32_t EVEN_2BIT_MASK = 0x33333333;
const uint32_t ODD_4BIT_MASK = 0xF0F0F0F0;
const uint32_t EVEN_4BIT_MASK = 0x0F0F0F0F;
const uint32_t ODD_8BIT_MASK = 0xFF00FF00;
const uint32_t EVEN_8BIT_MASK = 0x00FF00FF;
const uint32_t ODD_16BIT_MASK = 0xFFFF0000;
const uint32_t EVEN_16BIT_MASK = 0x0000FFFF;

class Solution {
public:

    int hammingWeight(uint32_t v) {
        v = (v & EVEN_BIT_MASK) + ((v & ODD_BIT_MASK) >> 1);
        v = (v & EVEN_2BIT_MASK) + ((v & ODD_2BIT_MASK) >> 2);
        v = (v & EVEN_4BIT_MASK) + ((v & ODD_4BIT_MASK) >> 4);
        v = (v & EVEN_8BIT_MASK) + ((v & ODD_8BIT_MASK) >> 8);
        return (v & EVEN_16BIT_MASK) + ((v & ODD_16BIT_MASK) >> 16);
    }
};

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。