位运算与二进制数中1的个数

ゝ一纸荒年。 2021-11-11 13:44 349阅读 0赞

**位运算**

位运算就是把数字用二进制表示之后，对每一位上的0或1的操作。常用的位运算有5种，分别是与、或、异或、左移和右移。其运算规律如下所示：

左移运算符<<：比如m << n时，最左边的n位将直接被丢弃，同时在最右边补n个0。如：

00001010 << 2 = 00101000

10010010 << 2 = 01001000

右移运算符>>：比如m >> n时，如果m是一个正数，则右移之后在最左边 补n个0；如果m是一个负数，则在最左边补n个1。如：

00001010 >> 2 = 00000010

10010010 >> 2 = 11100100

**二进制数中1****的个数**

题目描述：输入一个整数，输出该数二进制中的1的数目。

思路：先判断整数的二进制表示中最后一位是不是1；接着再把此数右移一位，此时原来处于倒数第二位的数就到了最后一位，然后再判断此时的最后一位数是否为1；这样每次移动一位，直到整数变成0为止。于是，问题就变成了如何判断一个数的最后一位是不是1的问题，即让最后一位数与1做与（&）运算，若结果为1，则说明最后一位是1，反之，则是0。

#include <stdio.h>
 int Count1(int n)
 {
 int count = 0;
 while (n)
 {
 	if (n & 1)
 	{
 		count++;
 	}
 	 n = n >> 1;
 }
 return count;
 }
 int main()
 {
 int n ;
 printf("请输入n：");
 scanf("%d", &n);
 int count = Count1(n);
 printf("%d中有%d个1!\n", n, count);
 return 0;
 }

但是，这样写的话只适合n为正数时的情况，当n为负数时，右移一位，然后最高位补1，然后程序就会陷入死循环。为了避免这种情况，我们可以不用右移输入的数字。首先把n和1做与运算，判断最低位是否为1。接着再把1左移一位变成2，然后在于n做与运算，判断倒数第二位是否为1，如此反复左移，每次都能判断其中一位是否为1。

int Count1(int n)
 {
 unsigned int flag = 1;
 int count = 0;
 while (flag)
 {
 	if (n & flag)
 	{
 	 count++;
 	}
 	flag = flag << 1;
 }
 return count;
 }
 int main()
 {
 int n ;
 printf("请输入n：");
 scanf("%d", &n);
 int count = Count1(n);
 printf("%d中有%d个1!\n", n, count);
 return 0;
 }

在上面这种解法下，循环的次数等于二进制数的位数，32位的整数需要循环32次。还有一种最简单的方法，但不易想到。我们假设一个整数不等于0，那么该整数的二进制表示中至少有一位是1。假设这个数的最右边是1，那么减去1时，最后一位就变成了0，而其他位都保持不变，相当于给最后一位做了取反操作。还有一种情况，假设最后一位不是1而是0的情况。如果该数的二进制表示中最右边的1位于第m位，那么减去1时第m位由1变成0，而第m位之后的所有0都变成1，第m位之前的数都保持不变。例如，一个二进制数1100，最右边的1位于第2位，减去1后，第2位变成0，后面的两位变成1，前面的1保持不变，即1100 – 1 = 1011。在这两种情况下，我们发现把一个整数减去1，都是把最右边的1变成0，如果它的右边还有0，则所有的0都变成1，而它左边的所有位都保持不变，接下来我们把一个整数和它减去1的结果做位与运算，相当于把它最右边的1变成0。以1100为例，它减去1的结果是1011，我们再把1100和1011做位与运算，得到的结果是1000，我们把1100最右边的1变成0，结果也是1000。这种算法总结起来就是：把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0。那么该整数的二进制表示中有多少个1，就进行多少次操作。

int Count1(int n)	
    {
        int count = 0;
        while (n)
        {
    	count++;
    	n = (n - 1) & n;
        }
        return count;
    }
    int main()
    {
        int n ;
        printf("请输入n：");
        scanf("%d", &n);
        int count = Count1(n);
        printf("%d中有%d个1!\n", n, count);
        return 0;
    }

以上即是三种求二进制数中1的个数的方法，各有利弊，，使用时还需慎重。