Uczta programistow, Programowanie

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
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³
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
 6
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
7
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).
  [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •