Ex15 二进制中1的个数

题目描述

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

解题思路

参考《剑指Offer》上的解法，以下皆讨论二进制的位和数。

1. 将一个不等于0的数减去1，则有以下两种情况：

• 当这个数的最右边是1的时候，最右边的位置为0，其它的位保持不变。以1011为例，1011-1=1010。
• 当这个数的最右边不是1，而最低为1的位置为0，其左边保持不变，其右边变为全1。以10100为例，10100-1=10011。

1. 将一个数减去1并与这个数相与，则将其最低位1的位及其右边皆置为0。以10100为例，10100&(10100-1)=10100&10011=10000。

综上所述，把一个数减去1，再和原来的数相与，就将这个数的最右边的1置为0。一个数的二进制中有多少个1，就可以进行多少次这样的运算。

代码

int
hammingWeight (uint32_t n)
{
  int weight = 0;
  while (n)
    {
      ++weight;
      n = (n - 1) & n;
    }
  return weight;
}

结果

执行结果：显示详情

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.3 MB, 在所有 C 提交中击败了14.40%的用户

备注

依然不懂LeetCode上的内存消耗时如何得到的。