Uczta programistow.pdf
(
638 KB
)
Pobierz
C:\Andrzej\PDF\ABC nagrywania p³yt CD\1 strona.cdr
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
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).
Plik z chomika:
kronos78
Inne pliki z tego folderu:
Asembler dla procesorow Intel Vademecum profesjonalisty.pdf
(400 KB)
Asembler cwiczenia praktyczne.pdf
(358 KB)
Architektura systemow zarzadzania przedsiebiorstwem Wzorce projektowe.pdf
(829 KB)
Architektura oprogramowania Metody oceny oraz analiza przypadkow.pdf
(429 KB)
Aplikacje w Visual C++ 2005 Przyklady.pdf
(296 KB)
Inne foldery tego chomika:
!!!!!!!!ze słowackiego radia, niektore opisanie, inne nie
# - Wzory CV
▶ Porady remontowo - budowlane
▶ Remont domu - poradnik
• AGD - kody błędów pralek automatycznych
Zgłoś jeśli
naruszono regulamin