Hacker's Delight
Hacker's Delight är en mjukvarualgoritmbok av Henry S. Warren, Jr. publicerad första gången 2002. Den presenterar snabba aritmetiska algoritmer på bitnivå och lågnivå för vanliga uppgifter som att räkna bitar eller förbättra divisionshastigheten genom att använda multiplikation.
Bakgrund
Författaren, en IBM-forskare som arbetar med system som sträcker sig från IBM 704 till PowerPC , samlade in vad han kallade "programmeringsknep" under sin karriär. Dessa knep gäller effektiv lågnivåmanipulation av bitsträngar och nummer. Enligt bokens förord av Guy L. Steele inkluderar målgruppen kompilatorförfattare och personer som skriver högpresterande kod.
Sammanfattning
Programmeringsexempel är skrivna i C och assembler för en RISC- arkitektur som liknar, men inte är identisk med PowerPC . Algoritmer ges som formler för valfritt antal bitar, exemplen vanligtvis för 32 bitar.
Förutom inledningen är kapitlen oberoende av varandra, vart och ett med fokus på ett visst ämne. Många algoritmer i boken är beroende av tvås komplement heltal.
Ämnet för den andra upplagan av boken innehåller algoritmer för
- Grundläggande algoritmer för att manipulera enskilda bitar, formler för identiteter, ojämlikheter, bräddavkänning för aritmetiska operationer och skift
- Avrundning uppåt och nedåt till en multipel av en känd potens av 2, nästa potens av 2 och för att detektera om en operation korsade en gräns för potens av 2
- Kontrollerar gränser
- Räknar totalt , inledande och efterföljande nollor
- Söker efter bitsträngar
- Permutationer av bitar och bytes i ett ord
- Programvara algoritmer för multiplikation
- Heltalsdivision
- Effektiv heltalsdelning och beräkning av resten när divisorn är känd
- Heltals kvadrat- och kubrötter _
- Ovanliga talsystem, inklusive bas -2
- Överföring av värden mellan flyttal och heltal
- Cykliska redundanskontroller , felkorrigerande koder och gråkoder
- Hilbert-kurvor inklusive en diskussion om tillämpningar
Stil
Stilen är en informell matematisk lärobok. Formler används flitigt. Matematiska bevis ges för vissa icke-uppenbara algoritmer, men är inte bokens fokus.
Reception
Mottagandet har generellt sett varit positivt.
Publiceringshistorik
Boken publicerades av Addison-Wesley Professional . Den första upplagan släpptes 2002 och den andra 2013.
Se även
Vidare läsning
- Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (april 1995) [1972-02-29]. "Artificiell intelligens Memo nr 239" . I Baker, Henry Givens Jr. (red.). HAKMEM (omskriven & konverterad utg.). Cambridge, Massachusetts, USA: Artificial Intelligence Laboratory , Massachusetts Institute of Technology (MIT). Arkiverad från originalet 2019-10-08 . Hämtad 2016-01-02 .
- Jones, Douglas W. (2014-09-10) [1999]. "Aritmetikstudier" . Iowa City, Iowa, USA: University of Iowa, Institutionen för datavetenskap. Arkiverad från originalet 2019-07-10 . Hämtad 2016-01-03 .
- Cowlishaw, Mike F. (2015) [1981, 2008]. "Allmän decimalaritmetik" . Arkiverad från originalet 2019-11-02 . Hämtad 2016-01-02 .
- Ingenoso, Tony (1999-02-03) [1998]. "Kapitel 11 - Fler knep i C och Assembler-kod". Få kod att fungera bättre - Hur man minimerar storleken på 80x86 kod och ibland gör den snabbare ( e-bok). Arkiverad från originalet 2019-11-18 . Hämtad 2019-11-18 .
- Anderson, Sean Eron, red. (2009-11-26) [1997]. "Bit Twiddling Hacks" . Stanford University . Arkiverad från originalet 2020-06-01 . Hämtad 2020-06-01 .