计算在一个 32 位的整数的二进制表示中有多少个
1
.
样例
给定
32
(100000),返回1
给定5
(101),返回2
给定1023
(1111111111),返回10
挑战
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
知识点
x & (x - 1) 可以消去二进制最右侧的 1
代码
public class Solution {
/*
* @param num: An integer
* @return: An integer
*/
public int countOnes(int num) {
// 负数以补码形式存在,对于负数此算法也适用
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
}
错误代码
public class Solution {
/*
* @param num: An integer
* @return: An integer
*/
public int countOnes(int num) {
int count = 0;
// 这么写 num 没更新
while (num & (num - 1) != 0) {
count++
return count;
}
};
网友评论