力扣对应题目链接：191. 位1的个数 - 力扣（LeetCode）
牛客对应题目链接：二进制中1的个数_牛客题霸_牛客网
一、《剑指Offer》内容
核心考点 ：二进制计算。
二、分析问题
1、循环检查二进制位
可以直接循环检查给定数字 n 的二进制的每一位是否为 1，那应该如何遍历二进制每一位呢？
可以考虑移位运算，每次移动一位即可。至于怎么统计到 1 呢？
我们都只知道数字 1 与数字相位与运算，其实只是最后一位为 1 就是 1，最后一位为 0 就是 0，这样我们就只需要将数字 1 移位运算，就可以遍历二进制的每一位，再去做位与运算，结果为 1 的就是二进制中为 1 的。
当检查第 i 位时，我们可以让 n 与 2^i 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。
- 遍历二进制的 32 位，通过移位 0~31 次实现。
- 将移位后的 1 与数字进行位与运算，结果为 1 就记录一次。
2、位运算优化
性质：n&(n−1)，会将 n 的二进制中最低位由 1 变成 0。
观察这个运算：n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。这样我们就可以利用这个位运算的性质加速我们的检查过程，我们不断地让当前的 n 与 n−1 做与运算，直到 n 的二进制位全部变为 0 即可。因为每次运算会使得 n 的最低位的 1 被翻转为 0，因此运算次数就等于 n 的二进制位中 1 的个数。
- 使用循环检查 n 是否为 0。
- 不为 0 就与 n−1 做位与运算，去掉二进制最后一位的 1，并统计次数。
三、代码
1、循环检查二进制位（两种写法）
//牛客AC代码 class Solution { public: int NumberOf1(int n) { int cnt=0; for(int i=0; i<32; i++) { if(((n>>i)&1)==1) cnt++; } return cnt; } }; //力扣AC代码 class Solution { public: int hammingWeight(int n) { int res=0; for(int i=0; i<32; i++) { if((n>>i)&1==1) res++; } return res; } };
//牛客AC代码 class Solution { public: int NumberOf1(int n) { int cnt=0; for(int i=0; i<32; i++) { if((n&(1<<i))!=0) cnt++; } return cnt; } }; //力扣AC代码 class Solution { public: int hammingWeight(int n) { int res=0; for(int i=0; i<32; i++) { if(n&(1<<i)) res++; } return res; } };
2、推荐：方法一（n & (n-1)）
这种方法可以避免无效检测。
//牛客AC代码 class Solution { public: int NumberOf1(int n) { int cnt = 0; while(n) { n &= (n-1); cnt++; } return cnt; } }; //力扣AC代码 class Solution { public: int hammingWeight(int n) { int res=0; while(n) { res++; n&=(n-1); } return res; } };
四、扩展
1、力扣相关题目链接：231. 2 的幂 - 力扣（LeetCode）
（1）分析题目
一个整数如果是 2 的整数次方，那么它的二进制表示中有且只有一位是 1，而其他所有位都是 0。根据前面的分析，把这个整数减去 1 之后再和它自己做与运算，这个整数中唯一的 1 就会变成 0。
（2）代码
class Solution { public: bool isPowerOfTwo(int n) { if(n>0 && (n&(n-1))==0) return true; else return false; } };
2、输入两个整数 m 和 n，计算需要改变 m 的二进制表示中的多少位才能得到 n。
（1）分析题目
比如 10 的二进制表示为 1010，13 的二进制表示为 1101，需要改变 1010 中的 3 位才能得到 1101。可以分为两步来解决这个问题：
- 求这两个数的异或。
- 统计异或结果中 1 的位数。
（2）代码
public class Solution { public int NumberOf1(int m, int n) { int num = m ^ n; int res = 0; while(num) { num = num * (num-1); res++; } return res; } }
五、举一反三
把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个 1 变成 0。很多二进制的问题都可以用这个思路解决。
