判断一个整数的二进制中1的个数

无意间看到这个题目，最先想到是将整数转换成二进制，然后再统计这个二进制中有多少个1。对于php而言，这很容易实现，转成二进制可用decbin()这个函数，然后将二进制数按1位进行分割用str_split()，最后对分割后的数值进行foreach即可完成数据的统计，实际上这是最low的解决方案，网上大多数使用下面的算法进行求解，觉得很巧妙，于是就mark了！

算法说明

设x的二进制位表示为
x=a_(n-1) a_(n-2)…a₀

按从低位到高位的顺序，不失一般性，假设x的第i位为第一个为1的二进制位，即：a_i = 1
此时有：
x = a_(n-1) a_(n-2) … a_(i+1) 1 0 0 … 0 （式1)
x-1= a_(n-1)a_(n-2) …a_(i+1) 0 1 1 … 1 （式2)
很明显，从式1和式2可以得出，在第一次 x & (x-1) 后：
x = a_(n-1) a_(n-2) … a_(i+1) 0 0 0 … 0

之后重复同样操作，直到x的二进制位中没有1为止，从上面可以看出，每执行过一次 x & (x-1) 后，都会将x的二进制位中为1的最低位的值变为0，并记数加1。目前而言，一个整数最大64bit，所有三种方法执行起来都可以认为是O(1)。

代码实现

<?php
$number = $argv[1];
$counter = 0;
while ($number)
{
    $counter += 1;
    $number = $number & ($number-1);

}

echo $counter . PHP_EOL;