您现在的位置是：首页 > 文章详情

C++程序设计基础（7）位运算

日期：2018-06-08点击：414收藏

注：读《程序员面试笔记》笔记总结

1.知识点

运算	符号	说明
与	&	有0为0，都1为1
或	\|	由1为1，都0为0
非（取反）	~	0变1，1变0
异或	^	同为0，异为1
左移	<<	高位移除，低位补零
右移	>>	低位移除，高位补0

1.1异或的性质

1 a^a==0 2 0^a==a 3 a^b^b==b^a^b==a

2.面试题

2.1不使用变量交换两个值

1 //method one 2 a = a - b;//save b message 3 b = a + b;//b= old a 4 a = b - a; 5 //method two 6 a = a ^ b; 7 b = a ^ b;//b= old a 8 a = a ^ b;

提示：利用位的运算性质

2.2计算二进制的1的个数

 1 //method one   2 for ( count = 0; num != 0; num=num >> 1) {  3 if (num & 1) {  4 count++;  5  }  6 }  7 //method two  8 for ( count = 0; num != 0; num &= num - 1) {//每次消掉最后的一个1  9 count++; 10 }

提示：一个数与自身减一后与操作，会消除末尾的1，每次消除一个1

2.3将二进制数倒数第M位的前N位取反(比如M=2，N=4)

（1）将1左移N位（00000001=>00010000）；

（2）将步骤一得到的数减1（00010000=>00001111）；

（3）将步骤二得到的数左移M位（00001111=>00111100）；

（4）得到的数字与原数字进行异或。

1 int getNum(int num, int n, int m) { 2 int res = 1 << n; 3 res--; 4 res = res << m; 5 return res ^ num; 6 }

2.4找出人群中的唯一单身狗（一个数组中唯一一个数出现一次，其余的数都出现过偶数次，求该数）

1 int getSingleDog(int *a, int n) { 2 int res = 0; 3 for (int i = 0; i < n; i++) { 4 res ^= a[i]; 5  } 6 return res; 7 }

提示：异或的性质b^b==0以及交换律

2.5（找出人群中三个单身狗中的任意一个）

 1 #define BITNUM 32  2 int getSingelNum_OneOfThree(int *a, int len) {  3 for (int i = 0; i < BITNUM; i++) {  4 int countOdd = 0, countEven = 0;  5 int resOdd = 0, resEven = 0;  6 int tem = 1 << i;  7  8 for (int j = 0; j < len; j++) {  9 if (tem & a[j]) { 10 countOdd++; 11 resOdd ^= a[j]; 12  } 13 else { 14 countEven++; 15 resEven ^= a[j]; 16  } 17  } 18 19 if (countOdd & 1 && resEven)//一组个数为奇数，另一组异或值不为零 20 return resOdd; 21 if (countEven & 1 && resOdd)//一组个数为奇数，另一组异或值不为零 22 return resEven; 23  } 24 return -1; 25 }