15. 二进制中 1 的个数

来源

https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

题目

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

示例:

示例 1.

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2.

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3.

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

思路 1

循环判断 n & 1，如果 n 的二进制是 1 结尾，返回 1，反之，返回 0，
n >>> 1，无符号右移 1 位,
由于有示例 3，js 需要用 >>>。

解题 1

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  let count = 0;
  while (n) {
    count += n & 1;
    n >>>= 1;
  }

  return count;
};

思路 2

循环判断 n & n - 1，消去二进制最右边的 1。

x	y
n	10101000
n-1	10100111
n & n - 1	10100000

时间复杂度 O(M) M 是二进制中 1 的数量

解题 2

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  let count = 0;
  while (n) {
    n &= n - 1;
    count++;
  }

  return count;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch