包括位运算的基本用法和实际应用。
Java位运算相关
位运算符(移位运算)
左移位:<<
右移位:>>
特殊的右移位:>>>
移位运算符的左操作数是被移的数,右操作数是要移动的位数。
num << 1
相当于左移一位,相当于num乘以2。即整体左移移位,低位补0。
num >> 1
相当于右移一位,相当于num除以2。即整体右移一位,符号位不动,和符号位相邻的位补上和符号位一样的数。
num >>> 1
相当于右移一位,和 >>
不同的是,这个运算符会让符号位也一起向右移动。高位补0。
注意:没有 <<<
这个运算符。
注意
移位运算符本身不是原地运算,也就是说,不能写出一条单独的语句 a >> 1;
,要写成 a = a >> 1;
。
或者使用 >>=
或者 >>>=
或者 <<=
。也就是写成 a >>= 1;
这样。
测试代码
1 | class BitwiseTest |
输出的结果:
因为 Java 基本的转换为二进制不能自动高位补零,所以有些是要高位补零的,我已经给加上了,所以和大家自己运行出来的可能有些不同。
1 | // Test << |
位运算的应用
取模
X % $2^n$ = X & ($2^n$ - 1)
一个数对 $2^n$ 取模 相当于 一个数和($2^n$ - 1)做按位与运算 。注意,必须是对 $2^n$ 取模才满足。
假设n为3,则 $2^3$ = 8,表示成2进制就是$(1000)_2$。$2^3$ - 1 = 7 ,即 $(0111)_2$。
此时 X & ($2^3$ - 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。
参考文章
Bit Twiddling Hacks - By Sean Eron Anderson