演算法圖鑑
演算法 · 4 個細項

Bit Manipulation位元運算

整數在記憶體裡就是一串位元。AND、OR、XOR、移位這幾個運算都是單一 CPU 指令，用對了能把某些問題壓到常數時間，也能用一個整數表示一整個集合。

為什麼要學 Bit Manipulation

現實中的應用
權限與功能開關

讀、寫、執行各佔一個位元，一個整數就存完所有權限。Unix 的 chmod 755、遊戲的狀態旗標都是這樣存。

→ 對應課程：Bitwise Basics
找出落單的那一個

一組資料每個都出現兩次，只有一個出現一次。全部 XOR 起來，成對的互相抵消，剩下的就是答案，不用任何額外記憶體。

→ 對應課程：XOR Tricks
網路遮罩與雜湊

IP 的子網路遮罩、雜湊表的取模用 AND 代替、布隆過濾器，底層都是位元運算。

→ 對應課程：Counting Bits

細項

4 篇
#演算法難度
01Bitwise Basics 基本運算AND / OR / XOR / NOT / 移位，取位、設位、清位用在：權限旗標、硬體暫存器、壓縮儲存02XOR Tricks XOR 技巧a ^ a = 0、a ^ 0 = a，交換與抵消用在：Single Number、缺少的數字、不用暫存變數的交換03Counting Bits 位元計數Brian Kernighan 的 n & (n−1)用在：漢明距離、population count04Subset Enumeration 位元列舉子集0 到 2ⁿ−1 每個整數就是一個子集用在：小規模組合問題、Bitmask DP 的前置