最近看源码的时候,遇到了各种位运算,又想起之前做的一个面试题也是求解一个包含各种位运算的表达式,这方面的知识点虽说平时可能用到的地方不会太多,但了解完之后发现它可以很方便的去实现一些逻辑,如奇数偶数的判断等。
进制
要了解位运算前,还是先回顾一下进制,通俗来说 x进制就是逢x进一,2进制、8进制、10进制和16进制如下表所示:
2进制 | 8进制 | 10进制 | 16进制 |
---|---|---|---|
0 | 0 | 0 | 0 |
01 | 1 | 1 | 1 |
10 | 2 | 2 | 2 |
11 | 3 | 3 | 3 |
100 | 4 | 4 | 4 |
101 | 5 | 5 | 5 |
110 | 6 | 6 | 6 |
111 | 7 | 7 | 7 |
1000 | 10 | 8 | 8 |
1001 | 11 | 9 | 9 |
1010 | 12 | 10 | A |
1011 | 13 | 11 | B |
1100 | 14 | 12 | C |
1101 | 15 | 13 | D |
1110 | 16 | 14 | E |
1111 | 17 | 15 | F |
进制转换
那么,他们之间需要如何来转换呢?这里以2进制和10进制的转换为例来进行说明。
整数部分,遵循 除2取余,逆序排列:1
2
3
4
5
6
7
8
9求10进制 123 的 2进制:
123 / 2 = 61 余 1
61 / 2 = 30 余 1
30 / 2 = 15 余 0
15 / 2 = 7 余 1
7 / 2 = 3 余 1
3 / 2 = 1 余 1
1 / 2 = 0 余 1
2进制为:1111011
再看小数部分,遵循 乘2取整,顺序排列,即用小数乘2后:取出积中的整数部分,然后用剩下的小数继续去乘2,直到小数部分为0或者是到指定精度为止。
那么负数怎么转换呢?这个就要提到补码了,为了计算方便,负数在计算机中都是以补码的形式存在,那么 -123 的2进制就为:1111011
的补码即 0000101
那么2进制 1101101
转换为10进制又是多少呢?这里先看下10进制数123,我们将它展开
1 | 123 = 1 * 100 + 2 * 10 + 3 * 1 |
很明显就看出了其中的规则,x进制的数 abc 转换为10进制:1
a * x^2 + b * x^1 + c * c^0
那 1101101
转换为10进制也就很容易了:1
2
31*2^6 + 1*2^5 + 0*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
= 1 * 64 + 1 * 32 + 0 * 16 + 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1
= 109
2进制和8进制以及16进制之间的转换更为方便,我们知道8=2^3
,而16=2^4
,因此可以分别用3位和4位2进制来表示1位8进制和16进制,位数不够补0,例如:1
22进制 1101101 = 2进制 001 101 101 = 8进制 155
2进制 1101101 = 2进制 0110 1101 = 16进制 6D
原码
数在计算机中的二进制表示,第一位代表符号,0表示正数,1表示负数,如2的原码为 0000 0010
,-2的原码为 1000 0010
反码
正数的反码就是原码,负数的反码为符号位不变,其余位取反,如2的反码为 0000 0010
,-2的反码为 1111 1101
补码
正数的补码就是原码,负数的补码为符号位不变,其余位取反后加一,如2的补码为 0000 0010
,-2的补码为 1111 1110
,补码保证了当一个数是正数时,其最左的比特位是0,当一个数是负数时,其最左的比特位是1。因此,最左边的比特位被称为符号位,关于补码的作用可以看看阮一峰老师这篇文章,个人觉得通俗易懂。
位运算
搞清楚了进制之间的转换,那么位运算其实也就没有什么难的了,位运算只要有一下几种,使用 Java 代码来进行展示。
与操作
在 Java 中操作符为 &
,1 与 1 相与为 1,否则为0,如:1101
与 0101
相与结果为 0101
。
或操作
在 Java 中操作符为 |
,0 与 0 相或为 0,否则为1,如:1101
与 0101
相与结果为 1101
。
非操作
在 Java 中操作符为 ~
,1 取反为 0,0 取反为 1,如 ~5 = -6
:1
2
3
4~ 0000 0000 0000 0000 0000 0000 0000 0101 5的原码
1111 1111 1111 1111 1111 1111 1111 1010 5取非的原码
= 1000 0000 0000 0000 0000 0000 0000 0110 转换为补码,等于 -6
这里很奇怪的一点,为什么取非之后还要转换为补码,因为是有符号的,而负数在计算器中是以补码的形式存在,对任一数值 x 进行按位非操作的结果为 -(x + 1)。
异或操作
在 Java 中操作符为 ^
,比较位不同时为1,否则为0,如 2 ^ 3 = 1
:1
2
3 0000 0000 0000 0000 0000 0000 0000 0010 2的原码
^ 0000 0000 0000 0000 0000 0000 0000 0011 3的原码
= 0000 0000 0000 0000 0000 0000 0000 0001 1的原码
将任一数值 x 与 0 进行异或操作,其结果为 x。将任一数值 x 与 -1 进行异或操作,其结果为 ~x。
左移
在 Java 中操作符为 <<
,向左移动指定位数,移出的位数抛弃,右侧补0。
右移
在 Java 中操作符为 >>
,向右移动指定位数,移出的位数抛弃,左侧补最高位,即最高位为1则补1,为0则补0,即符号位不会变,而 >>>
则是指无符号右移,左侧总是补0。
优先级
(+ - * ) > (>> << >>>) > & | ^