1.概述

（1）位運算是一種直接對二進制位進行操作的運算方式。它們是在計算機中對數據的底層操作，通常在位級別上進行，不考慮數據的整體值。在 Java 中，位運算符有以下幾種：

• 與運算 (&)：對兩個操作數的每一位進行與操作，只有當對應的位都為 1 時，結果為 1，否則為 0。
• 或運算 (|)：對兩個操作數的每一位進行或操作，只要對應的位至少有一個為 1，結果為 1，否則為 0。
• 異或運算 (^)：對兩個操作數的每一位進行異或操作，只有當對應的位不同時，結果為 1，否則為 0。
• 取反運算 (~)：對一個操作數的每一位進行取反操作，將 0 變為 1，將 1 變為 0。
• 左移運算 (<<)：將一個操作數的所有位向左移動指定的位數，低位補 0。
• 右移運算 (>>)：將一個操作數的所有位向右移動指定的位數，高位的處理取決于具體情況。
• 無符號右移運算 (>>>)：將一個操作數的所有位向右移動指定的位數，高位總是補 0。

（2）位運算常用于編程中的一些特定場景，如位掩碼、位集合操作、優化算法、設計以及操作硬件等。它們在處理位級別的數據和優化性能方面非常有用。

有關位運算的更多技巧，可以參考 Bit Twiddling Hacks。

2.位運算技巧

2.1.與運算 (&)

2.1.1.判斷奇偶性

判斷奇偶性：位運算中最低位為 1 表示奇數，為 0 表示偶數。

(n & 1) == 1	// n 為奇數
(n & 1) == 0	// n 為偶數

2.1.2.判斷一個數是否是 2 的冪

如果一個數是 2 的冪，那么它的二進制形式中只有最高位為 1，其他位都是 0。

(n & (n - 1)) == 0	// x 是 2 的冪
(n & (n - 1)) == 1	// x 不是 2 的冪

n & (n - 1) 的作用是消除數字 n 的二進制表示中的最后一個 1。因此，如果 n 是 2 的冪，那么 n 的二進制表示中只有一個 1，所以 n & (n - 1) 的結果必為 0。

2.1.3.將英文字母轉換為大寫

我們可以通過將小寫字母與下劃線 ‘_’ 進行與操作，將其轉換為對應的大寫字母。

(char) ('n' & '_') = 'N'
(char) ('N' & '_') = 'N'[添加鏈接描述](https://xgqngu.blog.csdn.net/article/details/130137431)

• 在位運算中，字符在內存中以數字的形式表示。在大部分字符編碼中（如 ASCII 碼），大寫字母的編碼值比小寫字母的編碼值要小；
• 在 ASCII 編碼中，大寫字母和小寫字母的 ASCII 碼值之間的差值為固定的 32（或二進制的 0010 0000），例如，字母 ‘A’ 的 ASCII 碼值為 65，而字母 ‘a’ 的 ASCII 碼值為 97，它們之間的差值就是 32。
• 而 ‘_’ 的二進制表示為 0101 1111，小寫字母 a-z 的 ASCII 值范圍為 97-122，即 0110 0001-0011 1101；
• 那么小寫字母與 ‘_’ 相與后，相當于其對應 ASCII 值減少了 32，因此也就轉換為了對應的大寫字母。

2.1.4.代替取模運算

（1）一般來說，我們要求 h 除以 n 的余數，會通過取模運算 (%)，即 h % n。但當 n 是 2 的冪次方時，我們可以使用位運算來代替取模運算，從而達到提高計算效率的目的，即：

h % n == hash & (n - 1)	// n 是 2 的冪次方

（2）當 n 是 2 的冪次方時，它的二進制表示為 100…00（n 個 0）。這意味著 n - 1 的二進制表示為 011…11（n 個 1）。因此，按位與運算 h & (n - 1) 實際上是將 h 的二進制表示的最后 n 位保留，其他位都設為 0，起到了取模的效果。

（3）在這種情況下進行替換有一些具體的應用場景，例如 HashMap 中數組 table 長度被設置為 2 的 n 次方中的一個目的就是上面提到的提高計算效率，具體細節可以參考 Java 基礎——HashMap 底層數據結構與源碼分析這篇文章中的 3.1 章節。

2.2.或運算 (|)

2.2.1.將英文字母轉換為小寫

我們可以通過將大寫字母與空格 ’ ’ 進行或操作，將其轉換為對應的小寫字母。

(char) ('N' | ' ') = 'n'
(char) ('n' | ' ') = 'n'

• 其原理與上面的通過與操作將英文字符轉換為大寫類似，空格字符在 ASCII 編碼中的值為 32（十進制），其二進制表示為 0010 0000。
• 而大寫字母 A-Z 的 ASCII 值范圍為 65-90，即 0110 0001-0011 1101；
• 那么大寫字母與 ’ ’ 相或后，相當于其對應 ASCII 值增加了 32，因此也就轉換為了對應的小寫字母。

2.3.異或運算 (^)

2.3.1.消除成對相同的數

（1）異或運算有兩個非常重要的性質：

• 一個數和 0 做異或運算的結果為它本身，即 a ^ 0 = a。
• 一個數和它本身做異或運算結果為 0，即 a ^ a = 0；

（2）其中，第二條性質明顯有一個重要的用途，即消除成對相同的數，如果再結合異或運算的交換律，那么我們可以很迅速地解決 136.只出現一次的數字這題，即給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

class Solution {public int singleNumber(int[] nums) {int single = 0;/*對于本題，只要把所有數字進行異或，成對的數字就會變成 0，落單的數字和 0 做異或還是它本身，所以最后異或的結果就是只出現?次的元素。*/for (int num : nums) {single ^= num;}return single;}
}

268.丟失的數字 這題也可以通過這個技巧來解決。

2.3.2.不使用臨時變量來交換兩個數

int a = -1;
int b = 2;
a ^= b;
b ^= a;
a ^= b;
System.out.println("a = " + a);     // a = 2
System.out.println("b = " + b);     // b = -1

其實，上面不使用臨時變量來交換兩個數是基于 a ^ a = 0 這一性質實現的，具體推導過程如下：

a ^= b;		// a1 = a ^ b
b ^= a;		// b1 = b ^ a1 = b ^ (a ^ b) = a
a ^= b;		// a2 = a1 ^ b1 = (a ^ b) ^ a = b

2.3.3.進行英文字母大小寫互換

(char) ('n' ^ ' ') = 'N'
(char) ('N' ^ ' ') = 'n'

• 其原理與上面的通過與操作將英文字符轉換為大寫類似，空格字符在 ASCII 編碼中的值為 32（十進制），其二進制表示為 0010 0000。
• 而大寫字母 A-Z 的 ASCII 值范圍為 65-90，即 0110 0001-0011 1101；
• 而小寫字母 a-z 的 ASCII 值范圍為 97-122，即 0110 0001-0011 1101；
• 大小寫字母與 ’ ’ 相異后，小寫字母對應 ASCII 值減少了 32，大寫字母對應 ASCII 值增加了 32，因此也就進行了英文字母大小寫互換。

2.3.4.判斷兩個數是否異號

計算機底層中整數通常使用補碼來表示，通過位運算判斷兩個數是否異號的原理是就是利用了補碼表示中最高位符號位的特性。默認情況下，整數的最高位為符號位，0 表示正數，1 表示負數。通過位運算判斷兩個數是否異號的步驟如下：

• 對兩個數進行異或運算 (^)。異或運算的結果在二進制表示中，兩個數對應位相同則為 0，相異則為 1。
• 如果結果小于 0，則說明這兩個數異號；如果結果大于 0，則說明這兩個數同號。

int a = 1;
int b = 2;
System.out.println(((a ^ b) < 0));  // false，a 和 b 同號int c = -1;
int d = 2;
System.out.println(((c ^ d) < 0));  // true，a 和 b 異號

2.4.取反運算 (~)

2.4.1.自增

int n = 2;
n = -~n;
System.out.println(n);	// 3

2.4.2.自減

int n = 2;
n = ~-n;
System.out.println(n);	// 1

2.5.移位運算 (<<、>>、>>>)

2.5.1.乘以 2

在二進制表示中，將一個數乘以 2 就等于將它向左移動 1 位，低位補 0。

int n = 3;
n <<= 1;
System.out.println(n);		// 6

2.5.2.除以 2

在二進制表示中，將一個數乘以 2 就等于將它向右移動 1 位，高位補符號位。

int n = 4;
n >>= 1;
System.out.println(n);		// 2

更多有關 Java 中移位運算符的細節可以參考 Java 基礎面試題——運算符這篇文章。

3.應用

大家可以去 LeetCode 上找相關的位運算的題目來練習，或者也可以直接查看 LeetCode 算法刷題目錄 (Java) 這篇文章中的位運算章節。如果大家發現文章中的錯誤之處，可在評論區中指出。