0191. 位 1 的个数
题目地址(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了。
关键点解析
n & (n - 1)可以消除n 最后的一个 1 的原理 简化操作bit 运算
代码
语言支持：JS, C++,Python,Java
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 countJava Code:
public class Solution { public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } } return count; }}复杂度分析
时间复杂度：$O(logN)$
空间复杂度：$O(N)$
扩展
可以使用位操作来达到目的。例如 8 位的整数 21:
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 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最后更新于
这有帮助吗？