우아한 프로그래밍, 바로 써먹는 알고리즘!

프로그래밍 핵(hack) 모음집. 프로그래머가 좀 더 우아하고 효율적인 소프트웨어를 만드는 데 도움이 되는 시간 절약 기법들과 알고리즘, 요령들이 담겼다. 이 책이 제시하는 핵들은 실용적이면서 흥미롭고, 예기치 못한 측면까지 보여주면서 프로그래밍에 대한 좀 더 깊은 통찰을 제공한다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

연습문제 해답

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

참고문헌
찾아보기