Uczta programistow.pdf

IDZ DO

PRZYK£ADOW Y ROZDZIA£

Uczta programistów

SPIS TRECI

KATALOG KSI¥¯EK

Autorzy: Henry S. Warren, Jr.

T³umaczenie: Marek Pêtlicki (rozdz. 1 – 9),

Bart³omiej Garbacz (rozdz. 10 – 16, dod. A, B)

ISBN: 83-7361-220-3

Tytu³ orygina³ u: Hacker's Delight

Format: B5, stron: 336

KATALOG ONLINE

ZAMÓW DRUKOWANY KATALOG

TWÓJ KOSZYK

DODAJ DO KOSZYKA

Do tworzenia wydajnych programów nie wystarczy teoretyczna wiedza o algorytmach,

strukturach danych i in¿ynierii oprogramowania. Istnieje pokana liczba sztuczek,

sprytnych technik i praktycznych rozwi¹zañ, których znajomoæ jest niezbêdna

ka¿demu programicie.

Niniejsza ksi¹¿ka zawiera pokany zestaw technik, które pomog¹ zaoszczêdziæ sporo

czasu. Techniki te zosta³y opracowane przez twórców kodu poszukuj¹cych eleganckich

i wydajnych sposobów tworzenia lepszego oprogramowania. W „Uczcie programistów”

dowiadczony programista Hank Warren dzieli siê z Czytelnikami znanymi sobie

sztuczkami, które zgromadzi³ wraz z imponuj¹cym dowiadczeniem w dziedzinie

programowania aplikacji i systemów operacyjnych. Wiêkszoæ z tych sztuczek jest

niezwykle praktyczna, niektóre zosta³y przedstawione jako ciekawostki lub zaskakuj¹ce

rozwi¹zania. Ich zestawienie stanowi niesamowit¹ kolekcjê, która jest w bêdzie

pomocna nawet dla najbardziej dowiadczonych programistów w rozszerzeniu ich

umiejêtnoci.

W ksi¹¿ce opisano nastêpuj¹ce zagadnienia:

• Obszerna kolekcja u¿ytecznych sztuczek programistycznych

• Drobne algorytmy rozwi¹zuj¹ce czêsto spotykane problemy

• Algorytmy kontroli przekroczenia ograniczeñ

• Zmiana kolejnoci bitów i bajtów

• Dzielenie ca³kowite i dzielenie przez sta³e

• Elementarne operacje na liczbach ca³kowitych

• Kod Gray'a

• Krzywa Hilberta

• Formu³y wyznaczania liczb pierwszych

Niniejsza ksi¹¿ka jest doskona³¹ pozycj¹ dla wszystkich programistów, którzy maj¹

zamiar tworzyæ wydajny kod. „Uczta programistów” nauczy Ciê tworzenia aplikacji

wysokiej jakoci — wy¿szej ni¿ wymagana a uczelniach i kursach programowania.

CENNIK I INFORMACJE

ZAMÓW INFORMACJE

O NOWOCIACH

ZAMÓW CENNIK

CZYTELNIA

FRAGMENTY KSI¥¯EK ONLINE

Wydawnictwo Helion

ul. Chopina 6

44-100 Gliwice

tel. (32)230-98-63

e-mail: helion@helion.pl

Spis treci

Przedmowa...........................................................................................................9

Wstp................................................................................................................11

Rozdział 1. Wprowadzenie .................................................................................13

1.1. Notacja .......................................................................................................................13

1.2. Zestaw instrukcji i model wykonawczy.....................................................................17

Rozdział 2. Podstawy ........................................................................................23

2.1. Manipulowanie prawostronnymi bitami ....................................................................23

2.2. Łczenie dodawania z operacjami logicznymi...........................................................27

2.3. Nierówno"ci w wyra#eniach logicznych i arytmetycznych.......................................29

2.4. Warto"( bezwzgl)dna.................................................................................................30

2.5. Rozszerzenie o znak...................................................................................................31

2.6. Przesuni)cie w prawo ze znakiem za pomoc instrukcji przesuni)cia bez znaku .....32

2.7. Funkcja signum ..........................................................................................................32

2.8. Funkcja porównania trójwarto"ciowego ....................................................................33

2.9. Przeniesienie znaku....................................................................................................34

2.10. Dekodowanie pola „zero oznacza 2 n ”......................................................................34

2.11. Predykaty porówna4.................................................................................................35

2.12. Wykrywanie przepełnienia.......................................................................................40

2.13. Kod warunkowy operacji dodawania, odejmowania i mno#enia.............................49

2.14. Przesuni)cia cykliczne .............................................................................................50

2.15. Dodawanie i odejmowanie liczb o podwójnej długo"ci...........................................51

2.16. Przesuni)cia liczb o podwójnej długo"ci .................................................................52

2.17. Operacje dodawania, odejmowania i wyznaczania warto"ci bezwzgl)dnej

na warto"ciach wielobajtowych......................................................................................53

2.18. Doz, Max oraz Min ..................................................................................................54

2.19. Wymiana warto"ci mi)dzy rejestrami......................................................................56

2.20. Wymiana dwóch lub wi)kszej liczby warto"ci ........................................................59

Rozdział 3. Ograniczenia potg dwójki.................................................................63

3.1. Zaokrglanie do wielokrotno"ci znanych pot)g liczby 2...........................................63

3.2. Zaokrglanie w gór) lub w dół do nast)pnej pot)gi liczby 2.....................................64

3.3. Wykrywanie przekroczenia ogranicze4 pot)gi dwójki..............................................67

Rozdział 4. Ograniczenia arytmetyczne...............................................................71

4.1. Kontrola ogranicze4 liczb całkowitych......................................................................71

4.2. Ograniczenia zakresów w operacjach sumy i ró#nicy ...............................................74

4.3. Ograniczenia zakresów w operacjach logicznych......................................................78

Uczta programistów

Rozdział 5. Zliczanie bitów................................................................................85

5.1. Zliczanie jedynek .......................................................................................................85

5.2. Parzysto"(...................................................................................................................94

5.3. Zliczanie zer wiodcych.............................................................................................97

5.4. Zliczanie zer ko4cowych..........................................................................................104

Rozdział 6. Przeszukiwanie słów ......................................................................111

6.1 Wyszukiwanie pierwszego bajtu o warto"ci 0 ..........................................................111

6.2. Wyszukiwanie pierwszego cigu jedynek o zadanej długo"ci.................................117

Rozdział 7. Manipulacja bitami i bajtami..........................................................121

7.1. Odwracanie kolejno"ci bitów i bajtów.....................................................................121

7.2. Tasowanie bitów ......................................................................................................126

7.3. Transponowanie macierzy bitów .............................................................................128

7.4. Kompresja lub uogólniona ekstrakcja......................................................................137

7.5. Uogólnione permutacje, operacja typu „owce i kozły”............................................143

7.6. Zmiana kolejno"ci oraz transformacje oparte na indeksach.....................................148

Rozdział 8. Mno*enie.......................................................................................151

8.1. Mno#enie czynników wieloelementowych..............................................................151

8.2. Bardziej znaczca połowa 64-bitowego iloczynu....................................................154

8.3. Konwersje mi)dzy bardziej znaczc połow 64-bitowego iloczynu ze znakiem

i bez znaku....................................................................................................................155

8.4. Mno#enie przez stałe................................................................................................156

Rozdział 9. Dzielenie całkowitoliczbowe...........................................................161

9.1. Warunki wst)pne......................................................................................................161

9.2. Dzielenie warto"ci wieloelementowych...................................................................165

9.3. Krótkie dzielenie bez znaku za pomoc dzielenia ze znakiem ................................170

9.4. Długie dzielenie bez znaku ......................................................................................173

Rozdział 10. Dzielenie liczb całkowitych przez stałe................................................181

10.1. Dzielenie ze znakiem przez znan pot)g) liczby 2................................................181

10.2. Reszta ze znakiem z dzielenia przez znan pot)g) liczby 2 ..................................182

10.3. Dzielenie i reszta ze znakiem w przypadku innych warto"ci ni# pot)gi liczby 2..184

10.4. Dzielenie ze znakiem przez dzielniki 2...............................................................187

10.6. Zawieranie obsługi w kompilatorze.......................................................................197

10.7. Inne zagadnienia.....................................................................................................201

10.8. Dzielenie bez znaku ...............................................................................................205

10.9. Dzielenie bez znaku przez dzielniki 1.................................................................207

10.10. Zawieranie obsługi w kompilatorze.....................................................................210

10.11. Inne zagadnienia (dzielenia bez znaku) ...............................................................212

10.12. Zastosowalno"( w przypadku dzielenia z modułem i dzielenia z funkcj podłoga .. 215

10.13. Podobne metody...................................................................................................215

10.14. Przykładowe liczby magiczne..............................................................................216

10.15. Dzielenie dokładne przez stałe.............................................................................217

10.16. Sprawdzanie zerowej reszty po wykonaniu dzielenia przez stał........................225

Rozdział 11. Niektóre funkcje podstawowe ........................................................231

11.1. Całkowitoliczbowy pierwiastek kwadratowy ........................................................231

11.2 Całkowitoliczbowy pierwiastek sze"cienny............................................................239

11.3. Całkowitoliczbowe podnoszenie do pot)gi............................................................241

11.4. Logarytm całkowitoliczbowy.................................................................................243

Spis treci

Rozdział 12. Niezwykłe podstawy systemów liczbowych .....................................251

12.1. Podstawa –2............................................................................................................251

12.2. Podstawa –1 + i......................................................................................................258

12.3. Inne podstawy ........................................................................................................261

12.4. Najbardziej wydajna podstawa...............................................................................262

Rozdział 13. Kod Graya .....................................................................................263

13.1. Kod Graya..............................................................................................................263

13.2. Zwi)kszanie warto"ci liczb całkowitych zakodowanych w kodzie Graya ............266

13.3. Ujemno-binarny kod Graya....................................................................................267

13.4. Rys historyczny i zastosowania..............................................................................268

Rozdział 14. Krzywa Hilberta .............................................................................269

14.1. Rekurencyjny algorytm generowania krzywej Hilberta.........................................271

14.2. Okre"lanie współrz)dnych na podstawie odległo"ci wzdłu# krzywej Hilberta .....273

14.3. Okre"lanie odległo"ci na podstawie współrz)dnych na krzywej Hilberta.............280

14.4. Zwi)kszanie warto"ci współrz)dnych na krzywej Hilberta...................................282

14.5. Nierekurencyjny algorytm generowania................................................................285

14.6. Inne krzywe wypełniajce przestrze4 ....................................................................285

14.7. Zastosowania..........................................................................................................286

Rozdział 15. Liczby zmiennopozycyjne................................................................289

15.1. Standard IEEE........................................................................................................289

15.2. Porównywanie liczb zmiennopozycyjnych za pomoc operacji

całkowitoliczbowych....................................................................................................292

15.3. Rozkład cyfr wiodcych.........................................................................................293

15.4. Tabela ró#nych warto"ci.........................................................................................295

Rozdział 16. Wzory na liczby pierwsze................................................................299

16.1. Wprowadzenie........................................................................................................299

16.2. Wzory Willansa......................................................................................................301

16.3. Wzory Wormella....................................................................................................305

16.4. Wzory na inne trudne funkcje................................................................................306

Dodatek A Tablice arytmetyczne dla maszyny 4-bitowej...................................313

Dodatek B Metoda Newtona ...........................................................................319

Bibliografia.......................................................................................................321

Skorowidz.........................................................................................................325

Rozdział 7.

Manipulacja

bitami i bajtami

7.1. Odwracanie kolejnoci

bitów i bajtów

Przez operacje odwrócenia kolejnoci bitów (ang. reversing bits ) rozumiemy wykonanie

„odbicia lustrzanego”, na przykład:

rev(

0x01234567

) =

0xE6A2C480

Przez operacj" odwrócenia bajtów rozumiemy podobne odbicie, z tym, $e w tym przy-

padku odwracamy kolejno&' bajtów w słowie. Odwracanie kolejno&ci bajtów jest opera-

cj) konieczn) w przypadku konwersji pomi"dzy formatami little-endian , stosowanymi

w procesorach DEC oraz Intel a formatem big-endian , stosowanym przez wi"kszo&' po-

zostałych producentów procesorów.

Odwrócenie kolejno&ci bitów mo$e zosta' wykonane w stosunkowo wydajny sposób

przez zamian" kolejno&ci s)siaduj)cych bitów, nast"pnie zamian" kolejno&ci w s)siadu-

j)cych parach pól 2-bitowych itd. [Aus1]. Poni$ej przedstawiamy przykład realizacji tego

mechanizmu. Wszystkie operacje przypisania mo$na wykona' w dowolnej kolejno&ci.

Na wi"kszo&ci maszyn jest mo$liwe dokonanie niewielkiego usprawnienia, polegaj)ce-

go na wykorzystaniu mniejszej liczby ró$nych stałych oraz na wykonaniu ostatnich dwóch

przypisa7 w bardziej bezpo&redni sposób, tak jak zostało przedstawione na listingu 7.1

(30 instrukcji z podstawowego zestawu RISC, bez rozgał"zie7).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: