可以每次右移一位遍历统计,也可以用n & (n - 1) 快速将最低位的1消去,统计消去所有1所需的次数,即为1的个数。
原理:设n的最低位1为第i位,那么n肯定是这样的形式...10...0(i - 1个0),那么n - 1的形式为...01...1(i - 1个1),可以看出n与n - 1最低i位都互不相同,那么n & (n - 1) 的最低i位全部为0,这样就相当于消去了n的最低位1。
class Solution { public: int NumberOf1(int n) { int res = 0; while (n) { res++; n &= (n - 1); } return res; } };