位运算 - 初见
按位取反
not运算的定义是把内存中的0和1全部取反。
示例：~ 6
使用按位取反运算符，要知道几点：
1、内存中，一个int，4个字节，1字节8位。
00000000 00000000 00000000 00000110
~ --------------------------11111111 11111111 11111111 11111001
小技巧：可以用~使每个数的最低位为0，方法：a & ~1
别问我上面为什么不用这么长，我也不知道。我猜，是我不想写这么长哈哈哈。
左移位运算符 > 2
0 1 1 0
>>2 -------------0 0 0 1 = 1
小技巧：操作数每右移一位，相当于该数除以2。
负数的二进制表示
既然都讲到这里了，那自然要了解一下负数的表示形式了。
==用字节的最高位表bai示:“1"表示"正”,“0"表示"负” ==
1、把补码“取反”（把二进制数的各位“1”换“0”，“0”换“1”。比如“”取反后为“”）
2、把取反后的二进制数“加1”
示例：-17 转码
再转回来
-17转码：
17： 00000000 00000000 00000000 00010001
反码： 11111111 11111111 11111111 11101110
转码： 11111111 11111111 11111111 11101111
转回来自己动手。
所以C++中int的取值范围为：-2^31~2^31-1。
投机 异或的几条性质
1、交换律
2、结合律（即(a^b)^c == a^(b^c)）
3、对于任何数x，都有x^x=0，x^0=x
4、自反性: a^b^b=a^0=a;
位运算实现乘除
上面有
位运算实现swap
//普通操作
void swap(int &a, int &b) {a = a + b;b = a - b;a = a - b;
}//位与操作
void swap(int &a, int &b) {a ^= b;b ^= a;a ^= b;
}
呐，我来试试分析：
a ^= b --> a = a^b
b ^= a --> b = b^a^b = a
a ^= b --> a = a^b^a = b
挺秀的啊，不过有的人说这样会出问题，比方说 a = b 的时候。
那我再来分析一下：
a ^= b --> a = a^b = 0
b ^= a --> b = b^a^b = a = 0
a ^= b --> a = a^b^a = b = 0
哦，确实，他是对的。
都说是投机了，大家看着用吧，下面的其他投机技巧也说不定会是地雷哦。
位操作判断奇偶数
只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。
if(0 == (a & 1)) {//偶数
}
位操作交换符号交换符号
将正数变成负数，负数变成正数
int reversal(int a) {return ~a + 1;
}
整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数5. 位操作求绝对值整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 ），然后根据符号进行相应的操作
int abs(int a) {int i = a >> 31;return i == 0 ? a : (~a + 1);
}
上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)
int abs2(int a) {int i = a >> 31;return ((a^i) - i);
}
位操作统计二进制中 1 的个数
统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：
第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000
我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：count = 0
while(a){ a = a & (a - 1); count++;
}
用 O(1) 时间检测整数 n 是否是 2 的幂次
N如果是2的幂次，则N满足两个条件。
1.N >0
2.N的二进制表示中只有一个1
因为N的二进制表示中只有一个1,所以使用N & (N - 1)将N唯一的一个1消去，应该返回0。
数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。（异或自反性）
但当涉猎
1
a&a=a
a^a=02
a&0=0
a|0=a
a^0=a3
a|(a&b)=a
a&(a|b)=a4、交换值
a^=b;
b^=a;
a^=b;5、判断奇偶(取出最后一位)
a &1
等价于a%2(结果等于,位运算效率高)6、比较两值是否相等
a^b==07、i+1位置1
a |=1<<i8、i+1位置0
a &=~(1<<i)9、取出i+1
位(联系第5点)
a & (1<<i)10、在对应i+1位，插入b的对应位;
a |=1<<i; (a的bit位置1)
a & (b & 1<<i) (与b的bit位相与)11、删除最后的1;
a & (a-1)12、负数
a = ~a+113、仅保留最后一-个1
a&(-a)14、得到全1
~015、保留最后i-1位
a & ((1<<i)-1)16、清零最后i-1位
a & ~((1<<i)-1)以上，为最常见的用法，不带循环，全部O(1)。
这个要常回来看看啊。
一个大数去重的栗子
如何对10亿个QQ号进行去重
初次见面，先打基础，待我这两天去上包装一下。
待我包装完，试试看用位运算进行排序能不能写出来。
位图
不急。。
过两天就写，估计也会是粉丝可见咯
