二進位計數器（binary counter）

想像一排電燈開關代表一個二進位數，以及一個把它加一的操作。要加一，你把最右邊的 0 翻成 1，並把它右邊每個 1 翻回 0——熟悉的進位。有時只翻一次（1010 加 1 只動一個位元）；有時是長連鎖（0111 加 1 翻四個位元）。攤還分析回答的問題是：在許多次加一中，平均每次加一翻幾個位元？

從 0 開始做 m 次加一，按位元位置數翻轉。第 0 位每次加一都翻：m 次。第 1 位翻的頻率一半（只在第 0 位進位時）：約 m/2 次。第 2 位四分之一：約 m/4。一般地，第 i 位約翻 m/2^i 次。總計 m(1 + 1/2 + 1/4 + ...) < 2m。所以 m 次加一花不到 2m 次翻轉，一次加一的攤還成本不到 2 = O(1)——即使計數器全為 1 時單一次加一可翻動全部 log m 位。記帳觀點：每個 1 位上留 1 存款；設一位花 2（翻轉加存入），進位時清一位免費（由它的存款支付）。位勢觀點：Phi = 1 位個數，對清掉 t 個 1 的加一給出攤還 (t+1) + (1-t) = 2。

二進位計數器是三種攤還方法在同一個 O(1) 答案上一致的最乾淨示範，這正是每本教科書都用它的原因。它模擬真實情境：被加許多次的計數器，或維持二進位表示的回溯方案。誠實的提醒：這 O(1) 只是攤還的。某一次特定加一（把 0111...1 溢位成 1000...0）確實翻動 Theta(log m) 個位元，所以若你需要每一次加一都快，這保證幫不上忙——但對一整段執行的總工作量，這個界恰恰正確。