Java 中對于位運算的優化以及運用與思考

作者：zhxhash

随着JDK的發展以及JIT的不斷優化，我們很多時候都可以寫讀起來易讀但是看上去性能不高的代碼了，編譯器會幫我們優化代碼。之前大學裡面學單片機的時候，由于記憶體以及處理器性能都極其有限（可能很多時候考慮記憶體的限制優先于處理器），是以很多時候，利用位運算來節約空間或者提高性能，那麼這些優秀的思想，放到目前的Java中，是否還有必要這麼做呢？我們逐一思考與驗證下（其實這也是一個關于Premature optimization的界定的思考）

1. 乘法與左移位

左移一位，相當于乘以2，左移n位，相當于乘以2的n次方。

1 << 1 == 1 * 2 //true
1 << n == 1 * pow(2, n) // true

public 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驗證下，添加依賴：

<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-core</artifactId>
<version>1.22</version>
</dependency>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-generator-annprocess</artifactId>
<version>1.22</version>
</dependency>
<!-- https://mvnrepository.com/artifact/site.ycsb/core -->
<dependency>
<groupId>site.ycsb</groupId>
<artifactId>core</artifactId>
<version>0.17.0</version>
</dependency>

實作思路：

被乘數的選擇：被乘數固定為1，或者是一個極小值或者極大值或者是稀疏值（轉換成2進制很多位是0），測試結果沒啥太大的參考意義，是以我們選擇2的n次方減某一數字作為被乘數
乘數生成的性能損耗：乘數是2的随機n次方，生成這個的方式要一緻，我們這裡要測試的僅僅是移位還有乘法運算速度，和實作複雜度沒有關系。實作代碼：

@Benchmark
@Warmup(iterations = 0)
@Measurement(iterations = 300)
public void multiply2_n_shift_not_overflow(Generator generator) {
int result = 0;
int y = 0;
for (int j = 0; j < generator.divide.length; j++) {
//被乘數x為2^n - j
int x = generator.divide[j] - j;
int ri = generator.divide.length - j - 1;
        y = generator.divide[ri];
        result += x * y;
//為了和移位測試保持一緻是以加上這一步
        result += y;
    }
}

@Benchmark
@Warmup(iterations = 0)
@Measurement(iterations = 300)
public void multiply2_n_mul_not_overflow(Generator generator) {
int result = 0;
int y = 0;
for (int j = 0; j < generator.divide.length; j++) {
int x = generator.divide[j] - j;
int ri = generator.divide.length - j - 1;
//為了防止乘法多了讀取導緻性能差異，這裡雖然沒必要，也讀取一下
        y = generator.divide[ri];
        result += x << ri;
//為了防止虛拟機優化代碼将上面的給y指派踢出循環，加上下面這一步
        result += y;
    }
}

測試結果：

Benchmark                 Mode  Cnt         Score         Error  Units
BitUtilTest.multiply2_n_mul_not_overflow    thrpt  300  35882831.296 ±  48869071.860  ops/s
BitUtilTest.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  Units
BitUtilTest.divide2_n_div                   thrpt  300  10219904.214 ±   5787618.125  ops/s
BitUtilTest.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  Units
BitUtilTest.mod2_n_1                        thrpt  300  10632698.855 ±   5843378.697  ops/s
BitUtilTest.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^y
x = 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  Units
BitUtilTest.swap_1  thrpt  300  267787894.370 ± 559479133.393  ops/s
BitUtilTest.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右移一位，重複上面的步驟，直到移位完畢。

高效一點的方法通過：

n & (n - 1) 可以移除最後一位1 （假設最後一位本來是0，減一後必為1，0 & 1為 0，最後一位本來是1，減一後必為0，0 & 1為 0）
移除了最後一位1之後，計數加1，如果結果不為零，則用結果繼續第一步。

int n = Integer.MAX_VALUE;
int count = 0;
while(n != 0) {
n &= n -1;
count++;
}

Java 中對于位運算的優化以及運用與思考

1. 乘法與左移位

2. 除法和右移位

3. “取餘”與“取與”運算

4. 求與數字最接近的2的n次方

5. 交換兩個數字

6. bit狀态位

7. 位計數

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method