Hakmem: classic programming hacks

Anyone interested in this will likely be interested in:

Bit Twiddling Hacks - http://graphics.stanford.edu/~seander/bithacks.html

The book Hacker's Delight by Henry S. Warren Jr and published by Addison Wesley - homepage at http://www.hackersdelight.org/

Also, there's the famous Quake inverse square root hack.

http://www.beyond3d.com/content/articles/8/

Here's a personal favorite of mine that I wrote a while back; I like it because it does what seems to be a slightly complicated problem to SIMD (count the number of nonzero elements in a 16-element array of 16-bit values) and does it in a really small number of instructions:

  static inline int array_non_zero_count_mmx( int16_t *v )
  {
      int count;
      asm(
          "pxor     %%mm7,  %%mm7 \n"
          "movq     (%1),   %%mm0 \n"
          "movq     8(%1),  %%mm1 \n"
          "packsswb 16(%1), %%mm0 \n"
          "packsswb 24(%1), %%mm1 \n"
          "pcmpeqb  %%mm7,  %%mm0 \n"
          "pcmpeqb  %%mm7,  %%mm1 \n"
          "paddb    %%mm0,  %%mm1 \n"
          "psadbw   %%mm7,  %%mm1 \n"
          "movd     %%mm1,  %0    \n"
          :"=r"(count)
          :"r"(v)
      );
      return (count+0x10)&0xff;
  }

It is, not surprisingly, an order of magnitude faster than the C equivalent. Bonus points for understanding what the "0x10" is for at the end.

This one is amazing: http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154