首页 > 代码库 > 也谈1+2+3+...+n的解答
也谈1+2+3+...+n的解答
据说某个公司有道笔试题是这样的：
求1+2+3+...+n，编程实现，但是不允许用if,while,for,?等语句，也不能用乘除法。当然肯定也不允许用pow这样的函数了。
我们都知道，1+2+3+...+n=n*(n+1)/2=(n*n+n)/2,一个数除以2，等于右移1位。比如4（二进制为100），右移1位则为2（二进制为10）。由于不能用乘除法，所以需要将n*n转换为加减法了。
回忆一下乘法的竖式计算方法，假设101×101，如下图所示：
1 0 1
1 0 1
———
1 0 1
0 0 0
1 0 1
------------------
1 0 2 0 1
则其计算过程就是一个乘数的每位与另一个乘数分别相乘，然后移位相加。所以n*n也可以转换成类似的方式来处理。假设n为32位整数，n*n也为32位整数，则n*n就是两个32位二进制数相乘。其实就是32个数相加，由上面的公式也可以看出来。
二进制乘法反而更简单，就如上图所示的一样，每位要么是0，要么是1，如果是0，则不用相加了，如果是1，则结果就需要加。具体做法就是n的每一位都跟n相乘，当然是要向前移一位，然后相加。
具体c++代码实现为：
int sum(int n)
{
int result = n;
((n>>1) & 1) && (result += (n<<1));
((n>>2) & 1) && (result += (n<<2));
...
((n>>31) & 1) && (result += (n<<31));
return result >> 1;
}需要说明的是&&符号，这里用到了编译器的优化功能，如果&&前面的表达式为false，则右边的表达式就不会执行。所以当某位为0的时候，就不需要相加了。也谈1+2+3+...+n的解答
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。