124.位1的个数
题目
给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
给定一个无符号整数 n，返回其二进制表示中 1 的个数（也叫汉明重量）。
思路
方法一：逐位检查（最直观）
循环 32 次，每次检查最低位是否为 1，然后右移一位。
就像你有一串灯（二进制位），你一个个看过去，亮着的就计数。
步骤： 初始化 count = 0。 循环 32 次（因为整数是 32 位）： 如果 n & 1 == 1，则 count++。 n >>= 1（右移一位）。 返回 count。 方法二：Brian Kernighan 算法（最优）
这个算法的核心是：n & (n-1) 可以消除 n 的最低位的那个 1。
例如：n = 12（二进制 1100），n-1 = 1011，n & (n-1) = 1000，消除了最后一个 1。
重复这个操作，直到 n 变成 0，操作的次数就是 1 的个数。
为什么快？
因为循环次数只等于 1 的个数，而不是固定的 32 次。如果数字中 1 很少，效率很高。
步骤： 初始化 count = 0。 当 n != 0 时： n = n & (n - 1)（消除最低位的 1）。 count++。 返回 count。
class Solution {
// you need treat n as an unsigned value
fun hammingWeight(n: Int): Int {
var num = n
var count = 0
while (num != 0) {
count += num and 1
num = num ushr 1 // 无符号右移
}
return count
}
}
class Solution {
fun hammingWeight(n: Int): Int {
var num = n
var count = 0
while (num != 0) {
num = num and (num - 1) // 消除最低位的 1
count++
}
return count
}
}
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!