位 1 的个数
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 56 ms, 内存: 14.9 MB
/*
* This solution uses Java Streams to count the number of '1' bits in a 32-bit integer.
* First, the integer is converted to a binary string. Then, we filter the characters to count only '1's.
* The result is the number of '1' bits.
*/
import java.util.stream.Collectors;
public class Solution {
public long hammingWeight(int n) {
// Convert to binary string and count '1's
return Integer.toBinaryString(n).chars()
.filter(ch -> ch == '1')
.count();
}
}
解释
方法:
这个题解使用了一种称为'位操作的技巧'来计算二进制中1的个数。核心思想是使用一个循环,每次循环中使用n &= n - 1的操作,该操作将n的二进制表示中最低位的1变为0。这是因为从二进制的角度来看,n - 1操作会将最低位的1变为0,并将所有更低位的0变为1。因此,当n和n - 1进行AND操作时,就会抹去最低位的1。循环每执行一次,就计数一次,直到n变为0为止。
时间复杂度:
O(k),其中k是数字n中1的数量
空间复杂度:
O(1)
代码细节讲解
🦆
请问 `n &= n - 1` 操作为什么能有效地去除 n 的最低位的 1?能否用一个具体的例子说明这个操作的过程?
▷🦆
在代码中,循环的终止条件是 `while n:`。对于不同的编程语言,是否有可能因为整数表示的差异(比如有符号和无符号)影响循环的执行?
▷🦆
在题解中,您提到了在最坏的情况下循环将执行32次。这是否意味着该方法对于更长的二进制数(例如64位)不是很高效?
▷🦆
对于非常大的输入值,比如接近整数类型上限的数,这种方法在实际应用中的表现如何?会有什么潜在的性能问题吗?
▷