位运算

· · 算法·理论

位运算

左移

若 $x=1$ ,那么 $x<<1$ 为2： $x$ : $~~~~~~~~~$ 0000000000000001 $x<<1$ : 0000000000000010 所以 $x<<1$ 即 $x*2$ （但运算速度更快） $x<<i$ 即$x*2^i

右移

类比左移。 $x>>i$ 即$x/2^i

或运算

$x$ : $~~$ 101 $y$ : $~~$ 010 $x|y$ : 111 原理就是比较的两位中有1结果就为1，没有就为0。 ### 与运算 & 即**按位与**（and） $x$ : $~~~~$ 101 $y$ : $~~~~$ 010 $x$&$y$ : 000 原理就是比较的两位中有0结果就为0，没有就为1。（与按位或相对） ### 非运算 ~ 即**按位取反**（not） $x$ : $~$ 101 ~$x$ : 010 就是把每一位修改为相反的值。（0变1，1变0） ### 异或 ^ 即**按位异或**（xor） $x$ : $~~~$ 1010 $y$ : $~~~$ 1100 $x$^$y$ : 0110 每一位相同为0，不同为1。 ### 一些操作 - **取一固定位值** 例：取从左向右第2位 $x$ : $~~~~~~~~~~~~~~~~$ 1010 $1<<1$ : $~~~~~~$ 0010 $x$&($1<<1$) : 0010 某一位与上1，既保留原位。（0&1是0，1&1是1） - **设置固定位为0** 例：将从左向右第2位设为0 $x$ : $~~~~~~~~~~~~~~~~~~~$ 1010 ~$1<<1$ : $~~~~~~~$ 1101 $x$& ~($1<<1$) : 0010 0可以将此位设为零，所以只要此位为零即可。（多位同理） - **固定位取反** $x$ : $~~~~~~~~~~~~~~~~$ 1010 $1<<1$ : $~~~~~~$ 0010 $x$^($1<<1$) : 0010 某一位和1异或，1^1为0，0^1为1，达成取反的目的。 - **n位全为1** ($1<<n$)$-1