【剑指offer】二进制中1的个数

考察知识点：位运算

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示

题解一

分析

借助位运算的思想，设立标记变量 flag =1，每次 flag 左移 1位和整数 n 的每一位进行位与，来判断 1 的个数
例如：
对于一个数 1101 ，计数 count = 0
1101 & 0001 = 0001，count +1，
1101 & 0010 = 0000，count 不变，
1101 & 100 = 1000，count +1，
1101 & 1000 = 1000，count + 1
所以 count = 3

代码

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         int flag = 1;
         while(flag!=0){
             if(flag&n){
                 count++;
             }
             flag = flag<<1;
         }
         return count;
     }
};

题解二

分析

例如：
对于一个数 n = 1101 ，n-1 = 1100，计数 count = 0
1101 & 1100 = 1100 = n，count +1，
1100 & 1011 = 1000 = n，count +1，
1000 & 0111 = 0 = n，count +1
所以 count = 3

代码

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n!=0){
             n = (n-1)&n;
             count++;
         }
         return count;
     }
};