位操作符 练习

一、异或（^)

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

即：

0^0 = 0，1^0 = 1，

0^1 = 1，1^1 = 0

按位异或的3个特点：

（1）  0异或任何数＝任何数

（2）  1异或任何数=任何数取反

（3） 任何数异或自己＝把自己置0

按位异或的几个常见用途：

（1） 实现两个值的交换，而不必使用临时变量。

　　例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：

　　a = a^b； 　　//a=10100111

　　b = b^a； 　　//b=10100001

　　a = a^b； 　　//a=00000110

（2） 快速判断两个值是否相等

　举例： 判断两个整数a，b是否相等，则可通过下列语句实现：

　　return （（a ^ b） == 0）

按位异或的性质：

（1）交换律：A⊕B=B⊕A

（2）结合律：A⊕（B⊕C）=(A⊕B)⊕C

  (3)  自反性：A⊕A=0

注： 位操作符 的操作数必须是整数。

二、练习

练习一：单身狗

在一个整型数组中，只有一个数字出现一次，其他数组都是成对出现的，请找出那个只出现一次的数字。

例如：

数组中有：1 2 3 4 5 1 2 3 4，只有5出现一次，其他数字都出现2次，找出5

思路：数组中出现两次的数字异或的结果为0（相同异或为0），0与“单身狗”异或的结果为“单身狗”（0异或任何数＝任何数）。

#include <stdio.h>int find_single_dog(int arr[], int sz)
{int ret = 0;int i = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}return ret;
}
int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int dog = find_single_dog(arr, sz);printf("%d\n", dog);return 0;
}

练习二：打印整数二进制的奇数位和偶数位

思路：int共32bit位，每一位与1按位与，bit位是1与1按位与为1，bit位是0与1按位与为0，打印出奇数位和偶数位分别对应的值

 检测num中某一位是0还是1的方式：1. 将num向右移动i位2. 将移完位之后的结果与1按位与，如果：结果是0，则第i个比特位是0结果是非0，则第i个比特位是1

#include <stdio.h>
void Printbit(int num)
{for (int i = 31; i >= 1; i -= 2){printf("%d ", (num >> i) & 1);}printf("\n");for (int i = 30; i >= 0; i -= 2){printf("%d ", (num >> i) & 1);}printf("\n");
}
int main() {int n = 0;scanf("%d", &n);Printbit(n);return 0;
}

练习三：二进制中1的个数

思路1：

循环进行以下操作，直到n被缩减为0：1. 用该数据模2，检测其是否能够被2整除2. 可以：则该数据对应二进制比特位的最低位一定是0，否则是1，如果是1给计数加13. 如果n不等于0时，继续1

代码：

int NumberOf1(int n)
{int count = 0;while(n){if(n%2==1)count++;n = n/2;}return count;
}

上述方法缺陷：进行了大量的取模以及除法运算，取模和除法运算的效率本来就比较低。思路2：
一个int类型的数据，对应的二进制一共有32个比特位，可以采用位运算的方式一位一位的检测，
每一位与1按位与，结果有多少个1，二进制中的1就有多少个

代码：

int NumberOf1(unsigned int n)
{int count = 0;int i = 0;for(i=0; i<32; i++){if(((n>>i)&1) == 1)count++;}return count;
}

方法二优点：用位操作代替取模和除法运算，效率稍微比较高缺陷：不论是什么数据，循环都要执行32次

思路3：小技巧
通过位运算公式 n & (n - 1)可以消去二进制n的最右边的一个一（小伙伴们可以自己手动计算一下，负数正数都试试）。其上述代码的思想就是不断消1，消一次使得计数器加一。最后使n变成零结束循环。

采用相邻的两个数据进行按位与运算
举例：
9999：‭10 0111 0000 1111‬
第一次循环：n=9999   n=n&(n-1)=9999&9998= 9998
第二次循环：n=9998   n=n&(n-1)=9998&9997= 9996
第三次循环：n=9996   n=n&(n-1)=9996&9995= 9992
第四次循环：n=9992   n=n&(n-1)=9992&9991= 9984
第五次循环：n=9984   n=n&(n-1)=9984&9983= 9728
第六次循环：n=9728   n=n&(n-1)=9728&9727= 9216
第七次循环：n=9216   n=n&(n-1)=9216&9215= 8192
第八次循环：n=8192   n=n&(n-1)=8192&8191= 0可以观察下：此种方式，数据的二进制比特位中有几个1，循环就循环几次，而且中间采用了位运算，处理起来比较高效

int NumberOf1(int n)
{int count = 0;while(n){n = n&(n-1);count++;}return count;
}

练习四：两个整数二进制位不同个数

思路：举例：0011 和 0010

两数按位异或的结果为0001，两数二进制位不同个数为1个，异或的结果有一个1，问题转化为两数异或后的结果有多少个1

代码：

#include <stdio.h>
int calc_diff_bit(int m, int n)
{int tmp = m^n;int count = 0;while(tmp){tmp = tmp&(tmp-1);count++;}return count;
}int main()
{int m,n;while(scanf("%d %d", &m, &n) == 2){printf("%d\n", calc_diff_bit(m, n));}return 0;
}