Hacker's delight is a interesting book. The only problem is it skiped many steps and hard to follow. For example, one of the topic is how to cout the number of binary 1s for a unsigned interger.
1. Easy answer start from here
unsigned int CountBitOne(unsigned int x)
{
unsigned int count = 0;
while(x)
{
count += x & 1;
x>>= 1;
}
return count;
}
Note: don't use for loop! That's not efficient as while loop. Think about the sparse 1 case.
2. A well know trick.
unsigned int CountBitOne(unsigned int x)
{
unsigned int count = 0;
while(x)
{
++count;
x &= (x -1);
}
return count;
}
It is easy to prove x&(x-1) reset the least significiant bit of 1 of value. Suppose we have 8bits interger value
x b'XXXX1000 (Capital X means either 1 or 0)
x-1 b'XXXX0111
x&(x-1) b'XXXX0000
3. Can you do more optimization? Look up table is a good, and probbaly the fast solution, just make sure your lookup table is always in cache.
4. Method 1 and 2 count one bit at one time. Can we do more bits at the same time?
Divide and Conquer Algorithm. Suppose there is a 8bit integer 213(11010101 in binary), the algorithm works like this(each time merge two neighbor blocks):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
uint32_t CountBitOne(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
I changed the parameter's type to uint32_t sicne the introduction of magic binary numbers.
5. Divide and conqure method provided in Hacker's delight
https://books.google.com/books?id=iBNKMspIlqEC&pg=PA66&hl=en#v=onepage&q&f=false
uint32_t pop(uint32_t x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
The first line of this algorith has the same effect as method 4, proved by truth table
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
6. Last one is the so called "fastest way—without using lookup tables and popcount.", copied from
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
It counts the set bits with just 12 operations.
uint32_t popcount(uint32_t v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
The trick is to multiply the result by 0b10101010 which has an interesting property. If our number has four bytes, A B C D, it will result in a new number with these bytes A+B+C+D B+C+D C+D D. A 4 byte number can have maximum of 32 bits set, which can be represented as 0b00100000.
All we need now is the first byte which has the sum of all set bits in all the bytes, and we get it by >> 24.
7. Intel x86 CPU has a POPCOUNT in SSE instruction set to count the number of 1s. On the GNU compiler you can just use:
int __builtin_popcount (unsigned int x);
In the worst case the compiler will generate a call to a function. In the best case the compiler will emit a cpu instruction to do the same job faster. Unfortunately there is no equivelant on ARM yet.
练习有益健康,拿这书的解法去面人就比较苛刻
《Hacker's Delight》热门书评
-
计算机算法大全——算法中的亚原子粒子世界
46有用 0无用 高博 2014-04-04
本书讲解的算法,和我译的那本《算法谜题》(http://book.douban.com/subject/25805152),虽然名字差不多,但是讲述的是完全不同的题材。本书讲解的题材,可以说市面上仅此一本(如果不算第一版的话),可以说是唯一一本讲解计算机算法的图书——而其他的算法书,则基本上全部是讲...
-
这译者的英文水平是小学二年级,视力水平是眼瞎!
23有用 0无用 炸酱面的情怀 2014-10-02
译者翻译的部分我已经不想再拿来恶心自己了,前面有豆友已经吐完槽了。我想说的是,今天我拢共就看了三页,从第二章开头(11页)看到了13页,实在就看不下去了。被低级到单细胞生物都不会犯的错误刺痛了三叉神经,确实没法儿淡定...
-
04版 中文版翻译的太差了!!!!!!!!!!!!!!
16有用 0无用 [已注销] 2012-11-13
此评论仅限于04机工版,已入英文第2版,不知14版翻译质量对于 a<x<b 且 c<y<d成立的情况下P44.译文:最后,对于a+c产生溢出但b+d不产生溢出的情况,等式成立的理由是a<b且c<d.原文: Lastly, the case that a+c ov...
-
面试时 SM 考官的神兵利器
14有用 5无用 Wang Feng 2011-02-28
临行前多读读,到时候随便挑一段代码讲讲,绝对让丫面无人色~~注意把握分寸一点,当心对方恼羞成怒。 ...
-
这本烂书应该归到娱乐类
9有用 13无用 mach 2010-12-21
年轻时买的,当时看了头几页,佩服地不行,不过后来就没再看了,前些日子整理的时候又看了看,趣味性极强,看得我很欢乐。里边记载了上古时期的先贤们经历的苦难以及他们的智慧。基本上,除了吹牛逼装逼外就没啥实用价值了。...
书名: Hacker's Delight
作者: Henry S·Warren Jr
出版社: Addison-Wesley
出版年: 2002-7-27
页数: 306
定价: USD 59.99
装帧: Hardcover
ISBN: 9780201914658