二进制1的个数

最简单的方式

1
const n = num => num.toString(2).replace(/0/g, '').length

就只有这样？

一个数N的二进制和（N-1）的二进制做与运算的到的结果总比N少一个1
根据这个原理我们可以让 N 和 N-1 做与运算得到新的值 M（二进制M 1 的个数比 N 中 1的个数少一个） 再和 M-1 做与运算，重复直到得到的值为0。（最终所有的1都会被与掉）

1
2
3
4
5
6
7
8
9
// 计算一个数的二进制中1的个数
const n = (num) => {
    let count = 0;
    while (num) {
        num &= num - 1;
        count ++;
    }
    return count;
}

进入一个常见的算法问题。

延伸一个问题：从一个数组中找出N个数，使它的的和为M的所有可能。

首先这个问题如果是N=1，就是直接查找。如果N=2就是每次选好一个数再和其它数累加。但是随着N越来越大简单的循环累计将变得极其复杂。

解法：

  • 首先数组长度为len的数组从中选取N（0-len）个数的全排列是有限的。