Index
0-bits, leading zeros. See nlz function.
0-bits, trailing zeros. See also ntz (number of trailing zeros) function.
detecting, 324. See also CRC (cyclic redundancy check).
plots and graphs, 466
1-bits, counting. See Counting bits.
The 16 Boolean binary operations, 53–57
A
Absolute value
computing, 18
add instruction
propagating arithmetic bounds, 70–73
Addition
arithmetic tables, 453
combined with logical operations, 16–17
of negabinary numbers, 301–302
plots and graphs, 461
in various number encodings, 304–305
Advanced Encryption Standard, 164
Alternating among values, 48–51
and
plots and graphs, 459
in three instructions, 17
and with complement, 131
Answers to exercises, by chapter
3: Power-of-2 Boundaries, 415–416
7: Rearranging Bits and Bytes, 423–425
10: Integer Division by Constants, 431–434
11: Some Elementary Functions, 434–435
12: Unusual Bases for Number Systems, 435–439
14: Cyclic Redundancy Check, 441–442
15: Error-Correcting Codes, 442–445
16: Hilbert‘s Curve, 446
18: Formulas for Primes, 448–452
Arithmetic, computer vs. ordinary, 1
range analysis, 70
searching for values in, 122
Arithmetic tables, 4-bit machine, 453–456
Arrays
checking bounds. See Arithmetic bounds.
indexes, checking. See Arithmetic bounds.
indexing a sparse array, 95
Autodin-II polynomial, 323
B
Base –1 + i number system, 306–308
extracting real and imaginary parts, 310
Base –1 – i number system, 308–309
Base –2 number system, 299–306
Gray code, 315
rounding down, 310
Basic RISC instruction set, 5–6
Basic, Wang System 2200B, 55
Big-endian format, converting to little-endian, 129
Binary decomposition, integer exponentiation, 288–290
Binary forward error-correcting block codes (FEC), 331
Binary search
Bit matrices, multiplying, 98
computing parity. See Parity.
counting bits. See Counting bits.
finding strings of 1-bits, 123–128
flipping bits, 135
generalized bit reversal, 135
half shuffle, 141
inner perfect shuffle, plots and graphs, 468–469
inner perfect unshuffle, plots and graphs, 468
numbering schemes, 1
reversing bits. See Reversing bits and bytes.
on rightmost bits. See Rightmost bits.
searching words for bit strings, 107, 123–128
sheep and goats operation, 161–165
shuffling bits, 139–141, 165–166
transposing a bit matrix, 141–150
unshuffling bits, 140–141, 150, 162
Bit reversal function, plots and graphs, 467
Bit vectors, 1
bitgather instruction, 163–165
Bits. See specific topics.
Bliss, Robert D., xv
Bonzini, Paolo, 263
Boole, George, 54
Boolean binary operations, all 16, 53–57
Boolean decomposition formula, 51–53, 56–57
Boundary crossings, powers of 2, 63–64
Bounds, arithmetic. See Arithmetic bounds.
Bounds checking. See Checking arithmetic bounds.
branch on carry and register result nonzero instruction, 63
Bytes. See also specific topics.
definition, 1
C
C language
arithmetic on pointers, 105, 240
GNU extensions, 105
referring to same location with different types, 104
representation of character strings, 117
Carry-save adder (CSA) circuit, 90–95
CCITT (Le Comité Consultatif Internationale...), 321
Ceiling function, identities, 183–184
Chang, Albert, 123
Character strings, 117
Check bits
Hamming code, 332
Checking arithmetic bounds, 67–69
Chinese ring puzzle, 315
Chipkill technology, 336
Code, definition, 343
Code rate, 343
Code size, 343
Comparison predicates
definition, 23
number of leading zeros (nlz) function, 23–24, 107
signed comparisons, from unsigned, 25
true/false results, 23
using negative absolute values, 23–26
Comparisons
computer evaluation of, 27
floating-point comparisons using integer operations, 381–382
three-valued compare function, 21–22. See also sign function.
Compress function, plots and graphs, 464–465
compress operation, 119, 150–161
with insert and extract instructions, 155–156
Computability test, right-to-left, 13–14, 55
Computer arithmetic
definition, 1
Constants
dividing by. See Division of integers by constants.
Counting bits. See also ntz (number of trailing zeros) function; nlz (number of leading zeros) function; population count function.
1-bits in
7- and 8-bit quantities, 87
divide and conquer strategy, 81–82
leading 0‘s, with
floating-point methods, 104–106
population count instruction, 101–102
search tree method, 109
by turning off 1-bits, 85
check bits, generating, 319–320
checksum, computing
generator polynomials, 322–323, 329
techniques for, 320
code vector, 319
definition, 319
feedback shift register circuit, 325–326
generator polynomial, choosing, 322–323, 329
practice
leading zeros, detecting, 324
residual/residue, 324
trailing zeros, detecting, 324
CRC codes, generator polynomials, 322, 323
CRC-CITT polynomial, 323
Advanced Encryption Standard, 164
bitgather instruction, 164–165
DES (Data Encryption Standard), 164
Rijndael algorithm, 164
Triple DES, 164
CSA (carry-save addr) circuit, 90–95
Cube root, approximate, floating-point, 389
Curves. See also Hilbert‘s curve.
D
Davio decomposition, 51-53, 56–57
de Kloet, David, 55
Decryption. See Cryptography.
DES (Data Encryption Standard), 164
difference or zero (doz) function, 41–45
Distribution of leading digits, 385–387
Divide and conquer strategy, 81–82
Division
arithmetic tables, 455
doubleword
of negabinary numbers, 302–304
nonrestoring algorithm, 192–194
notation, 181
shift-and-subtract algorithms (hardware), 192–194
signed
computer, 181
long, 189
multiword, 188
unsigned
computer, 181
Division of integers by constants
exact division
definition, 240
multiplicative inverse, Euclidean algorithm, 242–245
multiplicative inverse, Newton‘s method, 245–247
multiplicative inverse, samples, 247–248
floor division, 237
incorporating into a compiler, signed, 220–223
incorporating into a compiler, unsigned, 232–234
magic numbers
calculating, signed, 212–213, 220–223
calculating, unsigned, 231–234
definition, 211
table lookup, 237
uniqueness, 224
magicu2 algorithm, 236
modulus division, 237
remainder by multiplication and shifting right
remainder by summing digits
signed
incorporating into a compiler, 220–223
not using mulhs (multiply high signed), 259–262
remainder by multiplication and shifting right, 273–274
remainder by summing digits, 266–268
remainder from powers of 2, 206–207
test for zero remainder, 250–251
uniqueness, 224
timing test, 276
unsigned
by powers of 2, 227
incorporating into a compiler, 232–234
incremental division and remainder technique, 232–234
not using mulhu (multiply high unsigned) instruction, 251–259
remainder by multiplication and shifting right, 268–272
remainder by summing digits, 262–266
remainder from powers of 2, 227
test for zero remainder, 248–250
Double buffering, 46
Double-length addition/subtraction, 38–39
Doubleword division
Doublewords, definition, 1
doz (difference or zero) function, 41–45
Dubé, Danny, 112
E
ECCs (error-correcting codes)
check bits, 332
code, definition, 343
code rate, 343
code size, 343
coding theory problem, 345–351
efficiency, 343
FEC (binary forward error-correcting block codes), 331
Gilbert-Varshamov bound, 348–350
converting to SEC-DED code, 334–337
SEC-DED on 32 information bits, 337–342
information bits, 332
SEC (single error-correcting) codes, 331
SEC-DED (single error-correcting, double error-detecting) codes
on 32 information bits, 337–342
check bits, minimum required, 335
converting from Hamming code, 334–337
definition, 331
singleton bound, 352
sphere-packing bound, 348, 350
Encryption. See Cryptography.
End-around-carry, 38, 56, 304–305
Error detection, digital data. See CRC (cyclic redundancy check).
Estimating multiplication overflow, 33–34
Euler, Leonhard, 392
Even parity, 96
Exact division
definition, 240
multiplicative inverse, Euclidean algorithm, 242–245
multiplicative inverse, Newton‘s method, 245–247
multiplicative inverse, samples, 247–248
Exchanging
conditionally, 47
corresponding register fields, 46
two fields in same register, 47
exclusive or
plots and graphs, 460
propagating arithmetic bounds through, 77–78
scan operation on an array of bits, 97
in three instructions, 17
Exercise answers. See Answers to exercises.
Expand operation, 156–157, 159–161
Exponentiation
by binary decomposition, 288–290
in Fortran, 290
Extended Hamming code, 334–342
on 32 information bits, 337-342
F
Factoring, 178
FEC (binary forward error-correcting block codes), 331
feedback shift register circuit, 325–326
Fermat numbers, 391
FFT (Fast Fourier Transform), 137–139
find rightmost 0-byte, 118–121
decimal digits, 122
first uppercase letter, 122
length of character strings, 117
next higher number, same number of 1-bits, 14–15
strings of 1-bits
first string of a given length, 123–125
values within arithmetic bounds, 122
Flipping bits, 135
Floating-point numbers, 375–389
distribution of leading digits, 385–387
formats (single/double), 375–376
gradual underflow, 376
IEEE arithmetic standard, 375
table of miscellaneous values, 387–389
ulp (unit in the last position), 378
Floating-point operations
approximate cube root, 389
approximate reciprocal square root, 383–385
approximate square root, 389
comparing using integer operations, 381–382
converting to/from integers, 377–381
counting leading 0‘s with, 104–106
simulating, 107
Floor function, identities, 183, 202–203
Floyd, R. W., 114
Fortran
IDIM function, 44
integer exponentiation, 290
ISIGN function, 22
MOD function, 182
Fractal triangles, plots and graphs, 460
Full adders, 90
Full RISC instruction set, 7
Fundamental theorem of arithmetic, 404
G
Gardner, Martin, 315
Gaudet, Dean, 110
Gaudet‘s algorithm, 110
generalized extract operation, 150–156
Generalized unshuffle. See SAG (sheep and goats) operation.
Generator polynomials, CRC codes, 321–323
Gilbert-Varshamov bound, 348–350
Golay, M. J. E., 331
Goryavsky, Julius, 103
Gosper, R. W.
iterating through subsets, 14–15
Gradual underflow, 376
Graphics-rendering, Hilbert‘s curve, 372–373
Graphs. See Plots and graphs.
Gray, Frank, 315
Gray code
balanced, 317
converting integers to, 97, 312–313
cyclic, 312
definition, 311
incrementing Gray-coded integers, 313–315
negabinary Gray code, 315
plots and graphs, 466
Greatest common divisor function, plots and graphs, 464
GRP instruction, 165
H
Hacker, definition, xvi
HAKMEM (hacks memo), xiii
Half shuffle, 141
Halfwords, 1
Hamiltonian paths, 315
Hamming, R. W., 331
Hamming code
on 32 information bits, 337–342
converting to SEC-DED code, 334–337
triangle inequality, 352
Hexadecimal floating-point, 385
High-order half of product, 173–174
Hilbert, David, 355
Hilbert‘s curve. See also Space-filling curves.
coordinates from distance
curve generator driver program, 359
Lam and Shapiro method, 362–364, 368
parallel prefix operation, 365–366
state transition table, 361, 367
distance from coordinates, 366–368
incrementing coordinates, 368–371
non-recursive generation, 371
ray tracing, 372
three-dimensional analog, 373
Horner‘s rule, 49
I
IBM
Chipkill technology, 336
Harvest computer, 336
PCs, error checking, 336
PL/I language, 54
System/360 computer, 385
System/370 computer, 63
IDIM function, 44
IEEE arithmetic standard, 375
IEEE format, floating-point numbers, 375–377
IEEE Standard for Floating-Point Arithmetic, 375
Image processing, Hilbert‘s curve, 372
Incremental division and remainder technique, 232–234
Inequalities, logical and arithmetic expressions, 17–18
Information bits, 332
Inner perfect shuffle function, plots and graphs, 468–469
Inner perfect unshuffle function, plots and graphs, 468
Instruction level parallelism, 9
Instruction set for this book, 5–8
integer cube root function, 287–288, 297
Integer exponentiation, 288–290
integer fourth root function, 297
integer log base 2 function, 106, 291
integer log base 10 function, 292–297
Integer quotient function, plots and graphs, 463
integer remainder function, 463
integer square root function, 279–287
Integers. See also specific operations on integers.
converting to/from floating-point, 377–381
converting to/from Gray code, 97, 312–313
reversed, incrementing, 137–139
Inverse Gray code function
formula, 312
plots and graphs, 466
An Investigation of the Laws of Thought, 54
ISIGN (transfer of sign) function, 22
Iterating through subsets, 14–15
ITU-TSS (International Telecommunications Union...), 321
ITU-TSS polynomial, 323
K
Knuth, Donald E., 132
Knuth‘s Algorithm M, 171–172, 174–175
Knuth‘s mod operator, 181
Kronecker, Leopold, 375
L
Lam and Shapiro method, 362–364, 368
Landry, F., 391
Leading 0‘s, counting, 99–106. See also nlz (number of leading zeros) function.
Leading 0’s, detecting, 324. See also CRC (cyclic redundancy check).
Leading digits, distribution, 385–387
Least common multiple function, plots and graphs, 464
Little-endian format, converting to/from big-endian, 129
load word byte-reverse (lwbrx) instruction, 118
Logarithms
definition, 291
Logical operations
with addition and subtraction, 16–17
and, plots and graphs, 459
binary, table of, 17
exclusive or, plots and graphs, 460
or, plots and graphs, 459
propagating arithmetic bounds through, 74–76, 78
Logical operators on integers, plots and graphs, 459–460
Long Division, definition, 189
LRU (least recently used) algorithm, 166–169
lwbrx (load word byte-reverse) instruction, 118
M
MacLisp, 55
magic algorithm
incremental division and remainder technique, 232–234
Magic numbers
calculating, signed, 212–213, 220–223
calculating, unsigned, 232–234
calculating, Python code for
definition, 211
table lookup, 237
uniqueness, 224
in Python, 240
Mills, W. H., 403
MIT PDP-6 Lisp, 55
MOD function (Fortran), 182
modu (unsigned modulus) function, 98
Modulus division, 181–182, 237
Moore, Eliakim Hastings, 371–372
mulhs (multiply high signed) instruction
division with, 207–210, 212, 218, 222, 235
implementing in software, 173–174
mulhu (multiply high unsigned) instruction
division with, 228–229, 234–235, 238
implementing in software, 173
Multibyte absolute value, 40–41
Multibyte addition/subtraction, 40–41
Multiplication
arithmetic tables, 454
factoring, 178
low-order halves independent of signs, 178
high-order half of 64-bit product, 173–174
high-order product signed from/to unsigned, 174–175
of negabinary numbers, 302
plots and graphs, 462
Multiplicative inverse
multiply instruction, condition codes, 36–37
Multiword multiplication, 171–173
mux (multiplex) operation, 42, 56, 131, 163, 406
N
NAK (negative acknowledgment), 319
Negabinary number system, 299–306
Gray code, 315
Negative absolute value, 23–26
Negative overflow, 30
Newton-Raphson calculation, 383
multiplicative inverse, 245–248
Next higher number, same number of 1-bits, 14–15
Nibbles, 1
nlz (number of leading zeros) function
comparison predicates, 23–24, 107
for counting trailing 0‘s, 107
finding 0-bytes, 118
finding strings of 1-bits, 123–124
incrementing reversed integers, 138
and integer log base 2 function, 106
rounding to powers of 2, 61
Nonrestoring algorithm, 192–194
Normalized numbers, 376
Notation used in this book, 1–4
nth prime, finding
ntz (number of trailing zeros) function
from counting leading 0‘s, 107
ruler function, 114
Number systems
O
Odd parity, 96
1-bits, counting. See Counting bits.
or
plots and graphs, 459
in three instructions, 17
Ordinary arithmetic, 1
Ordinary rational division, 181
Outer perfect shuffle bits function, plots and graphs, 469
Outer perfect shuffle function, plots and graphs, 467
Outer perfect unshuffle function, plots and graphs, 468
Overflow detection
definition, 28
estimating multiplication overflow, 33–34
negative overflow, 30
unsigned add/subtract, 31
P
Parallel prefix operation
definition, 97
inverse, 116
parity, 97
Parallel suffix operation
expand operation, 156–157, 159–161
inverse, 116
adding to 7-bit quantities, 98
applications, 98
definition, 96
parallel prefix operation, 97
scan operation, 97
two-dimensional, 352
PCs, error checking, 336
Peano, Giuseppe, 355
Peano curves, 371–372. See also Hilbert‘s curve.
Peano-Hilbert curve. See Hilbert‘s curve.
Permutations on bits, 161–165. See also Bit operations.
Planar curves, 355. See also Hilbert‘s curve.
addition, 461
bit reversal function, 467
fractal triangles, 460
Gray code function, 466
greatest common divisor function, 464
inner perfect shuffle, 468–469
inner perfect unshuffle, 468
integer quotient function, 463
inverse Gray code function, 466
least common multiple function, 464
logical and function, 459
logical exclusive or function, 460
logical operators on integers, 459–460
logical or function, 459
multiplication, 462
number of trailing zeros, 466
outer perfect shuffle, 467–469
outer perfect unshuffle, 468
population count function, 467
remainder function, 463
rotate left function, 465
ruler function, 466
SAG (sheep and goats) function, 464–465
self-similar triangles, 460
Sierpinski triangle, 460
subtraction, 461
unsigned product of x and y, 462
population count function. See also Counting bits.
computing Hamming distance, 95
counting 1-bits, 81
counting trailing 0‘s, 107–114
plots and graphs, 467
Powers of 2
boundary crossings, detecting, 63–64
unsigned division, 227
PPERM instruction, 165
Prime numbers
Fermat numbers, 391
from polynomials, 392
Propagating arithmetic bounds
add and subtract instructions, 70–73
PSHUFB (Shuffle Packed Bytes) instruction, 163
PSHUFD (Shuffle Packed Doublewords) instruction, 163
PSHUFW (Shuffle Packed Words) instruction, 163
Q
Quicksort, 81
R
Range analysis, 70
Ray tracing, Hilbert‘s curve, 372
Rearrangements and index transformations, 165–166
Reed-Muller decomposition, 51-53, 56–57
Reference matrix method (LRU), 166–169
Reflected binary Gray code, 311–312, 315
Registers
exchanging conditionally, 47
reversing contents of, 129–135
RISC computers, 5
Reiser, John, 113
Remainder function, plots and graphs, 463
Remainders
arithmetic tables, 456
of signed division
by multiplication and shifting right, 273–274
of unsigned division
by multiplication and shifting right, 268–272
and immediate instruction, 227
incremental division and remainder technique, 232–234
Residual/residue, 324
Reversing bits and bytes, 129–137
6-, 7-, 8-, and 9-bit quantities, 135–137
big-endian format, converting to little-endian, 129
definition, 129
generalized, 135
load word byte-reverse (lwbrx) instruction, 118
rightmost 16 bits of a word, 130
table lookup, 134
Riemann hypothesis, 404
Right justify function, 116
Rightmost bits, manipulating, 11–12, 15
right-to-left computability test, 13–14, 55
Rijndael algorithm, 164
RISC
Rotate left function, plots and graphs, 464–465
Rounding to powers of 2, 59–62, 64
Russian decomposition, 51-53, 56–57
S
SAG (sheep and goats) operation
Scan operation, 97
Search tree method, 109
Searching. See Finding.
SEC (single error-correcting) codes, 331
SEC-DED (single error-correcting, double error-detecting) codes
on 32 information bits, 337–342
check bits, minimum required, 335
converting from Hamming code, 334–335
definition, 331
Select instruction, 406
Self-reproducing program, xvi
Self-similar triangles, plots and graphs, 460
shift left double operation, 39
shift right double signed operation, 39–40
shift right double unsigned operation, 39
shift right extended immediate (shrxi) instruction, 228–229
shift right signed instruction
alternative to, for sign extension, 19–20
division by power of 2, 205–206
from unsigned, 20
Shift-and-subtract algorithm
Shifts
Short division, 189–192, 195–196
shrxi (shift right extended immediate) instruction, 228–229
Shuffle Packed Bytes (PSHUFB) instruction, 163
Shuffle Packed Doublewords (PSHUFD) instruction, 163
Shuffle Packed Words (PSHUFW) instruction, 163
Shuffling
bits
half shuffle, 141
inner perfect shuffle, plots and graphs, 468–469
inner perfect unshuffle, plots and graphs, 468
shuffling bits, 139–141, 165–166
unshuffling, 140–141, 150, 162, 165-166
Sierpinski triangle, plots and graphs, 460
sign function, 20–21. See also three-valued compare function.
Signed bounds, 78
Signed comparisons, from unsigned, 25
Signed computer division, 181–182
Signed division
arithmetic tables, 455
computer, 181
long, 189
multiword, 188
Signed division of integers by constants
incorporating into a compiler, 220–223
remainder from non-powers of 2, 207–210
remainder from powers of 2, 206–207
test for zero remainder, 250–251
uniqueness of magic number, 224
Signed long division, 189
Signed numbers, propagating arithmetic bounds, 71–73
Signed short division, 190–192
Single error-correcting, double error-detecting (SEC-DED) codes. See SEC-DED (single error-correcting, double error-detecting) codes.
Single error-correcting (SEC) codes, 331
Space-filling curves, 371–372. See also Hilbert‘s curve.
Sparse array indexing, 95
Spheres, ECCs (error-correcting codes), 347–350
Square root, integer
shift-and-subtract algorithm, 285–287
Square root, approximate, floating-point, 389
Square root, approximate reciprocal, floating-point, 383–385
Stibitz, George, 308
Strachey, Christopher, 130
Strings. See Bit operations; Character strings.
strlen (string length) C function, 117
Subnormal numbers, 376
Subnorms, 376
subtract instruction
propagating arithmetic bounds, 70–73
Subtraction
arithmetic tables, 453
difference or zero (doz) function, 41–45
combined with logical operations, 16–17
of negabinary numbers, 301–302
plots and graphs, 461
Swap-and-complement method, 362–365
Swapping pointers, 46
System/360 computer, 385
System/370 computer, 63
T
Table lookup, counting bits, 86–87
three-valued compare function, 21–22. See also sign function.
Tight bounds
add and subtract instructions, 70–73
Timing test, division of integers by constants, 276
Tower of Hanoi puzzle, 116, 315
Trailing zeros. See also ntz (number of trailing zeros) function.
detecting, 324. See also CRC (cyclic redundancy check).
plots and graphs, 466
Transfer of sign (ISIGN) function, 22
Transposing a bit matrix
Triangles
fractal, 460
plots and graphs, 460
self-similar, 460
Sierpinski, 460
Triple DES, 164
True/false comparison results, 23
Turning off 1-bits, 85
U
Ulp (unit in the last position), 378
Unaligned load, 65
Unary functions, plots and graphs, 466–469
Uniqueness, of magic numbers, 224
Unshuffling
arrays, 162
Unsigned division
arithmetic tables, 455
computer, 181
Unsigned division of integers by constants
by powers of 2, 227
incorporating into a compiler, 232–234
incremental division and remainder technique, 232–234
remainders, from powers of 2, 227
test for zero remainder, 248–250
unsigned modulus (modu) function, 84
Unsigned product of x and y, plots and graphs, 462
Uppercase letters, finding, 122
V
Voorhies, Douglas, 373
W
Willans, C. P., 393
Word parity. See Parity.
Words
definition, 1
division
doubleword by single word, 192–197
signed, multiword, 188
multiplication, multiword, 171–173
searching for
first uppercase letter, 122
a value within a range, 122
word parallel operations, 13
Wormell, C. P., 397