在 Java 中翻轉數字的位
1. 概述
位元操作是程式設計中的一個基本概念,它涉及對二進位資料的各個位元進行操作。一個常見的操作是將整數中的所有位元翻轉,即將所有0轉換為1 ,將所有1轉換為0 。
在本教程中,我們將解釋位元翻轉的含義,並探討幾種用於翻轉整數位元的 Java 方法。為了完整起見,我們將介紹完整的 32 位元翻轉以及僅翻轉有效位元兩種方法。
2. 理解比特翻轉
在學習如何翻轉整數中的位元之前,最好先看一個直觀的例子。
首先,我們來考慮十進制數21 ,更具體地說,是它的二進位表示:
10101
目標是將每一位取反,使每個0變為1 ,每個1變為0 :
01010
這對應於十進制值10 ( 8+2 )。
在這個轉換過程中,原數中位置i的每一位在結果中都會被反轉。然而,這裡有一個重要的區別。當我們翻轉一個整數的全部 32 位元(即它的全部長度)時,結果與只翻轉有效位的結果不同。例如,由於二進位補碼表示法,翻轉整數21的全部 32 位元會得到-22 ,而只翻轉有效位元( 10101 -> 01010 )則會得到10 。
接下來,我們將詳細探討這兩種情況。
3. 使用位元非運算符
翻轉二進位位元最直接的方法是使用位元非運算子~ 。這個一元運算子會反轉整數二進位表示中的每一位:
public static int flipAllBits(int n) {
return ~n;
}
此運算子會翻轉整數的所有 32 位元。這表示~會反轉每一位,包括前導零,由於 Java 中使用了二進位補碼表示法,因此會將正數變成負數。
讓我們使用 JUnit 5 測試和 AssertJ 匹配器來驗證結果:
@Test
void givenPositiveInteger_whenFlipAllBits_thenReturnsNegativeComplement() {
assertThat(flipAllBits(21)).isEqualTo(-22);
assertThat(flipAllBits(0)).isEqualTo(-1);
assertThat(flipAllBits(-1)).isEqualTo(0);
}
我們可以看到,將21的所有 32 位翻轉後得到的是-22 ,而不是10這是因為 Java 的int型別是有符號的 32 位元整數。
要將21變成10 ,我們只需要翻轉有效位元。接下來我們來討論這種情況。
4. 只翻轉有效位
在許多實際場景中,我們只想翻轉數字二進位表示中實際使用的位,不包括前導零。例如,翻轉21 ( 10101 ) 的有效位元應該得到10 ( 01010 )。
4.1. 使用帶位長度計算的遮罩
想法很簡單:我們建立一個掩碼,其中每個有效位元位置都為1 ,然後將該數字與此掩碼進行異或運算。異或運算只會翻轉遮罩中為1位元:
public static int flipSignificantBits(int n) {
if (n == 0) {
return 0;
}
int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
int mask = (1 << bitLength) - 1;
return n ^ mask;
}
首先,我們處理n為0特殊情況。然後,我們使用Integer.numberOfLeadingZeros()計算有效位數。有了這個值,我們透過將1左移bitLength個位置並減去1來創建一個掩碼,從而得到一個與有效位數匹配的 1 序列。
最後,異或運算( ^ )只翻轉有效位,因為與1或會反轉一位,而與0異或則保持不變。
讓我們透過測試來驗證這一點:
@Test
void givenPositiveInteger_whenFlipSignificantBits_thenReturnsFlippedValue() {
assertThat(flipSignificantBits(21)).isEqualTo(10);
assertThat(flipSignificantBits(26)).isEqualTo(5);
assertThat(flipSignificantBits(0)).isEqualTo(0);
assertThat(flipSignificantBits(1)).isEqualTo(0);
assertThat(flipSignificantBits(7)).isEqualTo(0);
}
為了說明這一點,讓我們來追蹤數字26 (二進位11010 )的例子:
n = 11010 (26)
mask = 11111 (31)
n ^ mask = 00101 (5)
這種方法可以有效且有效率地只翻轉有效位。
4.2. 使用Integer.highestOneBit()
我們也可以使用內建的Integer.highestOneBit()方法來建立遮罩。此方法傳回一個僅設定了輸入值最高位的值:
public static int flipSignificantBitsUsingHighestOneBit(int n) {
if (n == 0) {
return 0;
}
int mask = (Integer.highestOneBit(n) << 1) - 1;
return n ^ mask;
}
這裡, Integer.highestOneBit(n)傳回最高有效位元的值。**將其左移一位並減1 ,即可建立一個掩碼,其中每個有效位元都為1**然後,對該遮罩進行異或運算,再次僅翻轉這些位元。
4.3. 使用遮罩進行位元非運算
除了異或運算,我們還可以將位元非運算子與遮罩結合使用,以獲得相同的結果:
public static int flipSignificantBitsUsingNot(int n) {
if (n == 0) {
return 0;
}
int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
int mask = (1 << bitLength) - 1;
return ~n & mask;
}
該函數首先計算n的位元非(NOT)運算,這將翻轉所有 32 位元。然後,與遮罩進行位元與(AND)運算,將除有效位元之外的所有位置零。簡而言之,結果相當於僅翻轉有效位元。
5. 其他方法
除了標準的位元運算子之外,還有其他一些非常規的方法可以翻轉整數的所有 32 位元。
5.1. 使用算術取反
由於採用二進位補碼表示法,翻轉n的所有位元等價於計算-n – 1 :
public static int flipBitsArithmetic(int n) {
return -n - 1;
}
這是因為,在二進位補碼中, n的取反等於按位元取反加1 ( -n = ~n + 1 )。因此, ~n = -n – 1 ,這與位元取反運算子的結果相同。
5.2. 使用異或運算與-1
另一種翻轉所有位元的方法是將該數與-1進行異或運算。在二進位中,我們用全 1 表示-1 (32 位元二進位表示為11111111…1 )。值得注意的是, ~0計算結果也是-1 ,因此我們可以交替使用這兩種方法:
public static int flipBitsXorMinusOne(int n) {
return n ^ -1;
}
由於與1進行異或運算會翻轉一位,因此與所有位元均為1值進行異或運算實際上會翻轉整數中的每一位。這會產生與 ~ 運算子相同的結果。
6. 結論
本文探討了Java中翻轉整數位的幾種方法。首先,我們介紹了使用位元非運算子(NOT)進行完整的32位元翻轉。接下來,我們研究了基於遮罩的方法,利用異或(XOR)和與(AND)運算僅翻轉有效位元。最後,我們介紹了使用算術取反和異或運算的替代方法。
和以往一樣,所有原始碼都可以 在 GitHub 上找到。