Hacker's Delight

Hacker’s Delight

November 4, 2008 @ 4:56 | In Books, Hacking, Programming | 11 Comments |

Hacker’s Delight
Author: Henry S. Warren, Jr.
Pages: 306
Published: 2003

You may think that I have become obsessed with books about hacking but this book is totally different from any of the others. In this book the term hacker is meant in the traditional sense (before the negative definition was popularized) of someone interested in understanding how things work and how to solve problems efficiently. Although the hacker term can be applied to whatever domain, in this book the domain is computing technology.

‘Hacker’s Delight’ is a book about bits and small programming tricks applied to machines. With ’small’ I mean that you won’t find here a description of the Merge sort or Radix sort but, for example, you will learn to determine in constant time if an integer is a power of two or not.

In more that 300 pages and with a mixture of pseudo assembler and C you will find all kind of tricks for arithmetic bounds, counting bits, searching bits, multiplications, elementary functions, floating point, etc. Even wondered if the base2 used by computers is the most efficient? This question and a lot more are covered in this book.

Although the book is a little bit oriented towards compiler developers, every ‘real’ programmer can get a huge benefit from reading and thoroughly understanding this book.

I read this book on several flights and really enjoyed this little gem book of tricks. I would definitely recommend to have it in your bookshelf.

Rating: 8 / 10

TrackBack URI

After all we are mostly all hackers are we not?
Out of interest is the method they used for power of 2
extern int i;
bool power_of_two( i & 0×01 );

Comment by Liam
November 4, 2008 @ 13:06 #
O dear that is multiple not power of lol.
I suspect it would use the same type of logic thought, just testing the upper bit with the rest zeroed out.

Comment by Liam
November 4, 2008 @ 13:57 #
Does this book tell how to enter into the FBI or the NASA computers?

Comment by Zalo
November 4, 2008 @ 15:42 #
bool IsPow2(int x)
{
return (((x) & ((x) – 1)) == 0);
}

Comment by ent
November 4, 2008 @ 16:59 #
I’ve seen that code before, but as a macro. It was in a classroom

Comment by Rickyah
November 5, 2008 @ 10:25 #
Is zero really a power of two?

Comment by Liam
November 5, 2008 @ 17:44 #
Liam I think you misunderstood the code abobe.

A power of two number express in binary ALWAYS has exactly ONE bit equal to 1:
2 = 0010
4 = 0100
8 = 1000
…

take that number and the previous:
1 = 0001
3 = 0011
7 = 0111

Perform an ‘and’ bit operation:
0010 & 0001 == 0000
0100 & 0011 == 0000
1000 & 0111 == 0000

For any number not power of two, e.g. 7 the result is not zero:
0111 & 0110 = 0110 == 6 != 0

Comment by RickyAH
November 5, 2008 @ 18:51 #
RickyAH thanks for your concern about me being unable to read code, but I fully understand it and understand the floor in the solution.

bool IsPow2(int x)
{
return x ? x & (x – 1) == 0 : false;
}
bool IsPow2_org(int x)
{
return (((x) & ((x) – 1)) == 0);
}
#include
int main()
{
int i = 0;
std::cout <<IsPow2(i) <<” ” <<IsPow2_org(i);
}

Comment by Liam
November 5, 2008 @ 19:17 #
Liam is right,

That function is not exactly correct because is returning true for zero (zero is not a power of two).

So, rename the function to IsPower2OrZero() or add to that function the check against zero.

Sorry for the bug.

Comment by ent
November 5, 2008 @ 19:20 #
Just typing that out quickly I have missed a set of parenthesis
return x ? (x & (x – 1)) == 0 : false;

Comment by Liam
November 5, 2008 @ 19:21 #
Sorry Liam, i totally misunderstood you

Comment by Rickyah
November 6, 2008 @ 13:21 #