某数二进制中包含1的个数计算

这是一个来自社区的题目，表述如下：

实现一个函数countOne，计算给定的参数数值（自然数）的二进制包含“1”的个数，如：

• countOne(10) => 2
• countOne(16) => 1
• countOne(3) => 2

如果不让使用 Number.prototype.toString 又该如何实现呢？

丢到公司技术群里沉没了，周末了自己来写下思考过程，实际上自己思考过程中不会这么顺利，写这篇文章只是为了梳理对比自己思考的过程，所谓：思考思考的过程。能帮助自己之后碰到一些问题能快速的切中要点而得出解法。

分割线

捷径

以10进制的27为例，二进制形式为： 11011，我们肉眼可以很快得出含有四个1，那么如何让计算机数出来呢？
当然，最容易想到的就是：

num.toString(2).replace(/0/g,"").length

当不让使用Number.prototype.toString的时候，我们依然最先想到的自己实现一个十进制转二进制的函数。然后按上面的方法来计算1的个数.

那么有没有更好的方式呢？

分析

我们分析下11011这个二进制数，如何一个个数1呢？试想一下，如果我们能通过某种方式一次性去掉一个1，直到这个数最终变为0，我们统计消除1的次数不就好了嘛？

我们先复习下几个位运算符：

1. 与运算 &

• 1 & 0 => 0
• 1 & 1 => 1
• 0 & 0 => 0

2. 或运算 |

• 1 | 0 => 1
• 1 | 1 => 1
• 0 | 0 => 0

3. 异或运算 ^

• 1 ^ 0 => 1
• 1 ^ 1 => 0
• 0 ^ 0 => 0

眼尖的小伙伴已经注意到上面的每种位运算符的三种运算情况，只有两个符合我们的需求（成功把前面的1变成了0）：

1 & 0   // 0
1 ^ 1  // 0

尝试

我们注意力重新回到11011这个二进制数上来，我们需要挑一个怎样的数字来应用上面的两种运算符号与11011做运算从而消除一个1呢？

1. 先分析异或运算

1.1 如果我们要消除第一个1

`11011` ^ X   => `01011`    (注意是二进制运算，不是十进制的11011)

我们很容易可以写出X应该为：10000

1.2 同理，我们要消除最后一个1

`11011` ^ X  => `11010`

依然很容易得出X应该为：00001 （为了方便你肉眼对齐验证，估计补了4个0）

无论我们是为了从前到后消除1而需要的二进制数10000,还是为了从后到前消除1而得到的二进制数1都与我们原来的数11011好像并没有什么明显的关联。

注意，我这里用了明显二字，而你要分析的话，还是有那么些规律的，比如我们多换几个数：

从左至右消1的那个数与原数还是有关系的，那么我们的问题就会变为如何从诸如11011得到10000的问题了，其实也不难，但总归是麻烦的，我们不妨先按同样的套路分析下与运算，看看会不会更简单。

2.与运算分析

2.1 如果我们要消除第一个1

`11011` &  X   => `01011` 

我们很容易可以写出X应该为：01011或01111

2.2 同理，如果我们要消除最后一个1

`11011` & X  => `11010`

依然很容易得出X应该为：11010 或 11110

眼尖的小伙伴应该已经发现了，要通过与运算消除最后一个1用到的数11010与原数11011不是亲兄弟嘛（原数减1）。

我们用这个规律多验证下试试：

`11010` & `11001` => `11000`
`11000` & `10111` => `10000`
`1000` & `0111` => `0000`

再试下：

`1110010` & `1110001` => `1110000`
`1110000` & `1101111` => `1100000`
`1100000` & `1011111` => `1000000`
`1000000` & `0111111` => `0000000`

是不是完美？

Coding

function countOne(num){
  let count = num > 0 ? 1 : 0
  while(num = num & (num - 1))count++
  return count
}

真正诠释了分析一大堆，代码两三行。其实无论是解决实际问题，还是做题，真正有意思的是过程，分析的过程，而非这个结果。