位运算的相关题型

xiaoxiao2021-02-28  105

位运算是把数字用二进制表示之后,堆每一位上0或者1的运算。

1.请实现一个函数,输入一个整数,输入该数的二进制表示中1的个数;

解法一:

一个整数有32个二进制位,只需要对这32位的每一位判断是否为1来统计其中一个个数;

如何判断每一位呢?看下面这个过程,用八位来模拟;

第一位:0000 1010  & 0000 0001  = 0000 0000  ;   结果为零,表示该二进制位是0;

第二位:0000 1010  & 0000 0010 =  0000 0010;结果不为0,表示该二进制位是1;

...

依次判断至结束;

int NumberOf1(int num) { unsigned int flag = 1; int count = 0; for (int i = 0; i < 32; i++) { if ((num & flag)) { count++; } flag = flag << 1; } return count; }上面的方法不管是几个1,1在高位还是低位都需要循环32次,下面这个解法就有效的减少了循环次数;

解法二:

说这个解法之前,先来个预备知识,一个数减去1,相当于最低位是1的这一位取反,以这位为分隔符,左边不变,右边的都变为1;比如:10 - 1 == 1010 - 1  等于1001;

9 - 1 == 1001 -1 等于 1000;由此可以总结:一个数减去1,都是把最右边的1变为0,如果它右边患有0的话,所有的0变为1;而它左边的所有位保持不变;

我们把一整数和这个整数减去1的结果做与运算,10 & (10 - 1)== 1010 & 1001 等于 1000;相当与这个整数二进制位中1的个数减少1个;

解法二的思路就是,把一个整数和这个整数减去1之后的结果相与,每次减少1个1,直到结果为零,与了多少次,就有多少个1;

int NumberOf1(int num) { int count = 0; while (num) //一个数&(这个数 - 1),相当于减少一个二进制中的1; { count++; num = num & (num - 1); } return count; }2.用一条语句判断一个整数是不是2的整数次方?

先来普及一条知识点:一个整数如果是2的整数次方,那么它的二进制表示中有且只有一位是1;

下来解出这个问题是不是 so easy,直接利用上一题解法二的思路判读1的个数是不是1个就可以了;

bool Check2(int n) { return (n & n - 1) ? false : true; }

转载请注明原文地址: https://www.6miu.com/read-69364.html

最新回复(0)