|
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2。
思路：母语C#的我对位运算确实接触较少，看到这题想的都是先转二进制，然后遍历。
private static int NumberOf1(int n)
{
int count = 0;
int flag = 1;
while (flag!=0)
{
if ((n&flag)!=0)
{
count++;
}
flag =flag<< 1;
}
return count;
}
实际上利用与运算，把数字位flag先等于1，一步步左移一位，检测对应位置是否为1。那么int是32位，flag就要从第1次到第32次计算。
那么作者给出了一套骚操作，又是一套利用数学的方法，其运行次数跟数字中有几个1一致。
先来看看代码：
private static int NumberOf1b(int n)
{
int count = 0;
while (n!=0)
{
++count;
n = (n - 1) & n;
}
return count;
}
一眼看出来，代码的核心是n=(n-1)&n，即n和n-1的与运算再回给n。这是什么意思呢？n-1在二进制中有特殊的一点，假设n=1011，那么n-1=1010,如果n=1100，那么n-1=1011,即如果一个二进制数减去1的话，在表现上，如果n的最后一位是1，则就变成0，如果最靠右的1不是最后一位，则那个1变成0，后面的0变成1。那么n-1对n来说就是对最右边的1开始进行取反操作。那么来一次n&(n-1)，那就会把最右边的1开始全部置0，这个操作跟统计一个十进制数有多少个非零数字一样，n&(n-1)就等于除以10剔除尾数一般。那么一直做n&(n-1)的话，直到n已经变成0之前，做了多少次就说明有几个1。
代码如下：
private static int NumberOf1b(int n)
{
int count = 0;
while (n!=0)
{
++count;
n = (n - 1) & n;
}
return count;
}
心得：这道题需要对二进制很理解，更偏数学。 | 
转播
