位运算

2021-12-26 本文已影响0人我阿郑

很多轮子的源码底层都会用到大量的位运算, 比如最经典的用 “>>1”代替“/2”, 比如加密解密算法、哈希算法、置位等等，都要用到位运算。因为,这可以提高性能, 加减乘除底层其实都是通过位运算实现的.

一、按位与（ & ）

按位& 操作通常用于二进制取位操作

例如：一个数 &(and) 1 的结果就是取二进制的最末位

这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数.
相同位的两个数字都为1，则为1；若有一个不为1，则为0

00111
11100
（&或者and）
----------------
00100

二、按位或（ | ）

按位或操作通常用于二进制特定位上的无条件赋值

例如：一个数 |(or) 1 的结果就是把二进制最末位强行变成1
如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了

00111
11100
（|或者or）
----------------
11111

三、按位异或（ ^ ）

按位异或运算通常用于对二进制的特定一位进行取反操作
按位异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变

0和1异或结果为1
1和0异或结果为1
1和1异或结果为0
0和0异或结果为0

00111
11100
（^或者xor）
----------------
11011

四、右移位运算 ( >> )

右移1位即除以2，并且取整

m_Height>>4相当于：m_Height/16

五、左移位运算 ( << )

若左移一位，则其数值变为a*2

六、按位取反 ( ~ )

按位取反也就是基于二进制进行的一个操作. 所不同的是，在完成按位取反之后，还需要转换为“原码”

如果开始二进制是 : 00111
按位取反后的二进制: 11000

⚠️: 比如十进制数字： 57

表示成8位二进制是 : 00111001
按位取反后的二进制: 11000110

负数在计算机里要用其补码来表示: 补码 = 符号位以后按位取反 + 1

所以我们得到的(11000110)是一个补码, 知道了补码,然后求原码:

负整数原码 = 补码除符号位后按位取反 + 1

所以11000110 除符号位以后按位取反后为 10111001 再加1 则为(10111010)

10111010 换成十进制为:-58
因此 ~57 = -58

例如: 32位cpu下, 计算~5的值, 过程如下：

5 的二进制为：0000 0000 0000 0000 0000 0000 0000 0101
~运算后: 1111 1111 1111 1111 1111 1111 1111 1010

如果忘记了负数的二进制表达方式, 可能会以为它(1……1010)应该表示-10

计算机使用补码表示负数, 所以
求原码 = 1111 1111 1111 1111 1111 1111 1111 1010 除符号位后取反 + 1 
      = 1000 0000 0000 0000 0000 0000 0000 0110
换成十进制等于: -6
即~5 = -6
因此，可以总结出~按位取反的计算结论是：~n = -(n+1)
例如: ~5 = -(5+1)
~3 = -(3+1) = -4 // 3按位取反后的十进制结果是: -4 ,即 ~3 = -4
~-4 = -(-4+1) = 3

按位取反应用

unsigned int a, b;
a=3; // 按位取反后的十进制结果是: -4 ,即 ~a = -4
b=~a;
printf("b is %d\n",b); // -4
a=~b;
printf("a is %d\n",a); // 3

✅ : 大胆猜测下, 关联对象中 HashMap的key 按位取反的原因是否是这样的原因

按位取反中，_-1=0，0=-1, 在C语言中,非0即为真

底层其他常用位运算

常可以看到这样的表达 a|=b ，意思是a =（a|b）, 这与 a+=b有点类似(a = a+b)

int  a =  1 , b =  2 ,c =  4 ; // 0x0001,0x0010,0x0100
a |= b; // a = 0x0011 = 3
b |= c; // b = 0x0110 = 6

这种表达很有用，这个方式在很多需要一个值标识多种状态下普遍适用

位运算