해커의 기쁨 (제2판)

Chapter 1 소개
1-1 표기법 1
1-2 명령 집합과 실행 시간 모형 6

Chapter 2 기초
2-1 제일 오른쪽 비트 다루기 13
2-2 논리 연산과 결합된 덧셈 19
2-3 논리식과 산술식의 부등 21
2-4 절댓값 함수 22
2-5 두 정수의 평균 22
2-6 부호 확장 23
2-7 부호 없는 오른쪽 자리이동으로 부호 있는 오른쪽 자리이동 구현 24
2-8 부호 함수 25
2-9 세 값 비교 함수 25
2-10 부호 전달 함수 26
2-11 “0은 2**n을 뜻함” 필드의 복호화 27
2-12 비교 술어 27
2-13 넘침 검출 33
2-14 더하기, 빼기, 곱하기 결과의 조건 부호 43
2-15 순환 자리이동 44
2-16 두 배 길이 더하기·빼기 명령 45
2-17 두 배 길이 자리이동 46
2-18 다중 바이트 덧셈, 뺄셈, 절댓값 47
2-19 차 또는 0(doz), 최댓값(max), 최솟값(min) 49
2-20 레지스터 교환 54
2-21 둘 이상의 값들을 교대로 설정 57
2-22 부울 분해 공식 60
2-23 열여섯 가지 이항 부울 연산을 모두 구현하는 명령들 62

Chapter 3 2의 거듭제곱 경계들
3-1 알려진 2의 거듭제곱의 배수로 반올림·반내림 69
3-2 그다음 2의 거듭제곱으로의 반올림·반내림 70
3-3 2의 거듭제곱 경계 횡단 검출 73

Chapter 4 산술 경계
4-1 정수 경계 점검 77
4-2 더하기와 빼기를 통한 경계 전파 80
4-3 논리 연산을 통한 경계 전파 84

Chapter 5 비트 개수 세기
5-1 값이 1인 비트 세기 91
5-2 패리티 108
5-3 선행 0 개수 세기 111
5-4 후행 0 개수 세기 121

Chapter 6 워드 검색
6-1 첫 0-바이트 찾기 133
6-2 주어진 길이의 첫 1-비트열 찾기 140
6-3 가장 긴 1-비트열 찾기 143
6-4 가장 짧은 1-비트열 찾기 145

Chapter 7 비트와 바이트의 재배치
7-1 비트, 바이트 뒤집기 149
7-2 비트 뒤섞기 161
7-3 비트 행렬의 전치 163
7-4 압축 또는 일반화된 추출 173
7-5 확장 또는 일반화된 삽입 180
7-6 압축과 확장을 위한 하드웨어 알고리즘 181
7-7 일반적인 치환과 ‘양과 염소’ 연산 186
7-8 재배치와 색인 변환 191
7-9 LRU 알고리즘 192

Chapter 8 곱셈
8-1 다중워드 곱셈 197
8-2 64비트 곱의 상위 절반 200
8-3 부호 있는/없는 상위 곱의 상호 변환 201
8-4 상수 곱하기 202

Chapter 9 정수 나눗셈
9-1 소개 207
9-2 다중워드 나눗셈 211
9-3 부호 있는 나눗셈을 이용한 부호 없는 짧은 나눗셈 216
9-4 부호 없는 긴 나눗셈 219
9-5 긴 나눗셈을 이용한 이중워드 나눗셈 225

Chapter 10 상수가 제수인 정수 나눗셈
10-1 알려진 2의 거듭제곱이 제수인 부호 있는 나눗셈 233
10-2 알려진 2의 거듭제곱이 제수인 나눗셈의 부호 있는 나머지 구하기 234
10-3 제수가 2의 거듭제곱이 아닌 부호 있는 나눗셈과 나머지 236
10-4 제수가 2 이상인 부호 있는 나눗셈 240
10-5 제수가 -2 이하인 부호 있는 나눗셈 249
10-6 컴파일러에 통합 251
10-7 기타 주제들 255
10-8 부호 없는 나눗셈 259
10-9 제수가 1 이상인 부호 없는 나눗셈 262
10-10 컴파일러에 통합(부호 없는 경우) 265
10-11 기타 주제들(부호 없는 경우) 268
10-12 법·바닥 나눗셈에 대한 적용 가능성 271
10-13 비슷한 방법들 271
10-14 마법의 수들의 예 273
10-15 간단한 파이썬 코드 274
10-16 제수가 상수인 완전 나눗셈 274
10-17 상수로 나눈 나머지가 0인지 점검 283
10-18 상위 곱하기 명령을 사용하지 않는 방법들 287
10-19 숫자들의 합산을 통한 나머지 계산 299
10-20 곱셈과 오른쪽 자리이동을 이용한 나머지 계산 306
10-21 완전 나눗셈으로의 변환 313
10-22 시간 측정 315
10-23 제수가 3인 나눗셈을 위한 회로 316

Chapter 11 기본 함수 몇 가지
11-1 정수 제곱근 319
11-2 정수 세제곱근 328
11-3 정수 거듭제곱 329
11-4 정수 로그 332

Chapter 12 색다른 기수의 수체계
12-1 기수 -2 341
12-2 기수 -1 + i 수체계 349
12-3 기타 기수들 352
12-4 가장 효율적인 기수는? 353

Chapter 13 그레이 부호
13-1 그레이 부호 355
13-2 그레이 부호화 정수의 증가 358
13-3 음이진 그레이 부호 360
13-4 간략한 역사 및 응용 360

Chapter 14 순환 중복 검사(CRC)
14-1 소개 365
14-2 이론 367
14-3 실제 응용 370

Chapter 15 오류 보정 부호
15-1 소개 379
15-2 해밍 부호 380
15-3 정보 비트 32개용 SEC-DED를 위한 소프트웨어 386
15-4 오류 보정에 대한 좀 더 일반적인 고찰 392

Chapter 16 힐베르트 곡선
16-1 힐베르트 곡선의 생성을 위한 재귀적 알고리즘 406
16-2 힐베르트 곡선을 따라 이동한 거리에 따른 좌표 계산 410
16-3 힐베르트 곡선의 한 점까지의 거리 417
16-4 힐베르트 곡선에서의 좌표 증가 419
16-5 비재귀적 생성 알고리즘 422
16-6 그 외의 공간 채움 곡선 423
16-7 응용 424

Chapter 17 부동소수점
17-1 IEEE 형식 428
17-2 부동소수점-정수 상호 변환 430
17-3 정수 연산을 이용한 부동소수점 수들의 비교 434
17-4 제곱근의 역수 근사 루틴 436
17-5 선행 숫자들의 분포 439
17-6 그 외의 여러 값들 441

Chapter 18 소수를 위한 공식들
18-1 소개 445
18-2 윌런스의 공식 448
18-3 워멜의 공식 452
18-4 그 밖의 어려운 함수에 대한 공식들 453

연습문제 해답

부록 A 4비트 컴퓨터를 위한 산술 연산표 517
부록 B 뉴턴의 반복법 523
부록 C 이산 함수 그래프 모음 527
C-1 정수에 대한 논리 연산들의 그래프 527
C-2 덧셈, 뺄셈, 곱셈 그래프 529
C-3 나눗셈 관련 함수들의 그래프 531
C-4 압축, SAG, 왼쪽 순환 자리이동 함수의 그래프 533
C-5 몇 가지 단항 함수들의 그래프 534

참고문헌 539
찾아보기 548

이번 절에서는 오른쪽으로 압축 함수와 그 역함수를 위한 하드웨어 지향적 알고리즘들을 제시한다([Zadeck]). 이전 절의 알고리즘들처럼 이번 절의 알고리즘들은 그 실행 시간이 컴퓨터의 워드 크기의 로그에 비례한다. 이 알고리즘들은 하드웨어에서 구현하기에 적합하지만, 기본 RISC 명령들로 구현한다면 빠른 코드가 나오지 않는다. 따라서 C나 기계어 코드는 제시하지 않고 작동 방식만 설명하겠다.

지금 풀고자 하는 문제는, 캐시 적중 실패(cache misss; 즉, 특정 주소에 있는 워드가 요청되었는데 그 주소의 자료가 캐시에 없는 상황)가 발생했을 때, 캐시의 블록(또는, 캐시 쪽 용어로 라인line)들 중 요청된 자료로 대체할 것을 컴퓨터가 어떻게 결정하는가이다. 이상적인 선택은 향후 제일 오랫동안 참조되지 않을 캐시 라인의 자료를 대체하는 것이다. 그러나 미래를 알 수는 없는 일이므로 추측이 필요하다. 다양한 응용 프로그램에 대한 최선의 추측으로 간주되는 것이 바로 최근 최소 사용(least recently used, LRU) 방침이다.