编程之美——求二进制数中1的个数

文中讲了五种方法：
1. 循环利用除法和模运算。该方法最容易想到。可谓没有技术含量的。
2. 循环利用位移和按位与。用位操作代替算术运算，提高效率。
3. 只考虑数字中的1。有经验规律知：对于2的方幂N与N-1取与为0.因而，可以利用该规律想法怎么把原数字变为0，经过的步数就是1的个数。如果没有相应的经验或常识，该方法不容易想到。
4. 利用分支操作。该方法速度并不快。但提供了一个思路：利用空间换时间。
5. 查表法。把1到255的情况罗列到一个数组内，然后通过查表一次就能得到结果。如果有了空间换时间的思想，这个方法是容易想到的。

该问题的两个习题解答：
1.对于32位数，我会选择查表法与只考虑数字中的1的方法。把两种方法结合。
算法的主体代码如下：
int count(int v)
{
     int i, num, p, q;
     p = v;
     for(num = 0, i = 0; i < 4; i++)
     {
         q = p & 0XFF)
         num + = countTable[q];
         p >>= 8;
     }
     return num;
}
注：该方法可以扩展为处理任意位数的变量，其中count为变量的位数，代码改变如下：
int count(int v, int count)
{
     int i, num, p, q, byteCount;
     p = v;
     byteCount = (count + 7) / 8;
     for(num = 0, i = 0; i < byteCount; i++)
     {
         q = p & 0XFF)
         num + = countTable[q];
         p >>= 8;
     }
     return num;
}
2. 把A变成B需要改变多少位？这个问题我是看的别人的答案。意思是问题转化成找出A和B不同的位数。而A和B不同的位数可以用异或运算得到。这样就转化成求一个数中1的个数的问题，即本文的提出的问题上了。通过这个问题，使我想到做学问一定要心静，宁静致远啊！

补充：Web开发 , 其他 ,