【2种解法】【JavaScript题解】【剑指offer】

题目描述

输入一个整数,输出该数二进制表示中 1 的个数。其中负数用补码表示。

专注前端与算法的系列干货分享,欢迎关注(¬‿¬):
「微信公众号:心谭博客」| xxoo521.com | GitHub

解法 1: 判断每一位

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

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

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

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

// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/
// ac地址:https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8

/**
 * @param {number} n
 * @return {number}
 */
function NumberOf1(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

// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/
// ac地址:https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8

/**
 * @param {number} n
 * @return {number}
 */
function NumberOf1(n) {
    let count = 0;

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

    return count;
}