位运算的妙用

做题中常用的位运算有以下几种：

1. 判断奇偶性

   if (n & 1) {
       printf("偶数"); 
   } else {
       printf("奇数");
   }

   常用于快速幂和其他判断奇偶性的地方

2. 乘除2的整次幂

   scanf("%d%d", &n, &m);
   // 输出n乘2的m次方 
   printf("%d", n << m);

   线段树求左儿子可以用 id << 1得到，一个偶数n 加1可以写做n | 1，如求左儿子可以用 id << 1 | 1得到。

   scanf("%d%d", &n, &m);
   // 输出n除2的m次方 
   printf("%d", n >> m);

   同理除2的整次幂也可以用右移运算符

3. 不开辟新空间交换a和b的值

   a ^= b;
   b ^= a;
   a ^= b;

   3和4都是利用两个相同的数异或等于0实现的。
   a ^= b之后    a = a ^ b;                b = b;
   b ^= a之后    a = a ^ b;                b = b ^ a ^b = a;
   a ^= b之后    a = a ^ b ^ a = b;    b = a;

4. 在一个数组中有n个数出现两次，还有1个数出现1次，求出现了一次的那个数

   int ans = 0;
   for (int i = 0; i < 2 * n + 1; i++) {
       ans ^= arr[i];
   } 
   printf("%d", ans);

   这种位运算的用法还有一个变种是在一个长度为1001的数组中只有1到1000这1000个数，并且只有1个数出现了两次，其他数都只出现一次，求出现两次的数

   // 假设这1001个数是从arr[1]到arr[1001]存的
   int ans = 0;
   for (int i = 1; i <= 1001; i++) {
       ans ^= i;
       ans ^= arr[i];
   } 
   printf("%d", ans);

   由于我们知道1到1000只有一个数出现两次其他数都只出现一次，那么我们在补上一个1到1000，使其他数都出现两次，唯一一个本来就有出现两次的数出现三次，最后出现两次的数都消掉之后剩下的就是唯一出现两次的数；

5. 不用判断语句求n的绝对值

   int temp = n >> 31;
   printf("%d", (n ^ temp) - temp);

   如果n为负数temp = -1，否则为0；一个数异或0等于本身然后减0还是本身，一个数异或-1相当于取反，然后减-1相当于加1，转为正数；