与运算（）、或运算（）、异或运算（^）的本质及⽤途，⽂
末附加位运算⾯试题
⽬录
⼀：与运算符（&）and
1、运算规则：
0&0=0；0&1=0；1&0=0；1&1=1
即：两个同时为1，结果为1，否则为0
2、例如：3&5
⼗进制3转为⼆进制的3：0000 0011
⼗进制5转为⼆进制的5：0000 0101
------------------------结果：0000 0001 ->转为⼗进制：1
即：3&5 = 1
3、⽤途：
负数二进制补码运算法则
1）判断奇偶性
⼀个数 and 1 的结果就是取⼆进制的最末位。
这可以⽤来判断⼀个整数的奇偶
⼆进制的 最末位为 0 表⽰该数为偶数，最末位为 1 表⽰该数为奇数
2）清零。
如果想将⼀个单元清零，即使其全部⼆进制位为0，只要与⼀个各位都为零的数值相与，结果为零。
3）取⼀个数中指定位
⽅法：⼀个数，对应X要取的位，该数的对应位为1，其余位为零，此数与X进⾏“与运算”可以得到X中的指定位。
例：设X=10101110，
取X的低4位，⽤ X & 0000 1111 = 00001110 即可得到；
还可⽤来取X的2、4、6位。
⼆：或运算（|）or
1、运算规则：
0|0=0；  0|1=1；  1|0=1；  1|1=1；
即 ：参加运算的两个对象，⼀个为1，其值为1。
2、例如：3|5　
即 00000011 | 0000 0101 = 00000111，因此，3|5=7。　
3、⽤途：
1）对⼀个数据的某些位 - 置 1
⽅法：到⼀个数，对应X要 置 1 的位，该数的对应位为 1，其余位为零。此数与 X 相或 可使 X 中的某些位 - 置1例：将 X=10100000 的低 4 位 置 1 ，⽤ X | 0000 1111 = 1010 1111 即可得到
2）强⾏变成最接近的偶数
变为偶数，即：把⼆进制最末位变成 0
对这个数 or 1 之后再减⼀就可以了，就能把这个数强⾏变成最接近的偶数
使 a 的最低位为0，可以表⽰为：a & ~1。
~1的值为 1111 1111 1111 1110，再按"与"运算，最低位⼀定为0
三：异或运算符（^）xor
1、运算规则：
0^0=0；  0^1=1；  1^0=1；  1^1=0；
即：参加运算的两个对象，如果两个位为“异”（值不同），则该位结果为1，否则 值相同，则为 0。
两个位 值相同得 0，不同得 1
2、例如：3^5
=  0000 0011 | 0000 0101 =0000 0110，因此，3^5 = 6
3、⽤途：
1）使特定位翻转⼀个数
对应X要翻转的个位，该数的对应位为1，其余位为零，此数与X对应位异或即可。
例：X=10101110，使X低4位翻转，⽤X ^0000 1111 = 1010 0001即可得到。
2）与 0 相异或，保留原值
X ^ 00000000 = 1010 1110。
异或其实就是不进位加法，如1+1=0，,0+0=0,1+0=1。
异或的⼏条性质:
1、交换律
2、结合律（即 (a^b)^c == a^(b^c) ）
3、对于任何数 x，都有 x^x=0，x^0=x
4、⾃反性:  a^b^b = a^0 = a;
3）多项式除法
不过它最重要的性质还是⾃反性：A XOR B XOR B = A
即：对给定的数 A，⽤同样的运算因⼦（B）作两次 异或 运算后仍得到 A 本⾝。
（0 和任意数字进⾏ 异或 操作结果为 数字本⾝）
（两个相同的数字进⾏ 异或 的结果为 0）
两次 异或 同⼀个数 最后结果不变
这是⼀个神奇的性质，利⽤这个性质，可以获得许多有趣的应⽤。
4）简单的加密
⽐如我想对我 MM 说1314520，但怕别⼈知道，于是双⽅约定拿我的⽣⽇19880516作为密钥。
1314520 xor 19880516 = 20665500，我就把 20665500 告诉MM。
MM 再次计算 20665500 xor 19880516 的值，得到 1314520，于是她就明⽩了我的企图5）要交换两个变量的值 - 不⽤引⼊中间变量
所有的程序教科书都会向初学者指出，要交换两个变量的值，必须要引⼊⼀个中间变量。
但如果使⽤异或，就可以节约⼀个变量的存储空间：
设有A,B两个变量，存储的值分别为a，b，则以下三⾏表达式将互换他们的值 表达式 （值） ：
a=a^b;
b=b^a;
a=a^b;
四：左移运算符（<<）
将⼀个运算对象的各⼆进制位全部左移若⼲位（左边的⼆进制位丢弃，右边补0）。
例：a = a<< 2将a的⼆进制位左移2位，右补0，
左移1位后a = a *2;
若左移时舍弃的⾼位不包含1，则每左移⼀位，相当于该数乘以2。
五：右移运算符（>>）
将⼀个数的各⼆进制位全部右移若⼲位，正数左补0，负数左补1，右边丢弃。
操作数每右移⼀位，相当于该数除以2。
例如：a = a>> 2 将a的⼆进制位右移2位，
左补0 or 补1得看被移数是正还是负。
六：⾯试题实战
1、⼩算法：
1）乘 2 的⾮负整数次幂
int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
return n << m;
}
2）除以 2 的⾮负整数次幂
int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
return n >> m;
}
注意：
我们平常写的除法是向 0 取整，⽽这⾥的右移是向下取整（注意这⾥的区别），
即当数⼤于等于 0 时两种⽅法等价，当数⼩于 0 时会有区别，如： -1 / 2 的值为 0 ，⽽ -1 >> 1 的值为 −1 。3）判断⼀个数是不是 2 的正整数次幂
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
4）对 2 的⾮负整数次幂取模
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }
5）取绝对值
int Abs(int n) {
return (n ^ (n >> 31)) - (n >> 31);
/* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
需要计算 n 和 -1 的补码，然后进⾏异或运算，
结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}
6）取两个数的最⼤/最⼩值
// 如果 a>=b,(a-b)>>31 为 0，否则为 -1
int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }
int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }
7）判断符号是否相同
bool isSameSign(int x, int y) {  // 有 0 的情况例外
return (x ^ y) >= 0;
}
8）获取⼀个数⼆进制的某⼀位
// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }
2、1-1000 放在含有 1001 个元素的数组中，只有唯⼀的⼀个元素值重复，其它均只出现⼀次。
每个数组元素只能访问⼀次，设计⼀个算法，将它出来；不⽤辅助存储空间，能否设计⼀个算法实现？
解法⼀：
显然已经有⼈提出了⼀个⽐较精彩的解法，将所有数加起来，减去1+2+...+1000的和。
这个算法已经⾜够完美了，相信出题者的标准答案也就是这个算法，唯⼀的问题是，如果数列过⼤，则可能会导致溢出。
解法⼆：
异或就没有这个问题，并且性能更好。
将所有的数全部异或，得到的结果 再与 1^2^3^...^1000 的结果进⾏ 再异或，得到的结果就是重复数。
2'、变种：给定⼀个⾮空整数数组，除了某个元素只出现⼀次以外，其余每个元素均出现了三次。出那个只出现了⼀次的元素。