H***g
发帖数: 105 | |
A*X
发帖数: 908 | 2 分块查表
【在 H***g 的大作中提到】
: 想了一会，没想出来。
|
H***g
发帖数: 105 | 3 怎么建这个表？
【在 A*X 的大作中提到】
: 分块查表
|
c****r
发帖数: 185 | 4 Partition 32 bits into 4 blocks, each has 8 bits,
then construct a table of size 256 in which
each entry is the number of 1's, e.g. [0x101]=2
Lookup the table for every block and sum up ...
【在 H***g 的大作中提到】
: 怎么建这个表？
|
b***n
发帖数: 53 | 5 why is 8 the magic number?
【在 c****r 的大作中提到】
: Partition 32 bits into 4 blocks, each has 8 bits,
: then construct a table of size 256 in which
: each entry is the number of 1's, e.g. [0x101]=2
: Lookup the table for every block and sum up ...
|
c****r
发帖数: 185 | 6 The table size is exponential to the block length.
8 seems to be a suitable length.
Furthermore, 8 can divide 32. If you use 10 bits,
you still need 4 rounds.
【在 b***n 的大作中提到】
: why is 8 the magic number?
|
s****l
发帖数: 12 | 7 check this out. It has a lot of interesting solutions
http://www-db.stanford.edu/~manku/bitcount/bitcount.html
【在 H***g 的大作中提到】
: 想了一会，没想出来。
|
s***e
发帖数: 284 | 8 赞
【在 s****l 的大作中提到】
: check this out. It has a lot of interesting solutions
: http://www-db.stanford.edu/~manku/bitcount/bitcount.html
|
s****l
发帖数: 12 | 9 那个MIT的解法很cool。
有意思的是运行最快的是看着最笨最简单的那个解法，:)。
【在 s***e 的大作中提到】
: 赞
|
b**g
发帖数: 335 | 10
Which one is the most stupid one? I think it's the first one (iterated).
And it is also the slowest.
Nothing can beat the table look-up methods..
【在 s****l 的大作中提到】
: 那个MIT的解法很cool。
: 有意思的是运行最快的是看着最笨最简单的那个解法，:)。
|
|
|
d*z
发帖数: 150 | 11 我觉得实际使用的话,查表方法不会那么快
估计做测试的时候没有考虑Cache的问题.
测试程序肯定是给出一大堆数据,然后连续计算他们的bitcount,
但是这样的话,对于查表方法是有利的,因为经过几次使用以后,整个表格都会在Cache里面
了. 而如果实际使用,估计8-bit的查表方法就要比16-bit的查表方法快.
而那些不需要访问内存的方法也肯定很快.
【在 b**g 的大作中提到】
:
: Which one is the most stupid one? I think it's the first one (iterated).
: And it is also the slowest.
: Nothing can beat the table look-up methods..
|
p*********e
发帖数: 1503 | 12 按位逐个加起来？
【在 H***g 的大作中提到】
: 想了一会，没想出来。
|
k**********g
发帖数: 989 | 13
里面
Agreed.
If it is only used infrequently, performance isn't a big problem.
If it is used frequently (millions or billions of times at once), the table
will be in CPU cache, so the table method will make sense.
【在 d*z 的大作中提到】
: 我觉得实际使用的话,查表方法不会那么快
: 估计做测试的时候没有考虑Cache的问题.
: 测试程序肯定是给出一大堆数据,然后连续计算他们的bitcount,
: 但是这样的话,对于查表方法是有利的,因为经过几次使用以后,整个表格都会在Cache里面
: 了. 而如果实际使用,估计8-bit的查表方法就要比16-bit的查表方法快.
: 而那些不需要访问内存的方法也肯定很快.
|
d*****l
发帖数: 8441 | |
d*****l
发帖数: 8441 | |
k*******d
发帖数: 701 | 16 if performance is not very important,try this java code as followings:
int n is a 32 bit number.
int counter(int n){
int count = 0;
while(n){
n &= (n-1);
count++;
}
return count;
} |
