Java19 Integer 位操作精解：compress與expand《Hacker‘s Delight》（第二版，7.4節）

`compress(int i, int mask)`?

這個方法是Java 19中新增的一個強大的位操作函數。

compress?方法的核心功能可以理解為 “按位過濾和壓縮” 。

過濾 (Filter): 它使用?mask（掩碼）作為過濾器。對于輸入整數?i，只有那些在?mask?中對應位為?1?的比特才會被保留。
壓縮 (Compress): 它將所有被保留下來的比特，按照它們在?i?中從低到高的原始順序，緊湊地排列到返回值的低位端。

一個直觀的例子

文檔中給出的例子非常經典：compress(0xCAFEBABE, 0xFF00FFF0)

輸入?i:?0xCAFEBABE?->?1100 1010 1111 1110 1011 1010 1011 1110
掩碼?mask:?0xFF00FFF0?->?1111 1111 0000 0000 1111 1111 1111 0000

執行過程:

mask?的高8位是?FF，所以?i?的高8位?CA?被選中。
mask?的次高8位是?00，所以?i?的次高8位?FE?被丟棄。
mask?的次低12位是?FFF，所以?i?的對應12位?BAB?被選中。
mask?的最低4位是?0，所以?i?的最低4位?E?被丟棄。
選中的比特?CA、B、AB?被按順序緊湊地排列，得到?0x000CABAB。

`expand`

public static int expand(int i, int mask)?是一個靜態方法，用于根據一個給定的掩碼?mask?來“擴展”或“解壓縮”整數?i?的位（bits）。這個操作可以看作是?Integer.compress(int i, int mask)?方法的逆過程。

核心功能：對于?mask?中每一個為?1?的位，該方法會從輸入整數?i?中按順序（從最低位開始）取一個位，并將其放置到結果中與?mask?中那個?1?位對應的位置。結果中所有對應?mask?中?0?位的位置都將被清零。

Javadoc 注釋解析與示例

我們先來看一下該方法的 Javadoc 注釋，特別是它給出的示例，這有助于直觀地理解其功能。

// ... existing code ...* @apiNote* Consider the simple case of expanding the digits of a hexadecimal* value:* {@snippet lang="java" :* expand(0x0000CABAB, 0xFF00FFF0) == 0xCA00BAB0* }* Starting from the least significant hexadecimal digit at position 0* from the right, the mask {@code 0xFF00FFF0} selects the first five* hexadecimal digits of {@code 0x0000CABAB}. The selected digits occur* in the resulting expanded value in order at positions 1, 2, 3, 6, and 7.
// ... existing code ...

讓我們來分解這個例子：

輸入?i:?0x0000CABAB
掩碼?mask:?0xFF00FFF0
預期結果:?0xCA00BAB0

分析過程：

mask?(0xFF00FFF0) 的二進制形式定義了哪些位是“有效”的目標位置。它的十六進制表示中，值為?F?的位置（第1, 2, 3, 6, 7位）代表了目標位置。
i?(0x0000CABAB) 是源數據。我們從?i?的最低位開始，依次取出位。
expand?操作會將?i?的位填充到?mask?指定的有效位置中：
- i?的最低的4位是?B?(1011)，它被放置在?mask?第一個有效區域（十六進制位 1），結果的?...xxxB0?部分形成。
- i?的接下來4位是?A?(1010)，它被放置在?mask?第二個有效區域（十六進制位 2），結果的?...xxAB0?部分形成。
- i?的再接下來4位是?B?(1011)，它被放置在?mask?第三個有效區域（十六進制位 3），結果的?...xBABA0?部分形成。
- mask?的第4、5位是?00，所以結果的對應位置也是?00。
- i?的再接下來4位是?A?(1010)，它被放置在?mask?第四個有效區域（十六進制位 6），結果的?...A00BAB0?部分形成。
- i?的最后4位是?C?(1100)，它被放置在?mask?第五個有效區域（十六進制位 7），最終形成?0xCA00BAB0。

Javadoc 還提到了一個關鍵恒等式：expand(compress(x, m), m) == x & m。這清晰地表明?expand?和?compress?是一對互逆的操作。

源碼解析：compress和expand是如何實現的？

實現源自經典著作《Hacker's Delight》（第二版，7.4節），是一種不包含分支和循環（Java代碼中的for循環在編譯后會展開）的高效并行算法。

以下分析改自?《Hacker's Delight》（第二版，7.4節）

compress

分步移動的數學原理??

??總體目標??：
每個位需右移的距離 = 該位對應mask ??右側 0 的數量??（記為?d）
??分治策略??：
將?d拆解為二進制分量，分 5 輪處理：
d = d? + 2×d? + 4×d? + 8×d? + 16×d? (其中 d? ∈ {0,1} 是二進制系數)
- ??第 j 輪??：處理 ??2??? 的權重分量
- ??移動條件??：當輪需移動的位 =?d二進制展開中 ??2? 的系數 d? 為 1?? 的位

??示例??：某位需移動?d=6（二進制?110）
第一輪（j=0）：移動?2?=1位（因?d?=0→ ??不移動??)
第二輪（j=1）：移動?21=2位（因?d?=1→ ??移動??)
第三輪（j=2）：移動?22=4位（因?d?=1→ ??移動??)

源碼：

    @IntrinsicCandidatepublic static int compress(int i, int mask) {// See Hacker's Delight (2nd ed) section 7.4 Compress, or Generalized Extracti = i & mask; // Clear irrelevant bitsint maskCount = ~mask << 1; // Count 0's to rightfor (int j = 0; j < 5; j++) {// Parallel prefix// Mask prefix identifies bits of the mask that have an odd number of 0's to the rightint maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove = maskPrefix & mask;// Compress maskmask = (mask ^ maskMove) | (maskMove >>> (1 << j));// Bits of i to be movedint t = i & maskMove;// Compress ii = (i ^ t) | (t >>> (1 << j));// Adjust the mask count by identifying bits that have 0 to the rightmaskCount = maskCount & ~maskPrefix;}return i;}

假設輸入為：
x = abcd efgh ijkl mnop qrst uvwx yzAB CDEF，（Java代碼里的 i ）
m = 1000 1000 1110 0000 0000 1111 0101 0101，

其中 x 中的每個字母代表一個比特（值為 0 或 1）。

x 中對應的比特向右移動位數?等于該比特右邊 m 中 0 的數量。

首先清除 x 中不相關的比特會很方便，得到：
x = a000 e000 ijk0 0000 0000 uvwx 0z0B 0D0F。

首先確定哪些比特需要（向右）移動奇數個位置，并將它們移動一個比特位。??
這可以通過計算 mk = ~m << 1 并對結果執行 parallelSuffix 來完成。

得到：
mk = 1110 1110 0011 1111 1110 0001 0101 0100，
mp = 1010 0101 1110 1010 1010 0000 1100 1100。

可以觀察到，

mk 標識了 m 中緊鄰右側是 0 的比特位，
mp 從右到左對這些位進行模 2 加法（parallelSuffix）。

因此，mp 標識了 m 中右側有奇數個 0 的比特位。

??將要移動一個位置的比特是那些位于嚴格右側有奇數個 0 的位置（由 mp 標識）并且在原始掩碼中為 1-比特的位。??

這可以簡單地通過 mv = mp & m 計算得出：
mv = 1000 0000 1110 0000 0000 0000 0100 0100。

m 的這些比特可以通過賦值語句移動：
m = (m ^ mv) | (mv >> 1);

x 的相同比特可以通過兩個賦值語句移動：
t = x & mv;
x = (x ^ t) | (t >> 1);

（移動 m 的比特更簡單，因為所有選中的比特都是 1。）

這里的異或操作是關閉 m 和 x 中已知的 1-比特，而或操作是打開 m 和 x 中已知的 0-比特。
這些操作也可以分別替換為異或，或者減法和加法。

??將由 mv 選擇的比特向右移動一個位置后，結果是：??
m = 0100 1000 0111 0000 0000 1111 0011 0011，
x = 0a00 e000 0ijk 0000 0000 uvwx 00zB 00DF。

??現在我們必須為第二次迭代準備一個掩碼，在這次迭代中，我們識別要向右移動 2 的奇數倍位置的比特。??

注意，mk & ~mp 這個量標識了那些在原始掩碼 m 中緊鄰右側有偶數?0 的比特。【因為奇數0的位置被刪除了】

這個量如果從右側用?parallelSuffix 求和，就能識別出那些向右移動 2 的奇數倍（2, 6, 10 等）位置的比特。
因此，該過程就是將這個量賦給 mk ，并執行上述步驟的第二次迭代。

??修訂后的 mk 值為：??
mk = 0100 1010 0001 0101 0100 0001 0001 0000。

expand

compress的逆向移動

public static int expand(int i, int mask) {// Save original maskint originalMask = mask;// Count 0's to rightint maskCount = ~mask << 1;int maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove1 = maskPrefix & mask;// Compress maskmask = (mask ^ maskMove1) | (maskMove1 >>> (1 << 0));maskCount = maskCount & ~maskPrefix;maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove2 = maskPrefix & mask;// Compress maskmask = (mask ^ maskMove2) | (maskMove2 >>> (1 << 1));maskCount = maskCount & ~maskPrefix;maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove3 = maskPrefix & mask;// Compress maskmask = (mask ^ maskMove3) | (maskMove3 >>> (1 << 2));maskCount = maskCount & ~maskPrefix;maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove4 = maskPrefix & mask;// Compress maskmask = (mask ^ maskMove4) | (maskMove4 >>> (1 << 3));maskCount = maskCount & ~maskPrefix;maskPrefix = parallelSuffix(maskCount);// Bits to moveint maskMove5 = maskPrefix & mask;int t = i << (1 << 4);i = (i & ~maskMove5) | (t & maskMove5);t = i << (1 << 3);i = (i & ~maskMove4) | (t & maskMove4);t = i << (1 << 2);i = (i & ~maskMove3) | (t & maskMove3);t = i << (1 << 1);i = (i & ~maskMove2) | (t & maskMove2);t = i << (1 << 0);i = (i & ~maskMove1) | (t & maskMove1);// Clear irrelevant bitsreturn i & originalMask;}

`parallelSuffix(int maskCount)`

這個方法是?Integer.compress?和?Integer.expand?的核心輔助函數。它的名字雖然叫?parallelSuffix（并行后綴），其實現的是一種“并行后綴異或掃描”算法。

代碼把變量命名為 maskPrefix，這是一個不恰當的命名

此方法計算一個“后綴”，但使用的不是加法，而是^（按位異或）運算。對于返回結果?maskPrefix?中的任意比特位?k，它的值等于輸入?maskCount?中從第?0?位到第?k?位所有比特的異或總和。

result[k] = maskCount[0] ^ maskCount[1] ^ ... ^ maskCount[k]

該算法采用分治策略，在對數時間內完成計算：

// ... existing code ...@ForceInlineprivate static int parallelSuffix(int maskCount) {// 步驟1: 計算相鄰比特的異或和int maskPrefix = maskCount ^ (maskCount << 1);// 步驟2: 計算相鄰2比特塊的異或和maskPrefix = maskPrefix ^ (maskPrefix << 2);// 步驟3: 計算相鄰4比特塊的異或和maskPrefix = maskPrefix ^ (maskPrefix << 4);// 步驟4: 計算相鄰8比特塊的異或和maskPrefix = maskPrefix ^ (maskPrefix << 8);// 步驟5: 計算相鄰16比特塊的異或和maskPrefix = maskPrefix ^ (maskPrefix << 16);return maskPrefix;}
// ... existing code ...

maskPrefix = maskCount ^ (maskCount << 1);: 第一步，每個比特位與它右邊（低位）的比特進行異或。現在每個比特位存儲了它自己和右邊鄰居的異或結果。
maskPrefix = maskPrefix ^ (maskPrefix << 2);: 第二步，將相鄰的2比特塊進行異或。這會把之前的結果組合起來，現在每個比特位存儲了原始值中連續4個比特的異或和。
后續步驟: 這個過程不斷重復，塊的大小翻倍（4, 8, 16），直到最終每個比特位都包含了從最低位到當前位所有比特的異或總和。

在?compress?和?expand?方法中，需要將源整數中的某些位根據掩碼（mask）移動到新的位置。這個移動的距離不是固定的。parallelSuffix?的作用就是高效地、并行地計算出所有需要移動的位應該移動多遠，是實現這兩個復雜位操作算法的關鍵基石。

@ForceInline?注解建議JIT編譯器將這個短小精悍的函數直接內聯到調用它的地方（compress和expand），以消除函數調用的開銷，追求極致性能。