您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 使用技巧 >> iOS 技巧大全

以值求冪:用位移運算拆解整數的二進位組成

編輯:iOS 技巧大全

有些數值是以 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 的個數,效率比逐位檢查更好。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved