基本的位操作：
| --->或操作
&--->与操作
^---->异或操作
~--->取反
<<-->左移
>>-->右移
题1：在一个序列中，只有一个数出现奇数次，请你找出这个数。
解：arr[5]={1,1,2,2,3}
1^1=0 2^2=0
所以：1^1^2^2^3=3 ok，搞定
//1.在arr中,只有一种数，出现奇数次,找出这个数 void printOddTimesNum(int arr[],int len){ int eor = 0; for(int i=0;i<len;i++){ eor = eor^arr[i]; } printf("唯一的那个奇数为:%d\n",eor); }
题2：在一个需要序列中，有两种数出现奇数次，求出这两个数。
解：arr[6]={1,1,2,2,3,4}
eor = 1^1^2^2^3^4=3^4
然后将eor的二进制中的最右边的为1的取出来。
eor & (~eor+1)
为什么这样做呢？因为我们知道异或操作是，不同为1，则说明在这一位二进制数的状况，这两个奇数是不同的。eor=3^4=0011^0100=0111
0111-->1000-->1001-->1001&0111=0001
如此以来，我们就可以将这个序列中的数分为两堆，一堆是这个位上是1的，一堆是这个位上不是1
那么，3和4肯定是在不同的堆中的。
1、1、3和2、2、4-->我们就可以求出这两个数了，跟只有一个数出现奇数次的情况一样
//arr中,有两种数,出现的奇数次,找出这两个数 void printOddTimesNum2(int arr[],int len){ int eor = 0; //找到那两个出现奇数次异或的结果 for(int i=0;i<len;i++){ eor = eor^arr[i]; } //取出eor中的二进制的最右边的1-->这样我们可以把数组分为第i位上是1的和第i位上不是1的 int tmp = eor & (~eor+1); int numOne = 0; for(int i=0;i<len;i++){ if((tmp & arr[i]) == 1){ numOne = numOne^arr[i]; } } printf("%d,%d\n",numOne,eor^numOne); }
题3：求出整数num的二进制上为1的个数
解：不断地取出num的最右边的1
//取出一个整数的二进制为1的个数 void bitcounts(int num){ int count = 0; while (num != 0) { int rightOne = num & (~num + 1); //取出最右边的1 count++; num = num ^ rightOne; //将最右边的1变成0 } printf("这个整数的二进制为1的个数为:%d\n",count); }
测试代码附上：
#include <iostream> #include <cstdlib> using namespace std; #define MAX_SIZE 100 //1.在arr中,只有一种数，出现奇数次,找出这个数 void printOddTimesNum(int arr[],int len){ int eor = 0; for(int i=0;i<len;i++){ eor = eor^arr[i]; } printf("唯一的那个奇数为:%d\n",eor); } //arr中,有两种数,出现的奇数次,找出这两个数 void printOddTimesNum2(int arr[],int len){ int eor = 0; //找到那两个出现奇数次异或的结果 for(int i=0;i<len;i++){ eor = eor^arr[i]; } //取出eor中的二进制的最右边的1-->这样我们可以把数组分为第i位上是1的和第i位上不是1的 int tmp = eor & (~eor+1); int numOne = 0; for(int i=0;i<len;i++){ if((tmp & arr[i]) == 1){ numOne = numOne^arr[i]; } } printf("%d,%d\n",numOne,eor^numOne); } //取出一个整数的二进制为1的个数 void bitcounts(int num){ int count = 0; while (num != 0) { int rightOne = num & (~num + 1); //取出最右边的1 count++; num = num ^ rightOne; //将最右边的1变成0 } printf("这个整数的二进制为1的个数为:%d\n",count); } int main(){ int len=0; int arr[MAX_SIZE]; printf("长度:"); scanf("%d",&len); printf("序列:"); for(int i=0;i<len;i++){ scanf("%d",&arr[i]); } //测试1 printOddTimesNum(arr,len); //测试2 printOddTimesNum2(arr,len); //测试3 5-->00000101 bitcounts(5); system("pause"); return 0; }
