題目：輸入一個(gè)整數(shù)恒水，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)诬滩。其中負(fù)數(shù)用補(bǔ)碼表示凉倚。
練習(xí)地址
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;
}
// 負(fù)數(shù)的最高位是1
return n < 0 ? count + 1 : count;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)渺氧，n是整數(shù)二進(jìn)制的位數(shù)。
- 空間復(fù)雜度：O(1)漂羊。
方法2
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
// 把最右邊的1變成0
n = (n - 1) & n;
}
// 負(fù)數(shù)的最高位是1
return n < 0 ? count + 1 : count;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)驾锰，n是整數(shù)二進(jìn)制出現(xiàn)1的次數(shù)。
- 空間復(fù)雜度：O(1)走越。
