创意C/C++编程挑战赛Time Limit Exceeded结束，题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思，我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类，里面包含一个mult(int a,int b)的函数，该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是，定义一个类的语句是class multiply{...}，这个空格要怎么避免？只要你知道typedef int foo也可以写成int typedef foo，我们就可以利用typedef来消除空格，把类的定义写成class{...}typedef multiply。但这下后面又冒出一个空格来，这个空格怎么消呢？一个巧妙的方法就是利用int typedef foo,bar的语句，把类定义语句写成class{...}typedef*foo,multiply，其中*foo是一个不会用到的类型，但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格，例如我们在定义mult函数时就可以写成void*mult(...){...}。最后一个难题就是，定义函数mult(int a,int b)，参数表里面的两个空格怎么办？其实办法依然很多。不少网友都用到了typeof，这样便可以把int a写成typeof(int)a了。完整的类定义如下：

class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;

    在gcc下，即使警告全开，下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

查看更多 »

    上次提到，我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded，这个比赛的得分算法很另类，它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中，有几个题目非常具有挑战性，参赛者提交的代码也是牛气冲天。

 
Power of 2
问题：
    输入数据含有多行，每行一个正整数。对每个数，检查看它是否是2的幂，是则输出yes，不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分：
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

查看更多 »

下面这个程序输出什么？
enum {false,true};
int main()
{
        int i=1;
        do
        {
                printf("%d\n",i);
                i++;
                if(i < 15)
                        continue;
        }while(false);
        return 0;
}

你相信么？下面这个程序输出的两行东西不一样！
  #include <stdio.h>
  #define f(a,b) a##b
  #define g(a)   #a
  #define h(a) g(a)

  int main()
  {
          printf("%s\n",h(f(1,2)));
          printf("%s\n",g(f(1,2)));
          return 0;
  }

下面的程序看似完全正确。你能看出它为什么通不过编译吗？
看出问题前不要去试着编译，不然你会后悔你没看出来这个低级的语法错误。
#include<stdio.h>

void OS_Solaris_print()
{
        printf("Solaris - Sun Microsystems\n");
}

void OS_Windows_print()
{
        printf("Windows - Microsoft\n");

}
void OS_HP-UX_print()
{
        printf("HP-UX - Hewlett Packard\n");
}

int main()
{
        int num;
        printf("Enter the number (1-3):\n");
        scanf("%d",&num);
        switch(num)
        {
                case 1:
                        OS_Solaris_print();
                        break;
                case 2:
                        OS_Windows_print();
                        break;
                case 3:
                        OS_HP-UX_print();
                        break;
                default:
                        printf("Hmm! only 1-3 :-)\n");
                        break;
        }

        return 0;
}

为什么下面这个程序的输出不是NONE？看你多久才能看出来。
  #include<stdio.h>
  int main()
  {
          int a=10;
          switch(a)
          {
                  case '1':
                      printf("ONE\n");
                      break;
                  case '2':
                      printf("TWO\n");
                      break;
                  defa1ut:
                      printf("NONE\n");
          }
          return 0;
  }

下面这个程序输出什么？
#include <stdio.h>
int main()
{
        int i=43;
        printf("%d\n",printf("%d",printf("%d",i)));
        return 0;
}

下面这个程序输出什么？
  #include<stdio.h>
  int main()
  {
      int a=1;
      switch(a)
      {   int b=20;
          case 1: printf("b is %d\n",b);
                  break;
          default:printf("b is %d\n",b);
                  break;
      }
      return 0;
  }

下面这个程序输出什么？
  #include <stdio.h>
  int main()
  {
      int i;
      i = 10;
      printf("i : %d\n",i);
      printf("sizeof(i++) is: %d\n",sizeof(i++));
      printf("i : %d\n",i);
      return 0;
  }

下面这个程序输出什么？
  #include <stdio.h>
  #include <stdlib.h>

  #define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))

  #define PrintInt(expr) printf("%s:%d\n",#expr,(expr))
  int main()
  {
      /* The powers of 10 */
      int pot[] = {
          0001,
          0010,
          0100,
          1000
      };
      int i;

      for(i=0;i<SIZEOF(pot);i++)
          PrintInt(pot[i]);
      return 0;
  }

下面这个程序输出什么？
  #include <stdio.h>
  int main()
  {
    int a=3, b = 5;

    printf(&a["Ya!Hello! how is this? %s\n"], &b["junk/super"]);
    printf(&a["WHAT%c%c%c  %c%c  %c !\n"], 1["this"],
       2["beauty"],0["tool"],0["is"],3["sensitive"],4["CCCCCC"]);
    return 0;
  }

下面这个程序输出什么？
#include <stdio.h>
int main()
{
        int i=23;
        printf("%d %d\n",i++,i++);
        return 0;
}

为什么下面这个程序的输出不是10？我故意取消了语法高亮:)
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %d\n",#expr,(expr))
  int main()
  {
      int y = 100;
      int *p;
      p = malloc(sizeof(int));
      *p = 10;
      y = y/*p; /*dividing y by *p */;
      PrintInt(y);
      return 0;
  }

下面这个程序输出什么？
  #include <stdio.h>
  int main()
  {
      int i = 6;
      if( ((++i < 7) && ( i++/6)) || (++i <= 9))
          ;
      printf("%d\n",i);
      return 0;
  }

下面这段代码是否合法？
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %d\n",#expr,(expr))
  int max(int x, int y)
  {
      (x > y) ? return x : return y;
  }

  int main()
  {
      int a = 10, b = 20;
      PrintInt(a);
      PrintInt(b);
      PrintInt(max(a,b));
  }

这是什么意思？有什么潜在的问题？
  #define SWAP(a,b) ((a) ^= (b) ^= (a) ^= (b))

这是什么意思？
  #define ROUNDUP(x,n) ((x+n-1)&(~(n-1)))

一些C语言的教材上会给出一个很经典的宏定义
  #define isupper(c) (((c) >= 'A') && ((c) <= 'Z'))
但这种宏定义的方法存在不足之处，一旦遇到下面这种情况就出问题了：
  char c;
  /* ... */
  if(isupper(c++))
  {
      /* ... */
  }
为了避免这种问题，应该怎样来定义isupper？


怎样用printf函数打印"I can print %"？别忘了百分号是用于格式化输出的。
不用任何比较运算符，写一个程序找出三个数中的最小数。
不用+号，（用位运算）实现加法运算。

最有趣的一个问题：不用分号，写一个Hello World程序。
这是有可能的，而且办法非常简单，只用到了最基本的语法规则。
实在想不出来再看答案吧（白色的）：
#include <stdio.h>
int main()
{
    if (printf("Hello World")){}
}

查看更多：http://www.gowrikumar.com/c/

    一个正整数n的阶乘就是前n个正整数的乘积，我们通常需要n-1次乘法操作来算出精确的值。不像等差数列求和、a的n次幂之类的东西，目前求阶乘还没有什么巨牛无比的高效算法，我们所能做的仅仅是做一些小的优化。

更少的乘法运算次数？
    在高精度运算中，乘法计算的速度远远慢于加减法，因此我们有必要减少乘法运算的次数。下面我将做一个非常简单的变换，使得计算阶乘只需要n/2次乘法。继续看下去之前，你能自己想到这个算法来吗？

    我们可以把一个数的阶乘转换为若干个平方差的积。例如，假如我想求9!，我可以把前9个正整数的乘积写成这个样子：
   1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9
= (5-4) * (5-3) * (5-2) * (5-1) * 5 * (5+1) * (5+2) * (5+3) * (5+4)
= (5-1) * (5+1) * (5-2) * (5+2) * (5-3) * (5+3) * (5-4) * (5+4) * 5
= (5^2 - 1^2) * (5^2 - 2^2) * (5^2 - 3^2) * (5^2 - 4^2) * 5
    注意到一个有趣的事实：上面的四个平方差算出来分别是24, 21, 16, 9，它们之间的差正好是连续的奇数（因为n^2等于前n个正奇数的和）。因此，我们可以用初始数(n/2)^2不断减去一个个的正奇数，求出所有n/2个平方差，再用n/2次乘法把它们乘起来。这种算法实现起来非常简单，并且（当n不大时）同样只需要单精度乘高精度，但需要的乘法次数大大减少了。假设我们已经有了一个高精度类，求n!只需要下面几句话：
long h=n/2, q=h*h;
long r = (n&1)==1 ? 2*q*n : 2*q;
f = LargeInteger.create(r);
for(int d=1; d<n-2; d+=2)
   f = f.multiply(q-=d);

更少的总运算次数？
    尽量提取阶乘中的因子2，我们可以得到另一种阶乘运算的优化方法。这很可能是不需要分解质因数的阶乘算法中最快的一种。
    假如我们需要计算20!，我们可以把20拆成若干组正奇数的乘积：

  1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 2 * 4 * 6 * 8 * 10 * 12 * 14 * 16 * 18 * 20
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 2^10
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 2 * 4 * 6 * 8 * 10 * 2^10
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 2 * 3 * 4 * 5 * 2^15
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 2 * 4 * 2^15
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 1 * 2 * 2^17
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 1 * 2^18

    只需要一次累乘就可以求到每一组奇数的乘积，最后再花费log(n)次乘法把它们全部乘起来。最后的那个2^18也可以二分计算出来。真正的代码还有很多细节上的优化，另外还借用了递归使得操作变得更加简便。你可以在本文最后附的那个链接里去找Split-Recursive算法。

还能再快一点么？
    继续扩展上面的算法，我们可以想到，如果把每个数的质因数都分解出来，并且统计每种质因子有多少个，我们就可以多次使用二分求幂，再把它们的结果乘起来。注意这里并不是真的要老老实实地去分解每个数的质因子。对于每个质数x，我们可以很快算出前n个正整数一共包含有多少个质因子x（记得如何求n!末尾有多少个0么）。这种算法的效率相当高，已经能够满足大多数人的需要了。

另一种诡异的阶乘算法：
    这个算法可能是所有有名字的阶乘算法中最慢的一个了（Additive Moessner算法），它对一个数列进行重复的累加操作，一次次地计算前缀和，总共将花费O(n^3)次加法操作。但是，令人费解的是，这个简单的程序为什么可以输出前n个正整数的阶乘呢？
a[0]:=1;
for i:=1 to n do
begin
   a[i]:=0;
   for j:=n downto 1 do
   begin
      for k:=1 to j do
         a[k]:=a[k]+a[k-1]
      write(a[i],' ');
   end;
end;
    我在网上搜索相关的东西时找到了另一个有趣的东西。对一个初始时全为1的数列反复进行这两个操作：累加求前缀和，然后以1,2,3,...的间隔划掉其中一部分数（即划去所有位置编号为三角形数的数）形成新的序列。类似的数列操作方法最先由Alfred Moessner提出的，我们这里不妨把它叫做Moessner数列。你会发现，第n轮操作开始前，数列的第一个数恰好是n! 。看看下面的例子吧：

1 1 1 1 1 1 1 1 1  1  1  1  1  1  1 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
x 2 x 4 5 x 7 8 9  x 11 12 13 14  x ...

2 4  5  7  8  9 11 12 13 14 ...
2 6 11 18 26 35 46 58 71 85 ...
x 6  x 18 26  x 46 58 71  x ...

6 18 26 46  58  71 ...
6 24 50 96 154 225 ...
x 24  x 96 154   x ...

24  96 154 ...
24 120 274 ...
x 120  x  ...

120 ...
.....

    当然，发现前面O(n^3)的程序和这个Moessner数列的关联时我很是吃了一惊：在前面的程序里，如果你输出每一次i循环末所得到的数列，你会发现输出的这些数正好就是后面这个问题里被我们划掉的数，而它们其实就是第一类Stirling数！
    这到底是为什么呢？是什么东西把阶乘、第一类Stirling数、Moessner数列和那个O(n^3)的程序联系在一起的呢？昨天，我想这个问题想了一天，最后终于想通了。如果把Moessner数列排列成这个样子，一切就恍然大悟了：

  
    仔细观察上图，我们会发现：
    1. 按照Moessner数列的定义，每个数都应该等于它左边的数和左上角的数的和（这个“左边”可以跳过若干空格）。例如，35 = 9 + 26，46 = 11 + 35。排成一系列三角形后，每个三角形最右边一列的数就是被划去的数，它永远不能参与它下面的那些行的运算。
    2. 设a[n,i,j]表示左起第n个三角形阵列中的第i行右起第j列上的数，则a[n,i,j]=a[n-1,i-1,j]*n + a[n-1,i,j]，例如274=50*5+24。如果递推时遇到空白位置而它左边隔若干空格的地方还有数的话，则需要用左边的数来补，例如18=4*4+2。对于每个三角形的最后一列来说，这个性质实际上就是第一类Stirling数的递推关系，因此Moessner数列中才会出现第一类Stirling数。
    3. 在第一类Stirling数中，s(n,1)=n! ，也即左起第n个三角形最底端的那个数等于n!。从上面的第二个性质来看，这也是显然的。
    4. O(n^3)的算法实际上就是在绘制上面这个图。每一次j循环末，我们得到的序列是第i个三角形中每一行左起第j个数组成的序列。例如，计算第5个三角形内的数时，程序首先累加出1, 11, 46, 96, 120, 120，这样便算出了a[5]=120，数列的前5个数再次累加即得到1, 12, 58, 154, 274，由此算出a[4]=274。
    第二个性质可以利用第一个性质进行数学归纳法证明，证明很简单，我就不多说了。现在我尽可能少写一些繁琐的细节，节约一些时间用来复习古代汉语。

做人要厚道，
转贴请注明出处。

查看更多：
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
http://www.luschny.de/math/factorial/index.html <---- 巨牛，20多种阶乘算法的代码！

    Ben orenstein尝试在Goolge Code Search里输入脏话，在众多的开源软件中找到了一些非常牛B的代码：

gdb-6.4.50.20060515:
/* OK, now set up the filehdr...  */

/*   We will NOT put a fucking timestamp in the header here. Every time you
     put it back, I will come in and take it out again.  I’m sorry.  This
     field does not belong here.  We fill it with a 0 so it compares the
     same but is not a reasonable time. — gnu@cygnus.com  */

Siesta-0.66:
    # This job would be great if it wasn’t for the fucking customers.

CGI-FormBuilder-3.0202:
        # Get field from radio buttons or checkboxes
        # Must cycle through all again to see which is checked. yeesh.
        # However, this only works if there are MULTIPLE checkboxes!
        # The fucking JS DOM *changes* based on one or multiple boxes!?!?!
        # Damn damn damn I hate the JavaScript DOM so damn much!!!!!!

DJabberd-0.81:
    # Trillian, again, is fucking stupid and crashes on just
    # about anything its homemade XML parser doesn’t like.

gift-0.11.5:
void list_lock_insert_sorted (ListLock *lock, CompareFunc func, void *data)
{
    if (lock->locked)
    {
        /* TODO: this is obviously not right ... this whole fucking module
         * sucks anyway */
        list_lock_prepend (lock, data);
        return;
    }

    lock->list = list_insert_sorted (lock->list, func, data);
}

bh-asia-03-grugq:
    /* if we get here, there are massive fucking problems, for a start
     * our stack is fucked up, and we can’t return(). Just crash out. */

trunk:
    /* FIXME: please god, when will the hurting stop? Thus function is so
              fucking broken it’s not even funny. */

SQL-Abstract-1.20:
    # Note to self: I have no idea what this does anymore
    # It looks like a cool fucking segment of code though!
    # I just wish I remembered writing it… :-\

mendax_linux:
for(i = 0 ; i < pktcount; i++) {
    from.sin_port = htons(ntohs(from.sin_port) + 1);
    pktlen = gen_tcp_pak(&pak, &from, dst, ip_id++,
                     seq_num, 0L, 0, flags);
    seq_num += 64000;

    /* don't fire dem packets too fucking fast */
    usleep(1000);

    send_pak((char *) &pak, pktlen, ether);
    putchar('.');
}

SugarOS-for-Microsoft-Full-4.5.0h:
    /*   Outlook can’t fucking follow RFC if someone PAID them to do it…
        oh wait, someone paid them NOT to do it. */

AfterStep-2.2.5:
    /* No we fucking don’t! DB entries should be stored in the same order
       as they are in the file ! I can’t belive I was so fucking stupid !  */

gallery-2.0.4/modules/core/classes/GalleryStorage:
else if ($affectedRows > 1) {
   /* Holy shit, we just updated more than one row!  What do we do now? */
   return GalleryStatus::error(ERROR_STORAGE_FAILURE, __FILE__, __LINE__,
                        "$query (" . implode('|', $data) . ") $affectedRows");
}

linux-2.4.34.1/arch/sparc/lib/checksum.S:
        /* Sun, you just can’t beat me, you just can’t.  Stop trying,
         * give up.  I’m serious, I am going to kick the living shit
         * out of you, game over, lights out. */

linux-2.6.1/arch/mips/kernel/sysirix.c:
    /* 2,191 lines of complete and utter shit coming up… */

nfs-utils-1.1.0/utils/statd/misc.c:
    if (!(ptr = malloc (size)))
            /* SHIT!  SHIT!  SHIT! */
            die (”malloc failed”);

dada-2_10_12:
    # code below replaces code above - any problems?
    # yeah, it doesn’t fucking work.

    Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍：
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

    code/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数，与上面的代码唯一不同的就是这个函数返回的是number*y：
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

    这样的代码速度肯定飞快，我就不用多说了；但算法的原理是什么呢？其实说穿了也不是很神，程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 - a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x - f(x)/f'(x)，式子化简为x' = x * (1.5 - 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。
    但这段代码真正牛B的是那个神秘的0x5f3759df，因为0x5f3759df - (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的，只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事，很少有人说得清楚。这篇论文比较科学地解释了这个常数。

3x12=36
2x12=24
1x12=12
0x12=18