题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
练习地址
https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8
https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
方法1
public class Solution {
public int NumberOf1(int n) {
int count = 0, flag = 1;
while (flag > 0) {
if ((n & flag) > 0) {
count++;
}
flag <<= 1;
}
// 负数的最高位是1
return n < 0 ? count + 1 : count;
}
}
复杂度分析
- 时间复杂度：O(n)，n是整数二进制的位数。
- 空间复杂度：O(1)。
方法2
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
// 把最右边的1变成0
n = (n - 1) & n;
}
// 负数的最高位是1
return n < 0 ? count + 1 : count;
}
}
复杂度分析
- 时间复杂度：O(n)，n是整数二进制出现1的次数。
- 空间复杂度：O(1)。
