32bit入力/任意bit出力 ハッシュ関数

32bit値から指定ビット長へのハッシュ関数。linuxカーネルより。

unsigned long hash_long(unsigned long val, unsigned int bits)
{
  unsigned long hash = val * 0x9e370001UL;
  return hash >> (32 - bits);
}

マジックナンバー0x9e370001(16)/2654404609(10)は、32bit値の黄金比 2^32 * (sqrt(5) - 1) / 2 = 2654435769.5 に近い素数が選択されている。

// 2^32 * (sqrt(5) - 1) / 2 = 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 = 2654404609