一道出题人闲的蛋疼的题目,单纯的语法技巧,难度系数不做判定。
题目描述如下:
题目:求1+2+…+n,
要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句
(A?B:C)。
逻辑分析:
1、我们都知道1到n的和,计算方法可按照等差数列n(n+1)/2计算得出,但是显然,这里禁用了乘除法,而一般的思路,如果采用加法运算,那么势必需要循环。
2、如果不采用循环,那么就只能*用递归,类似斐波那契的递归方法。但是很快我们发现,递归需要终止条件,而终止条件需要判定,这里我们却无法使用if等条件判定。从底层的角度出发,我们知道,计算机无非就是数字逻辑,&&式的短路条件跃然纸上,简单的思考过后,不难写出如下代码:
#include <stdio.h> int Factorial(int n) { int num = 0; (n > 0) && (num = n + Factorial(n - 1)); return num; } int main() { printf("%d\n",Factorial(100)); }
虽然效率因为系统栈的递归而底下(显然没有循环加法效率高,因为这里多了n层prolog的指令)。
3、实际上,&&给我们提供了很大的空间,短路&&替补了if的位置,那么也完全可以想到其他的实现方式。回到我们之前的n(n+1)/2,我们知道计算机底层的乘除法,很多都是利用位运算进行指令优化,而x/2不难得出(右移一位而已),那么我们只需要通过某种运算,得出n^2即可,显然,这不是一个简单的运算,我先给出代码,再做详解。
#define T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i) int foo(int n){ int r=n; T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31); return r >> 1; }
这是阿财给出的代码,非常难理解,我们知道,一般int是4字节,也就是32位,除去最高位符号位,也就是31位,而将n展开成二进制形式,无非就是看这31位哪里有1,哪里有0,n(n+1)也就是n(2^x1+2^x2+...+2^xn+1),其中xn递减,举个例子,比如n=5时,那么5*6 = 5(2^2+2^0+1),如果n=6,那么6*7=(2^2+2^1+1)。所以,我们不难写出这个式子(Y&(1<<i)) && (X+=(Y<<i)),&&用于短路,短路条件即是判定n的第i为是否为0,如果为0则短路,如果为1那么后续累加,还是用n=5做例子,5只有第0位和第2位为1,那么只有T(r,n,0)和T(r,n,2)不被短路,累加即相当于5*6 = 5(2^2+2^0+1)。
实际上还有各种各样的方式,回忆一下计算方法,然后试着写一个