跳至主要內容

191. 位1的个数


191. 位1的个数open in new window

🟢   🔖  位运算 分治  🔗 力扣open in new window LeetCodeopen in new window

题目

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weightopen in new window).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notationopen in new window. Therefore, in Example 3 , the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011

Output: 3

Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000

Output: 1

Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101

Output: 31

Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

  • The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

题目大意

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为 汉明重量)。

解题思路

思路一:循环

可以直接循环检查给定整数 n 的二进制位的每一位是否为 1

当检查第 i 位时,可以让 n2^i 进行 运算,当且仅当 n 的第 i 位为 1 时,运算结果不为 0

复杂度分析

  • 时间复杂度O(k),其中 k=32,一共需要检查 32 位。
  • 空间复杂度O(1),只需要常数的空间保存若干变量。

思路二:位运算

res 初始化为 0,用于存储返回结果。

n > 0 时,循环以下步骤:

  • n & 1 不为 0,则 n 的最后一位为 1res++
  • n >>= 1,将 n 右移一位,准备提取下一个位。

最终返回 res

复杂度分析

  • 时间复杂度O(k),其中 k=32,每次右移一位,一共需要检查 32 位。
  • 空间复杂度O(1),只需要常数的空间保存若干变量。

思路三:位运算

由于 n & (n−1)n 的二进制位中的最低位的 1 变为 0 ,如:6 & (6−1) = 4, 6 = (110)_2, 4 = (100)_2,运算结果 4 即为把 6 的二进制位中的最低位的 1 变为 0 之后的结果。

可以利用这个位运算的性质,不断让当前的 nn - 1 做与运算,直到 n 变为 0 即可。因为每次运算会使得 n 的最低位的 1 被翻转,因此运算次数就等于 n 的二进制位中 1 的个数。

复杂度分析

  • 时间复杂度O(m),其中 mn 的二进制表示中 1 的数量。每次 n &= n - 1 操作都会消除 n 中的一个 1,因此循环的次数等于 1 的个数。最坏情况下,当 n 的所有位都是 1 时,循环次数等于 m
  • 空间复杂度O(1),只需要常数的空间保存变量。

代码

循环
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
	let res = 0;
	for (let i = 0; i < 32; i++) {
		if (n & (1 << i)) {
			res++;
		}
	}
	return res;
};

相关题目

题号标题题解标签难度
190颠倒二进制位open in new window[✓]位运算 分治
2312 的幂open in new window位运算 递归 数学
338比特位计数open in new window位运算 动态规划
401二进制手表open in new window位运算 回溯
461汉明距离open in new window位运算
693交替位二进制数open in new window位运算
762二进制表示中质数个计算置位open in new window位运算 数学
3280将日期转换为二进制表示open in new window数学 字符串