这题有一些要点
1.不能用乘法 2.不能用循环 3. 不能用if来终止递归
其实不能用乘法也是可以用位运算来做乘法的
比如5*3,实际上是5*(11)(二进制) = 1*(5 << 1) + 1*(5 << 0);
5*6,实际上是 5*(110) = 1*(5<<2) + 1*(5<<1) + 0*(5 << 0);
所以可以将一个乘数按照二进制展开
int sumNums(int n) {int n0 = (n & -(n+1 >> 0 & 1)) << 0;int n1 = (n & -(n+1 >> 1 & 1)) << 1;int n2 = (n & -(n+1 >> 2 & 1)) << 2;int n3 = (n & -(n+1 >> 3 & 1)) << 3;int n4 = (n & -(n+1 >> 4 & 1)) << 4;int n5 = (n & -(n+1 >> 5 & 1)) << 5;int n6 = (n & -(n+1 >> 6 & 1)) << 6;int n7 = (n & -(n+1 >> 7 & 1)) << 7;int n8 = (n & -(n+1 >> 8 & 1)) << 8;int n9 = (n & -(n+1 >> 9 & 1)) << 9;int n10 = (n & -(n+1 >> 10 & 1)) << 10;int n11 = (n & -(n+1 >> 11 & 1)) << 11;int n12 = (n & -(n+1 >> 12 & 1)) << 12;int n13 = (n & -(n+1 >> 13 & 1)) << 13;return (n0+n1+n2+n3+n4+n5+n6+n7+n8+n9+n10+n11+n12+n13) >> 1;}
即,不用乘号做乘法