有些數值是以 2 的冪次相加組成的:
5 = 2^0 + 2^2 40 = 2^3 + 2^5
現在的問題是:給定 40,如何反推出它由 2^3 與 2^5 組成?
這其實就是「把十進位數轉成二進位」的過程。對 2 取餘數可以判斷目前這一位是 0 還是 1;若為 1,代表該位對應的 2 的冪次存在。接著把數字右移一位(除以 2)並把位數計數加一,重複直到數字變為 0。
int main(int argc, char *argv[]) {
@autoreleasepool {
int bit = 0;
int number = 40;
while (number != 0) {
int i = number % 2; // 取出目前最低位
if (i == 1) {
printf("2^%d\n", bit);
}
/**
* 右移一位:除以 2;左移則是乘以 2
*/
number = number >> 1;
bit++;
}
return UIApplicationMain(argc, argv, nil,
NSStringFromClass([AppDelegate class]));
}
}
輸入 40 會印出 2^3 與 2^5,與預期一致。
這個技巧不只用在解題。判斷某一位是否為 1 更直覺的寫法是位元運算 (number >> bit) & 1 或 number & (1 << bit);若要收集所有為 1 的位,也可以反覆用 number &= number - 1 把最低位的 1 消除,迴圈次數即為 1 的個數,效率比逐位檢查更好。