Chapter1: 位运算的奇技淫巧
1. 位运算基础
1. 基本概念与基本运算
1.1 原码、反码与补码
在计算机中，数字以二进制补码形式表达
具体的二进制数长度，要看定义的整数的类型，比如 int 一般是32位，short 16位等
-
原码
正数的原码: 其绝对值大小转换成的二进制数，然后最高位补符号位0
负数的原码: 其绝对值大小转换成的二进制数，然后最高位符号位1
-
反码
正数的反码: 与其原码相同
负数的反码: 其原码除符号位外各位取反
-
补码
正数的补码: 与其原码相同
负数的反码: 其原码除符号位外各位取反，末位+1
1.2 位运算概念
位运算概念：在处理整型数值 时，可以直接对组成整型数值的各个位进行操作。这意味着可以使用屏蔽技术获得整数中的各个位。
屏蔽技术：因为 0 与任何数进行 与运算& 都得 0 ,所以可以通过一个特定位为 1， 其它位为 0的数，与要了解的数进行 & 运算，再进行 右移位运算>> 将特定位移到第一位，即可知道这个特定位的值是 0 还是 1.
1.3 位运算基本运算
&(与)、|(或)、~(非|取反)、^(异或)<<左移,将二进制位进行右移操作，高位丢弃，低位补0-
>>右移, 各二进位全部右移若干位，对无符号数(正数)，高位补0；对于有符号数，各编译器处理方法不一样，有的补符号位（称为算术右移），有的补0（称为逻辑右移），在微软的VC6.0和VS2008编译器都是采取算术移位操作int a = -15, b = 15; printf("%d %d\n", a >> 2, b >> 2);因为15=0000 1111(二进制)，右移二位，最高位由符号位填充将得到0000 0011即3。-15 = 1111 0001(二进制)，右移二位，最高位由符号位填充将得到1111 1100即-4
注:
int类型一般占4字节，32位。因此15准确表达为15=00000000 00000000 00000000 00001111(二进制)
-15准确表达为
-15=11111111 11111111 11111111 11110001(二进制)
为了简便起见，文章中使用15=00001111(二进制)，-15=11110001(二进制)。
另外位操作还有一些复合操作符，如
&=、|=、^=、<<=、>>=。
2. 简单示例
1.1 判断奇偶数
用与1的 & 运算
奇数末位是 1, 偶数末位是 0,因此可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断a是不是偶数
1.2 获取特定二进制位是1还是0
因为 0 与任何数进行 与运算& 都得 0 ,所以可以通过一个特定位为 1， 其它位为 0的数，与要了解的数进行 & 运算，就能得到一个除了特定位得到保留、其它位都为 0的数。再进行 右移位运算>> 将特定位移到第一位，即可知道这个特定位的值是 0 还是 1.
1.3 交换两个整数变量的值
一般的写法需要一个额外变量来存储交换中间值
位运算写法：
void Swap(int &a, int &b)
{
if (a != b)
{
a ^= b;//a=a^b
b ^= a;//b=b^a=b^(a^b)=(b^b)^a=0^a=a,即b=a
a ^= b;//a=a^b=(a^b)^a=(a^a)^b=0^b=b,即a=b
}
}
1.4 变换符号
变换符号就是正数变成负数，负数变成正数。
只需要取反后加1 reverse=~a + 1 即可
如
对于-11和11，可以通过下面的变换方法将-11变成11
1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)
同样可以这样的将11变成-11
0000 1011(二进制) –取反-> 0000 0100(二进制) –加1-> 1111 0101(二进制)
1.5 求整数的绝对值
对于负数可以通过对其取反后加1来得到正数 ,所以可以通过判断语句，如果是整数则返回原数，否则返回 ~a+1
先移位来取符号位，int i = a >> 31 ; 如果 a 为正数，i 等于0 ; a 为负数，i 等于 -1 (注意是补码，高位补1)。对 i 进行判断: 如果 i 等于 0，直接返回。否之，返回 ~a+1。完整代码如下：
int my_abs(int a)
{
int i = a >> 31;
return i == 0 ? a : (~a + 1);
不用判断语句的方法：
任何数与 0 异或运算都不变，与 -1 (0xFFFFFFFF,即11111111111111111111111111111111)异或运算相当于取反，所以代码优化如下：
对于正数，((a^i)-i) 返回 a ，对于负数，则相当于返回 ~a+1
int my_abs(int a){
int i=a>>31;
return ((a^i)-i);
}
3. 参考资料
[1] 负数的二进制表示方法
[2] 位操作基础篇之位操作全面总结
