手撕位运算
0x00 -- 位运算概览
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 按位与， | 2个位都为1，结果为1 |
| ｜ | 按位或， | 一个位为1，结果为1 |
| ^ | 按位异或， | 相同为0，相异为1 |
| ~ | 按位取反， | 1变0，0变1 |
| <<n | 左移 | 各二进位全部左移n位，高位丢弃，低位补0 |
| >>n | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
0x01 -- 按位与 &
运算规则：0&0=0 0&1=0 1&1=1
俩位相同为1，否则为0
3&5 = 1
3 0000 0011
5 0000 0101
& 0000 0001
用途
- 清零
如果想将一个单元清0，即让这个数的各个位都为0，就让这个数去与一个各位都为0的数值按位与。结果为0
- 取一个数的指定位
举个🌰:
a = 1010 1110, 取a的低四位。只需要找一个b，把b的低四位设置为1，其余为0，即
b= 0000 1111 .
&= 0000 1110. 就可以得到a的指定部分， 这个过程中
b也就是a的（mask）所谓的掩码。
- 判断奇偶
只要根据末尾是
0还是1来判断是否是奇偶数。是0就是偶数，是1就是奇数。因此可以代替
if (a % 2) == 0替换为
if(a&1==0)来判断a是否为偶数。
0x02 -- 按位与 ｜
运算规则：0｜0=0 0｜1=1 1｜1=1
只要其中一位是1， 结果就位1.
3|5 = 7
3 0000 0011
5 0000 0101
| 0000 0111
用途
- 用来对一个数据的某些位设置位1
举个🌰:
a = 1010 1110, 设置a的低四位为1。只需要找一个b，把b的低四位设置为1，其余为0，即
b= 0000 1111 .
|= 1010 1111. 就可以得到按位与后的结果，
0x03 -- 按位异或 ^
运算规则：0^0=0 0^1=1 1^0=1 1^1=0
参加元算的俩个数，相同的位为0，不同的位为1；
异或的几条性质:
交换律
结合律 (ab)c == a(bc)
对于任何数x，都有 xx=0，x0=x
自反性: abb=a^0=a;
用途
-
翻转指定位
举个🌰:
a = 1010 1110, 翻转a的低四位。只需要找一个b，把b的低四位设置为1，其余为0，即
b= 0000 1111 .
^= 1010 0001. 就可以得到按位异或后的结果。 就把a的低四位按位翻转了。
-
与0相异或值不变
1010 1110 0000 0000 ^1010 1110 a 3 0000 0011 b 4 0000 0100 a^b 0000 0111 a b 4 0000 0100 b^a 0000 0111 a 0000 0011 b -
交换俩个数
void swap(int a, int b) { if(a!=b) { a^=b; b^=a; a^=b; } }
0x05 -- 按位取反 ~
运算规则: ~1=0 ~0=1
使a的最低位为0，可以表示为：
a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
0x06 -- 左移运算符 <<
使a的最低位为0，可以表示为：
a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
0x07 -- 右移运算符 >>
定义：将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。
操作数每右移一位，相当于该数除以2。
综合应用
比如有两个int类型变量x、y,首先要求x+y的和，再除以2，但是有可能x+y的结果会超过int的最大表示范围，所以位运算就派上用场啦。
(x&y)+((x^y)>>1);
对于一个大于0的整数，判断它是不是2的几次方
`((x&(x-1))==0)&&(x!=0)；
求绝对值
int abs( int x ) {
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
取模运算，采用位运算实现：
a % (2^n) 等价于 a & (2^n - 1)
乘法运算 采用位运算实现
a * (2^n) 等价于 a << n
除法运算转化成位运算
a / (2^n) 等价于 a>> n
求相反数
(~x+1)
a % 2 等价于 a & 1
