【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;
}