位运算，相信所有的同学都有所了解。

那么关于位运算有哪些特殊的技巧呢？

速度比较

取模时间 > 四则运算时间 > 位运算时间

所以对于一个语句

if (a % 2 == 1) {  
    a /= 2;  
}  

我们可以优化成为

if (a & 1 == 1) {  
    a >>= 1;  
}  

异或运算的特殊性

异或同一个数2次或者偶数次，那么本身的值不变。

例如：

a^b^b = a
x^y^y^y^y = x

接下来我们来看一下它的应用。

缺页问题
题目描述：
小明有一本很喜欢的漫画书，但是由于他上课的时候偷看这本漫画书被老师发现，于是老师将小明的漫画书撕了扔进垃圾桶。

小明放学后从垃圾桶里将漫画书捡了回来，缺发现漫画书少了一页。小明的漫画书一共有N页，由于现在页码顺序错乱，小明也不知道是少了哪一页，聪明的你能告诉小明缺失的是哪一页吗？
输入描述：
第一行输入一个整数N（N<1000000），表示小明书的总页数。
第二行输入N-1个数整数，代表小明找到的页码。
输出描述：
请输出小明缺失的页码在单独的一行。
请注意：本题的空间很小，要求你尽量不使用额外的空间来解决。
输入样例#:
6
6 2 1 5 3
输出样例#:
4
题目来源：
DreamJudge 1506

题目解析：由于本题要求我们以尽量小的空间来解决问题，所以我们不能够使用数组来存储每一个数。那么我们应该怎么办呢？这个时候可以想到异或运算的特殊技巧，同一个数异或两次那么就会消除，如果我们提前将1到N的所有数字进行异或处理，然后再去异或输入的N-1个数，那么答案就是缺失的那个数。

参考代码

#include<bits/stdc++.h>  
using namespace std;  
  
int main(){  
    int n, x;  
    scanf("%d", &n);  
    int sum = 0;  
    for (int i = 1; i <= n; i++) {  
        sum ^= i;  
    }  
    for (int i = 1; i < n; i++) {  
        scanf("%d", &x);  
        sum ^= x;  
    }  
    printf("%d\n", sum);  
    return 0;  
}  

常见位运算问题

1.位操作实现乘除法

数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

int a = 2;  
a >> 1; ---> 1  
a << 1; ---> 4  

2.取相反数

思路就是取反并加1，也即~n + 1或者(n ^ -1) + 1。

3.判断奇偶性

/* 判断是否是奇...

题目练习

DreamJudge 1118 将军的书