位运算|常用场景

位运算介绍

最近工作涉及一些数据传输\加密\计算相关内容,发现位运算这么好用的东西,竟然没人用.这里做一下位运算基础操作和常用场景.

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）。 摘自百度百科

位操作是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，情况并非如此：位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。摘自维基百科

位运算一般用于二进制数据计算,但总所周知,计算机所有的数据都是二进制.现代高级语言中,有各种函数和运算符可以直接对数字进行计算,但是需要特定的场景使用位运算能提升运行效率和稳定性.

位运算

位运算包含 与或非,异或,位移

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

与

与运算,两个位都为1时，结果才为1

输入A	输入B	输出
0	0	0
0	1	0
1	0	0
1	1	1

或

或运算两个位都为0时，结果才为0

输入A	输入B	输出
0	0	0
0	1	1
1	0	1
1	1	1

非、取反

取反运算 0变1，1变0

输入A	输出
0	1
1	0

异或

异或运算 两个位相同为0，相异为1

输入A	输入B	输出
0	0	0
0	1	1
1	0	1
1	1	0

按位与 按位或 按位非 按位异或

两个二进制数字,右端对齐后,逐位进行位计算的到的结果
例如

jshell> 28 | 5
$19 ==> 29

将十进制转二进制 28 = 0001 1100 , 5 = 0000 0101
按位或运算

    0001 1100
OR  0000 0101
----------------
    0001 0101

0001 0101 = 29
其他运算相同的操作逻辑

位移运算

左移

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）
例如

jshell> int i = 7
i ==> 7

jshell> i <<= 1
$5 ==> 14

jshell> i
i ==> 14

位于计算是二进制操作,先把7转为二进制 7 = 0000 0111
将 所有位向左移动1位,最右位补0.

0000 0111 << 1 
0000 1110 

0000 1110 转10进制 等于 14

i 左移一位 相当于 i * 2,
i 左移N位 等于 $ i * 2^N $

右移

各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）
java 右移分为有符号右移(>>>,逻辑右移) 和无符号右移(>>,算术右移)
java 保存有符号(负号)整数时,最高位(最左)保存符号,0代表正数,1代表负数.保存负数时以补码形式保存,其实就是取反了.
以java int 为例,int 是4字节长度保存整数,一共4 * 8 = 32 位.最高位保存符号,其余31位用来保存实际数字,所以int 取值范围 为 -2147483648 ~ 2147483647 .
因为有0的存在,需要占一位,正数部分最大值为 $2^{31} -1$,负数为 $- ( 2^{31} )$.
负数数字补码部分由于0的存在,需要-1后取反
例如

  0 = 0000 0000 0000 0000 0000 0000 0000 0000
 10 = 0000 0000 0000 0000 0000 0000 0000 1010
 -1 = 1111 1111 1111 1111 1111 1111 1111 1111
-10 = 1111 1111 1111 1111 1111 1111 1111 0110

 10 >> 1 = 5
  5 = 0000 0000 0000 0000 0000 0000 0000 0101
 -10 >> 1 = -5
 -5 = 1111 1111 1111 1111 1111 1111 1111 1011
 
 10 >>> 1 = 5 
  5 = 0000 0000 0000 0000 0000 0000 0000 0101
 -10 >>> 1 = 2147483643
 2147483643 = 0111 1111 1111 1111 1111 1111 1111 1011
 

有符号右移时,高位会补符号位的值,负数右移前面会补1
无法好位移时,高位直接补0,负数右移后,符号位补0变正数

使用场景

位计算

位计算用的最多的应该是权限判断相关的,1个int类型,32个有效长度,可以保存32种可叠加的状态.例如linux的权限,使用3位进行保存读写执行状态,其中,1为是否可执行,2为是否可写,4为是否可读.把这三个数转换为二进制,就能发现.

1  =>  0001  ==  1 << 0
2  =>  0010  ==  1 << 1
4  =>  0100  ==  1 << 2

一个文件初始为0000,使用或运算赋权可读4,再叠加赋权可写权限2,

    0 = 0000
    4 = 0100
    2 = 0010
| -----------
        0110 = 6
0 | 4 | 2 = 6

linux 可读可写,不可执行权限即为6.
验证是否有权限,则使用与运算,判断对应位是否为1.
例如,文件权限为6 ,判断是否包含写权限2.

    6 = 0110
    2 = 0010
& -----------
        0010 = 2
        
(6 & 2 == 2) = true 验证文件具有写权限

删除权限需要使用异或计算,相同位为0,不同位为1
例如,文件权限为6 ,删除写权限2.

    6 = 0110
    2 = 0010
^ -----------
        0100 = 4

异或运算可以用来排他计算.一个非常经典的算法题:一个int数组,长度为奇数,除一个数字外,其他的数字都是成对出现,最快找到这个数.这时就需要使用异或运算,遍历每个元素进行异或,相同得0,不同得1,结果就是最不同的孤寡蛙.

位移运算

位移运算最简单的用处就是快速 乘除 2 以及2的指数.运算速度比乘除运算符要快.但是只适合整数,小数的二进制以指数方式保存,无法使用位移运算.

汇总

//声明权限
int a = 1 << 0;
int b = 1 << 1;
int c = 1 << 2;
int i = 0;
// 赋权
i |= a; // i = i | a;
// 回收
i ^= a;// i = i ^ a;
//判断
i & a == a; // boolean

//判断是否为偶数
(i & 1) != 0 ; // i % 2 != 0