java实现次方的运算_Java中对于位运算的优化以及运用与思考
引言
隨著JDK的發展以及JIT的不斷優化,我們很多時候都可以寫讀起來易讀但是看上去性能不高的代碼了,編譯器會幫我們優化代碼。之前大學里面學單片機的時候,由于內存以及處理器性能都極其有限(可能很多時候考慮內存的限制優先于處理器),所以很多時候,利用位運算來節約空間或者提高性能,那么這些優秀的思想,放到目前的Java中,是否還有必要這么做呢?我們逐一思考與驗證下(其實這也是一個關于Premature optimization的界定的思考)
1. 乘法與左移位
左移一位,相當于乘以2,左移n位,相當于乘以2的n次方。
1 << 1 == 1 * 2 //true1 << n == 1 * pow(2, n) // truepublic int pow(int i, int n) { assert n >= 0; int result = 1; for (int i = 0; i < n; i++) { result *= i; } return result;}看上去,移位應該比乘法性能快。那么JIT與JVM虛擬機是否做了一些優化呢?優化分為兩部分,一個是編譯器優化,另一個是處理器優化。我們先來看看字節碼是否一致判斷是否有編譯優化,例如直接將乘以2優化成左移一位,來編寫兩個函數:
public void multiply2_1() { int i = 1; i = i << 1;}public void multiply2_2() { int i = 1; i *= 2;}編譯好之后,用javap -c來看下編譯好的class文件,字節碼是:
public void multiply2_1(); Code: 0: iconst_1 1: istore_1 2: iload_1 3: iconst_1 4: ishl 5: istore_1 6: return public void multiply2_2(); Code: 0: iconst_1 1: istore_1 2: iload_1 3: iconst_2 4: imul 5: istore_1 6: return可以看出左移是ishl,乘法是imul,從字節碼上看編譯器并沒有優化。那么在執行字節碼轉換成處理器命令是否會優化呢?是會優化的,在底層,乘法其實就是移位,但是并不是簡單地左移
我們來使用jmh驗證下,添加依賴:
org.openjdk.jmh jmh-core 1.22org.openjdk.jmh jmh-generator-annprocess 1.22site.ycsb core 0.17.0實現思路:
測試結果:
Benchmark Mode Cnt Score Error UnitsBitUtilTest.multiply2_n_mul_not_overflow thrpt 300 35882831.296 ± 48869071.860 ops/sBitUtilTest.multiply2_n_shift_not_overflow thrpt 300 59792368.115 ± 96267332.036 ops/s可以看出,左移位相對于乘法還是有一定性能提升的
2. 除法和右移位
這個和乘法以及左移位是一樣的.直接上測試代碼:
@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public void divide2_1_1(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE / l; }}@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public void divide2_1_2(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE >> j; }}結果:
Benchmark Mode Cnt Score Error UnitsBitUtilTest.divide2_n_div thrpt 300 10219904.214 ± 5787618.125 ops/sBitUtilTest.divide2_1_shift thrpt 300 44536470.740 ± 113360206.643 ops/s可以看出,右移位相對于除法還是有一定性能提升的
3. “取余”與“取與”運算
對于2的n次方取余,相當于對2的n次方減一取與運算,n為正整數。為什么呢?通過下圖就能很容易理解:
十進制中,對于10的n次方取余,直觀來看就是:
其實就是將最后n位取出,就是余數。 對于二進制,是一樣的:
這個運算相當于,對于n-1取與:
這個是一個很經典的位運算運用,廣泛用于各種高性能框架。例如在生成緩存隊列槽位的時候,一般生成2的n次方個槽位,因為這樣在選擇槽位的時候,就可以用取與代替取余;java中的ForkJoinPool的隊列長度就是定為2的n次方;netty中的緩存池的葉子節點都是2的n次方,當然這也是因為是平衡二叉查找樹算法的實現。
我們來看下性能會好多少:
@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public void mod2_n_1(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE % l; }}@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public void mod2_n_2(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE & (l - 1); }}結果:
Benchmark Mode Cnt Score Error UnitsBitUtilTest.mod2_n_1 thrpt 300 10632698.855 ± 5843378.697 ops/sBitUtilTest.mod2_n_2 thrpt 300 80339980.989 ± 21905820.262 ops/s同時,我們從這里也可以引申出,判斷一個數是否是2的n次方的方法,就是看這個數與這個數減一取與運算看是否是0,如果是,則是2的n次方,n為正整數。
進一步的,奇偶性判斷就是看對2取余是否為0,那么就相當于對(2-1)=1取與。
4. 求與數字最接近的2的n次方
這個廣泛運用于各種API優化,上文中提到,2的n次方是一個好東西。我們在寫框架的很多時候,想讓用戶傳入一個必須是2的n次方的參數來初始化某個資源池,但這樣不是那么靈活,我們可以通過用戶傳入的數字N,來找出不大于N的最大的2的n次方,或者是大于N的最小的2的N次方。
抽象為比較直觀的理解就是,找一個數字最左邊的1的左邊一個1(大于N的最小的2的N次方),或者是最左邊的1(小于N的最大的2的N次方),前提是這個數字本身不是2的n次方。
那么,如何找呢?一種思路是,將這個數字最高位1之后的所有位都填上1,最后加一,就是大于N的最小的2的N次方。右移一位,就是小于N的最大的2的N次方。
如何填補呢?可以考慮按位或計算,我們知道除了0或0=0以外,其他的都是1. 我們現在有了最左面的1,右移一位,與原來按位或,就至少有了兩位是1,再右移兩位并按位或,則至少有四位為1。。。以此類推:
用代碼表示是:
n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;n += 1; //大于N的最小的2的N次方n = n >>> 1; //小于N的最大的2的N次方如果有興趣,可以看一下Java的ForkJoinPool類的構造器,其中的WorkQueue大小,就是通過這樣的轉換得來的。
5. 交換兩個數字
這個在單片機編程中經常會使用這個位運算性質:一個數字異或自己為零,一個數字異或0為自己本身。那么我們就可以利用這個性質交換兩個數字。
假設有數字x,y。 我們有x^y^y = x^(y^y)= x^0 = x 還有x^y^y^x^y = 0^y = y 那么我們可以利用:
x = x ^ y;y = x ^ y; //代入后就是x^y^yx = x ^ y; //代入后就是x^y^y^x^y這個方法雖然很巧妙,但是是一種時間換空間的方式; 我們常用的利用另一個變量實現交換是一種空間換時間的方式,來對比下性能:
@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public int swap_1() { int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2; int z = x; x = y; y = z; return x + y;}@Benchmark@Warmup(iterations = 0)@Measurement(iterations = 300)public int swap_2() { int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2; x ^= y; y ^= x; x ^= y; return x + y;}結果:
Benchmark Mode Cnt Score Error UnitsBitUtilTest.swap_1 thrpt 300 267787894.370 ± 559479133.393 ops/sBitUtilTest.swap_2 thrpt 300 265768807.925 ± 387039155.884 ops/s測試來看,性能差異并不明顯,利用位運算減少了空間占用,減少了GC,但是交換減少了cpu運算,但是GC同樣是消耗cpu計算,所以,很難界定。目前還是利用中間變量交換的更常用,也更易讀一些。
6. bit狀態位
我們為了節省空間,嘗嘗利用一個數字類型(例如long類型)作為狀態數,每一位代表一個狀態是true還是false。假設我們使用long類型,則一個狀態數可以最多表示64個屬性。代碼上一般這么寫:
public static class Test { //如果你的field是會被并發修改訪問,那么最好還是加上緩存行填充防止false sharing @jdk.internal.vm.annotation.Contended private long field; private static final long SWITCH_1_MASK = 1; private static final long SWITCH_2_MASK = 1 << 1; private static final long SWITCH_3_MASK = 1 << 2; public boolean isSwitch1On() { return (field & SWITCH_1_MASK) == 1; } public void turnOnSwitch1() { field |= SWITCH_1_MASK; } public void turnOffSwitch1() { field &= ~SWITCH_1_MASK; }}這樣能節省大量空間,在實際應用中,很多地方做了這種優化。最直接的例子就是,Java對象的對象頭:
|-------------------------------------------------------|--------------------|| Mark Word (32 bits) | State ||-------------------------------------------------------|--------------------|| identity_hashcode:25 | age:4 | biased_lock:1 | lock:2 | Normal ||-------------------------------------------------------|--------------------|| thread:23 | epoch:2 | age:4 | biased_lock:1 | lock:2 | Biased ||-------------------------------------------------------|--------------------|| ptr_to_lock_record:30 | lock:2 | Lightweight Locked ||-------------------------------------------------------|--------------------|| ptr_to_heavyweight_monitor:30 | lock:2 | Heavyweight Locked ||-------------------------------------------------------|--------------------|| | lock:2 | Marked for GC ||-------------------------------------------------------|--------------------|7. 位計數
基于6,有時候我們想某個狀態數里面,有多少個狀態是true,就是計算這個狀態數里面多少位是1.
比較樸素的方法就是:先判斷n的奇偶性,為奇數時計數器增加1,然后將n右移一位,重復上面的步驟,直到移位完畢。
高效一點的方法通過:
作者:zhxhash
轉載自:https://my.oschina.net/u/3747772/blog/3155006
總結
以上是生活随笔為你收集整理的java实现次方的运算_Java中对于位运算的优化以及运用与思考的全部內容,希望文章能夠幫你解決所遇到的問題。
                            
                        - 上一篇: 后怎么恢复_爬山后小腿肌肉酸痛怎么办 ?
 - 下一篇: 创建全国文明城市宣传文案40句