今天跟大家一起学习探讨一个关于位运算如何高效的做除法和取余操作。
看例子:
1. 取余操作
9 % 4 = 1
对应的二进制
9 ---------- 0000 1001
4 ---------- 0000 0100
0000 1001
& 0000 0011
--------------------------------
0000 0001
得到答案二进制 0000 0001 即对应的十进制 1
14 % 4 = 2
对应的二进制
14 --------- 0000 1110
4 --------- 0000 0100
0000 1110
& 0000 0011
--------------------------------
0000 0010
得到答案二进制 0000 0010 即对应的十进制 2
17 % 8 = 1
对应的二进制
17 -------- 0001 0001
8 -------- 0000 1000
0001 0001
& 0000 0111
--------------------------------
0000 0001
得到答案二进制 0000 0001 即对应的十进制 1
由上三个例子我们可以得到结论:
一个数a对一个数b(b=()取余时,可以用a & (-1) 更高效的得到结果(需要注意到是此方法只能用于(b=)
下面用代码来验证结果及效率比较
/**
* 说明:1. 为了使效率的比较更加明显,我选择较大的数8192来进行取余(当然16384是2的n次方数)
* 2. 使用毫微秒作为计时单位
* @author Kenny
*
* 运行结果:
* 1 = 1
* 2 = 2
* 1 = 1
* calcWithAnd use time 1785465
* calcWithMod use time 2565504
*
*/
public class Test {
public static void main(String[] args) {
//结论正确性验证
System.out.println(9 % 4 + " = " + (9 & 3));
System.out.println(14 % 4 + " = " + (14 & 3));
System.out.println(17 % 8 + " = " + (17 & 7));
//运行效率比较
long start = System.nanoTime();
calcWithAnd();
long stop = System.nanoTime();
System.out.println("calcWithAnd use time " + (stop - start));
start = System.nanoTime();
calcWithMod();
stop = System.nanoTime();
System.out.println("calcWithMod use time " + (stop - start));
}
public static void calcWithAnd() {
int result = 0;
for(int i = 10; i < 2000000000; i++) {
result = i & 16383;
}
}
public static void calcWithMod() {
int result = 0;
for(int i = 10; i < 2000000000; i++) {
result = i % 16384;
}
}
}
代码可以直接复制运行看下效果,结果可能会有偏差,跟机器运行环境和机器状态有关,但是能说明结论。
¥29.8
¥9.9
¥59.8