Titel

Wertung

sehr empfehlenswert

Das Buch des Jahres 2002! Wer Assembler oder eine libc oder einen Compiler programmiert, der braucht dieses Buch. Es geht auf das HAKMEM Memo vom MIT 1972 zurück (online siehe unten) und enthält alles was man mit Bits so machen kann.

Hauptthema

Das Buch beschäftigt sich mit den kleinen Tricks, die normalerweise nur auf Maschinenwortebene zum Tragen kommen, z.B. das effiziente Zählen der 1-Bits in einem Wort.

Kapitelstruktur

 Foreword (von Guy Steele)
 Preface
 Ch 1, Introduction
 Ch 2, Basics
 Ch 3, Power-of-2 Boundaries
 Ch 4, Arithmetic Bounds
 Ch 5, Counting Bits
 Ch 6, Searching Words
 Ch 7, Rearraging Bits and Bytes
 Ch 8, Multiplication
 Ch 9, Integer Division
 Ch 10, Integer Division by Constants
 Ch 11, Some Elementary Functions
 Ch 12, Unusual Bases for Number Systems
 Ch 13, Gray Code
 Ch 14, Hilberts Curve
 Ch 15, Floating Point
 Ch 16, Formulas for Primes
 Appendix A, Arithmetic Tables for a 4-Bit Machine
 Appendix B, Newton's Method
 Bibliography
 Index

Verständlichkeit, Sprache

Klares Englisch, sehr konzis. Das Buch enthält relativ viele Formeln, aber auch anschauliche Codebeispiele in C und RISC-Assembler.

Was ist die Botschaft? Motivation und Begründung

Der Autor (und Guy Steele) will die vielen Tricks, die er im Laufe seiner beruflichen Karriere als Compilerbauer und CPU Architekt bei IBM (vom 704 bis zum PowerPC) gesammelt hat, in diesem Buch für die Nachwelt bewahren.

Meine Meinung

Dem Autor ist es definitiv geglückt, ein Standardwerk zu schreiben. Es ist grundlegendwie Knuth, aber noch lesbar (und spannend ist es auch). Der normale Leser wird nur selten in die Verlegenheit kommen, die aufgezeigten Algorithmen auch einzusetzen. Aber es ist erfrischend, Code zu sehen, der sich gegen den Zeitgeist "Bloatware" stellt.

Das Buch ist vermutlich mit troff oder TeX gemacht und fest gebunden, also auch optisch ein Hochgenuss.

Autor(en)

Henry S. Warren, Jr.

Erscheinungsjahr, Verlag, ISBN, Seitenzahl

2002, Addison-Wesley, 0-201-91465-4, 306 Seiten

URLs

Amazon: http://www.amazon.de/exec/obidos/ASIN/0201914654

Verlag: http://www.awprofessional.com/catalog/product.asp?product_id={E289746E-7E46-47C6-9CAA-C9F78991A843}

Homepage & Errata: http://www.hackersdelight.org/

Autor: http://domino.watson.ibm.com/comm/research.nsf/pages/d.compsci.warren.html

Slashdot: http://books.slashdot.org/books/03/01/14/1450204.shtml?tid=156

HAKMEM MEMO: http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

Weitere Links zum Thema Bitfummelei:

• http://graphics.stanford.edu/~seander/bithacks.html
• http://realtimecollisiondetection.net/blog/?p=78

Wurzel Magie

In Quake III findet sich ein extrem kompakter und vor allem schneller Wurzel-Algorithmus ohne Schleife, der schneller als der FSQRT-Befehl des Prozessors ist! Hier die Implementation für sqrt():

 /* ================
  * SquareRootFloat?
  * ================
 */
 float SquareRootFloat?(float number) {
     long i;
     float x, y;
     const float f = 1.5F;
 
     x = number * 0.5F;
     y  = number;
     i  = * ( long * ) &y;
     i  = 0x5f3759df - ( i >> 1 );
     y  = * ( float * ) &i;
     y  = y * ( f - ( x * y * y ) );
     y  = y * ( f - ( x * y * y ) );
     return number * y;
 }

 float InvSqrt?(float x)
 {
     float xhalf = 0.5f*x;
     int i = *(int*)&x; // get bits for floating value
     i = 0x5f375a86- (i>>1); // gives initial guess y0
     x = *(float*)&i; // convert bits back to float
     x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
     return x;
 }

Schlagworte

Bit, Bitvektoren, Algorithmen, Graycode, Integerdivision, Fliesskomma

Datum

13-Dez-2002

last modified: $Date: 2008/09/23 19:27:37 $