位操作基礎#

基本運算子#

Kotlin 的位運算不是符號運算子，而是 Int/Long 上的中綴函式：and、or、xor、inv()、shl、shr、ushr。下表範例用 0b 前綴表示二進位字面值。

XOR 的特殊性質#

XOR（異或）在演算法中極為常用：

// 不使用臨時變數交換 a 和 b
a = a xor b  // a = a^b
b = a xor b  // b = a^b^b = a
a = a xor b  // a = a^b^a = b

三大核心技巧#

判斷奇偶性：x and 1#

最後一位為 1 是奇數，為 0 是偶數。

if ((x and 1) == 1) {
    // 奇數
} else {
    // 偶數
}

x and 1 比 x % 2 更高效（直接位操作 vs 除法運算）。

清除最低位的 1：x and (x - 1)#

將 x 二進位中最右邊的 1 變為 0。

x         = 1010...1000
x-1       = 1010...0111
x and x-1 = 1010...0000

應用：計算二進位中 1 的個數（Hamming Weight）

var count = 0
while (x != 0) {
    x = x and (x - 1)
    count++
}

取得最低位的 1：x and -x#

取出 x 二進位中最右邊的 1（Lowbit）。

x        = ...10100
-x       = ...01100  (補碼 = 取反 + 1)
x and -x = ...00100

應用：樹狀陣列（Binary Indexed Tree）

進階操作#

進行移位操作時，注意整數型態的位數限制和符號位處理，避免溢位或非預期結果。

位操作速記表#

十進位     二進位
   6    =  110
  11    =  1011
  -1    =  1111...1111 (全1，補碼表示)

在二補數表示法中，-1 的二進位表示是全 1（111...111），這是常見的面試考點。

單一位元的四件套#

對「第 i 位」的所有操作，本質上都圍繞同一個工具：把 1 左移到第 i 位做出一個 mask（1 shl i），再用適當的運算子把它套上去。把這四個操作放在一起看，規律就很清楚：

fun get(num: Int, i: Int): Int    = (num shr i) and 1
fun setBit(num: Int, i: Int): Int = num or (1 shl i)
fun clear(num: Int, i: Int): Int  = num and (1 shl i).inv()
fun toggle(num: Int, i: Int): Int = num xor (1 shl i)

重點不是死背這四行，而是理解「mask 怎麼建」。記住三件事就能自己推：1 shl i 把目標位點亮；and mask 用來「篩出／保留」、or mask 用來「設為 1」、xor mask 用來「翻轉」；要把某位清成 0，就把 mask 取反（.inv()）再 and。

常用慣用法#

這些慣用法在面試與競賽裡反覆出現，值得形成肌肉記憶——但更重要的是看懂它們為什麼成立。

判斷是否為 2 的冪#

fun isPowerOfTwo(n: Int): Boolean {
    return n > 0 && (n and (n - 1)) == 0
}

2 的冪在二進位中只有一個 1（如 1000）。而 n and (n - 1) 會清掉最低位的那個 1（減一會把最低位的 1 借成 0、其右側全變 1，再 and 就把這個 1 連同右側一起歸零）。所以若 n 是 2 的冪，清掉唯一的 1 後就變成 0。前面的 n > 0 用來排除 0 與負數。

不用暫存變數交換兩數#

a = a xor b  // a = a^b
b = b xor a  // b = (a^b)^b = a
a = a xor b  // a = (a^b)^a = b

靠的是 XOR 的可逆性（x xor x = 0、x xor 0 = x）：第二步把原本的 a 還原到 b、第三步把原本的 b 還原到 a。這是「同一份資料用可逆運算來回變換、不需額外狀態」的典型案例，與狀態抽象與狀態圖裡用等價變換在狀態間移動的想法一脈相承。

XOR 交換在 a 與 b 是**同一個變數（或別名）**時會把值清成 0，因此實務上仍以暫存變數交換為主，這個技巧的價值在於展示 XOR 的可逆性。

取最低位的 1#

val lowbit = n and -n

-n 是 n 的二補數（取反加一），這使得 n 與 -n 只在「最低位的 1」這一位上同時為 1，and 之後就只留下那一位。例如 n = ...10100，-n = ...01100，n and -n = ...00100。這是樹狀陣列（Binary Indexed Tree）走訪節點的核心操作。

算術右移 vs 邏輯右移#

Kotlin 和 Java、C 一樣是定寬整數語言：Int 固定 32 位、Long 固定 64 位。針對右移，Kotlin 貼心地提供兩個不同的中綴運算子——shr（算術右移） 對負數在高位「補符號位（補 1）」，等同除以 2 並向下取整；ushr（邏輯右移，unsigned shift right） 一律在高位「補 0」，把符號位當成一般的位元。

val x = -8                 // 32-bit 補碼：11111111_11111111_11111111_11111000
println(x shr 1)           // -4，算術右移補符號位，等同 -8 / 2 向下取整
println(x ushr 1)          // 2147483644，邏輯右移高位補 0，把符號位當成一般的 1

Kotlin 的 shr 是算術右移：對負數會補符號位，等同除以 2 並向下取整（注意是向下取整，不是向零取整：-7 shr 1 == -4 而非 -3）。若想要定寬語言的邏輯右移（高位補 0），直接用 ushr 即可——不必像 Python 那樣手動 and 0xFFFFFFFF 遮罩再右移。從 Java/C 移植依賴 >>> 的位運算程式時，把 >>> 直接對應成 Kotlin 的 ushr；別誤用 shr，否則負數的符號位會一路延伸，得到非預期結果——這是跨語言移植位操作最常見的陷阱之一。