求1到n的和

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解答

最简单用递归的思想，使用tmp>0切断递归

public int Sum_Solution(int n) {
        int tmp = n;
        boolean b=tmp >0 && (1==(tmp += (Sum_Solution(n - 1))));
        return tmp;
    }

网上题解

链接：https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1?f=discussion
来源：牛客网

总结前面大牛们的方法，提供java的两种阶梯思路：

共同点：

一，利用利用短路 && 来实现 if的功能；

二，利用递归来实现循环while的功能

不同点：

方法一：递归实现1+2+..+n;

方法二：n(n+1)/2,递归实现n(n+1)；

方法三，利用Math实现n(n+1)

关于如何递归实现a*b，有大佬总结过，我搬下来：利用位运算来做，快速幂，快速模乘,

原理是把a拆成2的幂的和，a = 2^e0 + 2^e1 + 2^e2….
那么 a * b = (2^e0 + 2^e1 + 2^e2+…) * b

= b * 2^e0 + b * 2^e1 + b * 2^e2 + …
= (b << e0) + (b << e1) + ….
接下来看代码：

方法一：递归实现1+2+..+n;

public static int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && ((sum += Sum_Solution(--n)) > 0);
        return sum;
    }

方法三，利用Math实现n(n+1)

1
2
3

public static int Sum_Solution1(int n) {
       return (int) (Math.pow(n, 2) + n) >> 1;
}

方法二：n(n+1)/2,递归实现n(n+1)；

先参考使用while的例子，再转换

原理是把a拆成2的幂的和，a = 2^e0 + 2^e1 + 2^e2….

那么 a * b = (2^e0 + 2^e1 + 2^e2+…) * b

= b * 2^e0 + b * 2^e1 + b * 2^e2 + …
= (b << e0) + (b << e1) + ….

public static int Sum_Solution2(int n) {
        int res = 0;
        int a = n;//若a=2=10
        int b = n + 1;//b=3=11
        while (a != 0) {
            if ((a & 1) == 1)//a在第二位==1的时候才更新res=0+110=6
                res += b;
            a >>= 1;//a右移1位 1
            b <<= 1;//b左移动1位 110
        }
        return res>>=1;//n(n+1)/2     
 }

接下来，用(a & 1) == 1和(a != 0)来代替判断语句

public int Sum(int n) {
       int res = multi(n, n + 1);//n*(n-1)
       return res>>=1;//n*(n-1)/2
   }
    
   private int multi(int a, int b) {
       int res = 0;
       //循环体内部, if ((a & 1) == 1), res += b;
       boolean flag1 = ((a & 1) == 1) && (res += b) > 0;
       a >>= 1;
       b <<= 1;
       // while (a != 0) {}循环条件
       boolean flag2 = (a != 0) && (res += multi(a,b)) > 0 ;
       return res;
   }