按位异或运算
俗称：xor运算
1、xor的基本知识
我们来看看xor运算的机理：
1001011001011----a
xor 1011010001110----b
0010001000101—c
看了上面的式子，体会到异或运算的原理了吧，就是：0和1异或0都不变，异或1则取反。很容易理解，如果b中的某位为1，那么a xor b 的作用是在a相应的位进行取反操作。用通俗易懂的语言来讲就是xor运算通常用于对二进制的特定一位进行取反操作。
我们再看到上面那个计算式子，如果得到的结果c再与b做异或运算即：
0010001000101—c
xor 1011010001110—b
1001011001011—d
注意到了吧，a == d 是成立的！那么我们可以得到一个结论：(a xor b) xor b = a。
同时我们还可以得到一个很诡异的swap操作：
a ^= b; b ^= a; a ^= b;
自己拿起笔来模拟一下就很清楚的了。
2、xor和 not （按位否）操作之间的关系
事实上很简单，nor操作是xor操作的一个特例。取反实质上就是同1做异或操作
~x = x^0x FFFFFFFF
3、两个比较有趣的式子：(n ^(n+1)) 和 ((n ^(n-1))+1)>>1
（1）首先来看(n ^(n+1))这个式子，假设n = 10011010， n+1 = 10011011，则：
10011010—n
xor 10011011—n+1
00000001—ans
如果还不能看出什么的话，再来一个例子：n = 11111111， n+1 = 100000000，则：
11110111—n
xor 11111000—n+1
000001111—ans
得到的结果为n的倒数出现第一个0的位以及后面所有的1全部变成1，其它位都为0的数。
（2）再来看看((n ^(n-1))+1)>>1这个式子
假设n = 10011010， n-1 = 10011001，则：
10011010—n
xor 10011001—n-1
00000011—ans
ans+1 >> 1 = 000000100 >> 1 = 000000010
看出来了吧，也就是取出n出现倒数第一个1的位及该位后面的0组成的数
4、统计n中1的奇偶性
思路：我们在按位与运算的时候学过了怎么计算一个整数中1的个数，但是我们现在用xor来解决吧：
复制代码 x = x ^ (x>>1); x = x ^ (x>>2); x = x ^ (x>>4); x = x ^ (x>>8); x = x ^ (x>>16); return x&1; 复制代码
说道这里，顺便提一下怎么求解一个数n的前导0的个数，下面的代码来自Hacker’s Delight
复制代码 int nlz(unsigned x) { int n; if (x == 0) return(32); n = 1; if ((x >> 16) == 0) {n = n +16; x = x <<16;} if ((x >> 24) == 0) {n = n + 8; x = x << 8;} if ((x >> 28) == 0) {n = n + 4; x = x << 4;} if ((x >> 30) == 0) {n = n + 2; x = x << 2;} n = n - (x >> 31); return n; }//代码自己慢慢理解吧 复制代码
