注：读《程序员面试笔记》笔记总结
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 }
提示：按位从尾部根据0和1分成两组，当两组都有数，且偶数个的组所有值取异或不为零时，另一组取异或的值极为其中一个满足的值。
