Anoyer
剑指Offer（十一）：二进制中1的个数输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
思路一： 利用lowbit函数作用每次计算出n的最低位1的位权，这样可以在$log(n)$次计算内
class Solution {
public:
int NumberOf1(int n) {
int cnt=0;
while(n){
++cnt;
n-=(n)&(-n);
}
return cnt;
}
};思路二： $O(1)$玄学计算
class Solution {
public:
int NumberOf1(uint32_t n) {
uint32_t tmp=n - ((n>>1) &033333333333)-((n>>2) &011111111111);
return((tmp+(tmp>>3)) &030707070707) %63;
}
};输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
思路一： 利用lowbit函数作用每次计算出n的最低位1的位权，这样可以在$log(n)$次计算内
class Solution {
public:
int NumberOf1(int n) {
int cnt=0;
while(n){
++cnt;
n-=(n)&(-n);
}
return cnt;
}
};思路二： $O(1)$玄学计算
class Solution {
public:
int NumberOf1(uint32_t n) {
uint32_t tmp=n - ((n>>1) &033333333333)-((n>>2) &011111111111);
return((tmp+(tmp>>3)) &030707070707) %63;
}
};