求一个数的最短二进制表达式

分类： 50. algorithem & software 2007-02-15 17:21 502人阅读 评论(0) 收藏 举报

   1, linux kernel(2.6)的hash函数计算方法
    unsigned long hash_long(unsigned long val, unsigned int bits)
    {
        unsigned long hash = val * 0x9e370001UL;
        return hash >> (32 - bits);
    }
   
2,在understanding linux kernel (3rd edition)中对所选取常数0x9e370001UL
有一段描述:
 
    The Magic Constant
You might wonder where the 0x9e370001 constant (= 2,654,404,609) comes from.
This hash function is based on a multiplication of the index by a suitable
large number, so that the result overflows and the value remaining in the
32-bit variable can be considered as the result of a modulus operation.
Knuth suggested that good results are obtained when the large multiplier
is a prime approximately in golden ratio to 232 (32 bit being the size of
the 80x86's registers). Now, 2,654,404,609 is a prime near to 2^32*(sqrt(5)-1)/2
that can also be easily multiplied by additions and bit shifts, because
it is equal to  2^0-2^16-2^19+2^22-2^25+2^29+2^31.

3,联想到"一道C语言笔试题的算法以及简单证明"中所使用的算法
  实际上这个算法同时也得到了整数的最短二进制表达式, 对+/-做一个逆运算即可.

4,这个表达式的作用
  很显然,可以用于对乘法的优化.