剑指offer - 二进制中1的个数 - JavaScript

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

题目描述

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

解法 1: 判断每一位

依次判断数字的每一位,统计其中 1 的数量。整体思路如下:

  • 数字先和 1 相与,结果为 0 说明该位是 0,结果为 1 说明该位是 1
  • 将 1 左移一位,再和数字相与。这次判断的是倒数第二位是否位 1
  • 将 1 总共左移 32 次(因为数字底层是 32 位),统计总数即可

注意:尽量规避让原数字右移动,有符号位的问题,可能会陷入死循环。尽量采取左移而不是右移

时间复杂度 O(1), 空间复杂度 O(1)。代码如下:

// ac地址:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/

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

        flag = flag << 1;
    }

    return count;
};

解法 2: n & (n - 1)

解法 2 采用n & (n - 1)的做法,这种做法的可行原因是:能将数字 n 的二进制表示中,最右边的 1 变成 0

举个例子,以 5 为例,其二进制是 101:

  • 101 & 100 => 100
  • 100 & 011 => 0

因此,整体思路是:

  • n 和 n-1 相与的结果赋给 n
  • n 如果为 0,结束;否则回到第 1 步

和解法 1 相比,空间复杂度是 O(1),但是解法 1 一定需要循环 32 次,但是解法 2 的循环次数就是数字中 1 的个数,优于解法 1

// ac地址:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;

    while (n) {
        n = n & (n - 1);
        ++count;
    }

    return count;
};

更多资料

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×