空间换时间

问题一

求一个32位整数包含bit 1的个数。

classical:

int cntnzw(int x)
{
  int count = 0, i;

  for (i = 0; i < sizeof(x) * 8; i++) {
    if (x & (1 << i))
      ++count;
  }

  return count;
}


不足： 包含跳转指令（jmp, or branch）

另外一个空间换取时间的版本：

static char bitcount[256] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

int cntnzw(int x)
{
  int count = 0;

  count += bitcount[(x) & 0xff];
  count += bitcount[(x>>8) & 0xff];
  count += bitcount[(x>>16) & 0xff];
  count += bitcount[(x>>24) & 0xff];

  return count;
}


优点：没有branch分支。
缺点：多用了256 bytes空间
     由于要访问额外的数组，潜在导致了cache miss rate，考虑一个cache line size == 32 / 64 bytes

另外一个小例子：

#define S (1 << 7)
static char from_hex_array[0x80] = {
  ['a'] = 10 | S, ['b'] = 11 | S, ['c'] = 12 | S,
  ['d'] = 13 | S, ['e'] = 14 | S, ['f'] = 15 | S,
  ['A' ] = 10 | S, ['B'] = 11 | S, ['C'] = 12 | S,
  ['D'] = 13 | S, ['E'] = 14 | S, ['F'] = 15 | S,
  ['0'] = 0 | S, ['1'] = 1 | S, ['2'] = 2 | S, ['3'] = 3 | S, ['4'] = 4 | S,
  ['5'] = 5 | S, ['6'] = 6 | S, ['7'] = 7 | S, ['8'] = 8 | S, ['9'] = 9 | S,
};
#undef S

static inline int from_hex(int ch)
{
  return from_hex_array[ch & 0x7F] & 0x7F;
}

static inline int isxdigit(int ch)
{
  return from_hex_array[ch & 0x7F] & (1 << 7)
}

/* convert hex string to int */
long my_atol(const char* str)
{
  const char* s = str;
  long res = 0;

  while (*s) {
    if (!isxdigit(*s))
      break;
    res += (res << 4) + from_hex(*s);
    ++s;
  }

  return res;
}