題⽬描述

求 1+2+3+...+n ，要求不能使⽤乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等關鍵字及條件判斷語句（ A?B:C ）。

示例
輸⼊：5
輸出：15

思路及解答

用for循環

這個問題，如果直接使⽤ for 循環，超級簡單，重拳出擊，時間複雜度為 O(n) 。代碼如下：

public class Solution {
    public int Sum_Solution(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }
}

可是上⾯的明顯違反了使⽤for 循環的原則

乘除法

試試公式法， 1+2+3+...+(n-1)+n = n * (n+1)/2 ,

public class Solution {
    public int Sum_Solution(int n) {
        if (n >= 0) {
            return n * (n + 1) / 2;
        }
        return 0;
    }
}

但是上⾯的做法，同樣是使⽤乘法，也違反了原則，那麼要不使⽤循環，也不適⽤乘法，怎麼做呢？

遞歸

遞歸可以模擬出循環，⼏乎所有的for 循環操作，都可以以遞歸的⽅式實現。每⼀次遞歸，我們讓n 減少1 ，直到減少為0 。

public class Solution {
    public int Sum_Solution(int n) {
        if (n >= 0) {
            return n + Sum_Solution(n - 1);
        }
        return 0;
    }
}

• 時間複雜度為O(n)
• 空間複雜度也是O(n)

位運算乘法

位運算乘法法：通過位運算實現乘法操作

思路：將n(n+1)用位運算實現，然後右移1位代替除以2

public class Solution {
    public int sum(int n) {
        // 計算n*(n+1) using bit manipulation
        int result = multiply(n, n + 1);
        // 右移1位相當於除以2
        return result >> 1;
    }
    
    /**
     * 位運算實現乘法：利用俄羅斯農民算法
     * 原理：a * b = (a << i)的和，其中i對應b中為1的位
     */
    private int multiply(int a, int b) {
        int result = 0;
        
        // 當a不為0時繼續循環
        while (a != 0) {
            // 如果a的最低位是1，則加上對應的b值
            if ((a & 1) != 0) {
                result += b;
            }
            // a右移1位，b左移1位
            a >>= 1;
            b <<= 1;
        }
        
        return result;
    }
    
    // 無循環的位運算乘法版本（符合要求）
    public int sumNoLoop(int n) {
        int res = multi(n, n + 1);
        return res >> 1;
    }
    
    private int multi(int a, int b) {
        int res = 0;
        // 通過多個位判斷代替循環
        res += ((a & 1) == 1) ? b : 0;
        a >>= 1;
        b <<= 1;
        
        res += ((a & 1) == 1) ? b : 0;
        a >>= 1; 
        b <<= 1;
        
        // 繼續處理更多位...（根據n的範圍確定需要處理的位數）
        return res;
    }
}

• 時間複雜度：O(log n) - 取決於數字的位數
• 空間複雜度：O(1)

案例解析：

計算 13 × 9:
13 = 1101(二進制)
9 = 1001(二進制)

13 × 9 = 13 × (1 + 0 + 0 + 1) 按位展開
       = (13<<0) + (13<<3) 對應9中為1的位
       = 13 + 104 = 117