Computer Systems: A Programmer's Perspective Chương 2 · Representing and Manipulating Information

Chương 2 · Biểu diễn và thao tác thông tin Chapter 2 · Representing and Manipulating Information

Một bit không có nghĩa gì cho đến khi bạn chọn cách diễn giải nó Số 0 và 1 chỉ có nghĩa khi ta nói chúng nghĩa là gì A bit means nothing until you choose how to interpret it

Bryant và O'Hallaron mở đầu bằng một sự thật nền tảng: máy tính hiện đại lưu và xử lý thông tin dưới dạng tín hiệu hai mức — những chữ số nhị phân, hay bit.1 Một bit đứng lẻ thì gần như vô dụng; chỉ khi ta gộp các bit lại và áp một cách diễn giải lên các mẫu bit có thể có, chúng mới biểu diễn được phần tử của một tập hữu hạn bất kỳ.1

Máy tính chỉ biết hai thứ: bật và tắt, viết là 1 và 0. Mỗi chữ số ấy gọi là một bit. Một bit đứng một mình thì chẳng nói lên điều gì — giống một ngón tay giơ lên, chưa biết là đang đếm hay đang chỉ đường. Phải gộp nhiều bit lại và thoả thuận “nhóm này nghĩa là một con số, nhóm kia là một chữ cái” thì chúng mới có nghĩa. Nhớ nhé: bit chỉ có nghĩa khi ta quy ước nó nghĩa là gì.

Bryant and O'Hallaron open with a foundational fact: modern computers store and process information as two-valued signals — binary digits, or bits.1 A single bit in isolation is nearly useless; only when we group bits and apply an interpretation to the possible bit patterns can they represent the elements of any finite set.1

Điểm tinh tế là cùng một mẫu bit có thể mang nhiều giá trị khác nhau tuỳ cách diễn giải. Các ông chỉ ra ba cách diễn giải số quan trọng nhất: không dấu (unsigned) dựa trên ký pháp nhị phân truyền thống, chỉ biểu diễn số không âm; bù hai (two's-complement) là cách phổ biến nhất để biểu diễn số nguyên có dấu; và dấu phẩy động (floating-point) là phiên bản cơ số 2 của ký pháp khoa học để xấp xỉ số thực.1 Cả chương là hành trình làm rõ ba cách diễn giải đó và hệ quả của việc máy chỉ có số bit hữu hạn.

Luận đề của chương: vì máy chỉ dùng một số bit hữu hạn để mã hoá một con số, mọi phép toán đều có thể tràn (overflow) khi kết quả quá lớn; hiểu rõ ba cách mã hoá — không dấu, bù hai, dấu phẩy động — cùng dải giá trị của chúng là điều kiện để viết chương trình đúng và an toàn.1

Ý chính: máy chỉ có chỗ cho một số bit nhất định, nên có lúc con số “tràn” ra ngoài và cho kết quả lạ. Biết số được cất giữ ra sao thì mới tránh được bất ngờ. Nhớ nhé: chỗ chứa có hạn, nên số có thể tràn.

The chapter's thesis: because a machine uses only a finite number of bits to encode a number, every operation can overflow when the result is too large; understanding the three encodings — unsigned, two's-complement, and floating-point — and the range of each is what lets you write correct and secure programs.1

Cụm khái niệm 01 Concept cluster 01

Lưu trữ thông tin: byte, địa chỉ, hệ thập lục phân và thứ tự byte Máy cất thông tin ở đâu và sắp xếp ra sao Information storage: bytes, addresses, hexadecimal, and byte order

Thay vì truy cập từng bit riêng lẻ, hầu hết máy tính dùng khối 8 bit — gọi là byte — làm đơn vị nhỏ nhất có thể định địa chỉ trong bộ nhớ. Một chương trình mức máy nhìn bộ nhớ như một mảng byte rất lớn gọi là bộ nhớ ảo, trong đó mỗi byte có một con số định danh duy nhất gọi là địa chỉ.1

Máy không cầm từng số 0 và 1 một; nó gom 8 bit thành một ô gọi là byte, giống như trứng xếp theo vỉ. Mỗi ô có một số thứ tự riêng gọi là địa chỉ, để máy biết tìm ở đâu. Nhớ nhé: 8 bit là một byte, mỗi byte có một số nhà riêng.

Rather than accessing individual bits, most computers use blocks of 8 bits — called a byte — as the smallest addressable unit of memory. A machine-level program views memory as a very large array of bytes called virtual memory, in which every byte has a unique identifying number called its address.1

Định nghĩa. Một byte gồm 8 bit. Ở dạng nhị phân, giá trị của nó chạy từ 00000000₂ đến 11111111₂; nhìn như số thập phân là từ 0 đến 255.1 Vì viết nhị phân thì dài dòng còn thập phân thì khó đổi qua lại, ta viết mẫu bit bằng cơ số 16 — hệ thập lục phân (hexadecimal).1

Nói đơn giản. Một byte chứa được một số từ 0 đến 255. Viết toàn 0 và 1 thì mỏi mắt, nên người ta viết gọn bằng hệ 16 chữ số, dùng thêm A đến F. Nhớ nhé: một byte = số từ 0 đến 255, viết gọn bằng hex.

Definition. A byte is 8 bits. In binary its value ranges from 00000000₂ to 11111111₂; viewed as decimal, from 0 to 255.1 Because binary is verbose and decimal is awkward to convert, we write bit patterns in base-16 — hexadecimal.1

1 byte = 8 bit
= 0x00 … 0xFF
= 0 … 255
= 2 chữ số hex

1 byte = 8 số 0/1
= 0 … 255
= 2 chữ hex

1 byte = 8 bits
= 0x00 … 0xFF
= 0 … 255
= 2 hex digits

  1. hexadecimal

    Hex — cách viết gọn mẫu bit theo cơ số 16 Hex — viết gọn bằng 16 chữ số Hexadecimal — a base-16 shorthand for bit patterns

    Hệ thập lục phân dùng các chữ số ‘0’–‘9’ cùng các ký tự ‘A’–‘F’ để biểu diễn 16 giá trị, mỗi chữ hex gói gọn đúng 4 bit.1 Trong C, hằng số bắt đầu bằng 0x hoặc 0X được hiểu là hex; ví dụ các ông viết số FA1D37B₁₆ thành 0xFA1D37B.1

    Hex đếm bằng 16 chữ số: 0–9 rồi A, B, C, D, E, F (tức 10 đến 15). Mỗi chữ hex thay cho đúng 4 bit, nên đổi qua lại rất nhanh. Nhớ nhé: một chữ hex = bốn bit.

    Hexadecimal uses digits ‘0’–‘9’ plus letters ‘A’–‘F’ to represent 16 values, with each hex digit packing exactly 4 bits.1 In C, a constant starting with 0x or 0X is read as hex; for example, the authors write the number FA1D37B₁₆ as 0xFA1D37B.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi lần bạn đọc địa chỉ bộ nhớ, mã màu web như #1d4ed8, hay giá trị trong trình gỡ lỗi, bạn đang đọc hex. Mã màu trên web như #1d4ed8 chính là hex đấy. Every memory address, web colour such as #1d4ed8, or debugger value you read is written in hex.
  2. word size

    Kích thước từ máy — vì sao 32-bit bị giới hạn 4 GB Máy 32-bit và máy 64-bit khác gì Word size — why 32-bit caps out at 4 GB

    Mỗi máy có một kích thước từ (word size) cho biết độ lớn danh nghĩa của dữ liệu con trỏ. Với máy có từ w-bit, không gian địa chỉ ảo tối đa là 2w byte. Một từ 32-bit giới hạn không gian địa chỉ ở 4 gigabyte (hơn 4×10⁹ byte một chút); lên 64-bit thì không gian đạt 16 exabyte, cỡ 1,84×10¹⁹ byte.1

    Máy tính có một “cỡ số” quen dùng: máy cũ là 32-bit, máy nay là 64-bit. Cỡ này quyết định máy “nhìn thấy” được bao nhiêu bộ nhớ. Máy 32-bit chỉ với tới 4 GB, còn 64-bit thì nhiều đến mức thực tế không chạm trần. Nhớ nhé: 32-bit trần 4 GB, 64-bit thì gần như vô hạn.

    Every machine has a word size giving the nominal size of pointer data. For a machine with a w-bit word, the virtual address space is at most 2^w bytes. A 32-bit word limits the address space to 4 gigabytes (just over 4×10⁹ bytes); a 64-bit word reaches 16 exabytes, around 1.84×10¹⁹ bytes.1

    Bạn gặp nó ở đâuWhere you meet it Giới hạn 4 GB RAM trên hệ điều hành 32-bit cũ chính là hệ quả trực tiếp của kích thước từ. Máy cũ chỉ nhận 4 GB RAM là vì lý do này. The old 4 GB RAM ceiling on 32-bit operating systems is a direct consequence of word size.

    Kích thước dữ liệu

    Theo Hình 2.3 của sách, kiểu char chiếm 1 byte, short 2 byte, int thường 4 byte, float 4 byte và double 8 byte; long và con trỏ là 4 byte ở chương trình 32-bit nhưng 8 byte ở 64-bit.1

    Kiểu cố định độ rộng

    Để tránh sự tuỳ tiện của kích thước “điển hình”, chuẩn ISO C99 đưa ra các kiểu cố định như int32_t và int64_t, bảo đảm đúng 4 và 8 byte trên mọi trình biên dịch.12

  3. byte ordering

    Thứ tự byte — little-endian và big-endian Xếp byte: đầu nhỏ trước hay đầu lớn trước Byte ordering — little-endian and big-endian

    Với đối tượng trải trên nhiều byte, ta phải quy ước thứ tự lưu chúng. Máy lưu byte ít quan trọng nhất trước gọi là little-endian; máy lưu byte quan trọng nhất trước gọi là big-endian. Với số int giá trị 0x01234567 đặt tại địa chỉ 0x100, máy big-endian xếp 01 23 45 67, còn little-endian xếp 67 45 23 01.1

    Một số lớn cần nhiều ô byte để chứa. Có máy cất mẩu nhỏ trước, có máy cất mẩu lớn trước — như hai người cùng viết ngày tháng theo thứ tự ngược nhau. Cả hai đều đúng, miễn là thống nhất. Nhớ nhé: cùng một số, hai máy có thể xếp byte ngược chiều nhau.

    For objects spanning multiple bytes we must agree on their order. A machine storing the least significant byte first is little-endian; one storing the most significant byte first is big-endian. For an int with value 0x01234567 at address 0x100, a big-endian machine stores 01 23 45 67, while a little-endian machine stores 67 45 23 01.1

    Bạn gặp nó ở đâuWhere you meet it Khi gửi dữ liệu nhị phân qua mạng hay đọc tệp tạo trên máy khác, trật tự byte sai sẽ biến con số thành vô nghĩa. Gửi file giữa hai máy khác loại mà thấy số lạ, thường là do chuyện này. Sending binary data over a network or reading a file made on another machine can turn numbers to nonsense if byte order is wrong.

    Nguồn gốc chữ “endian”

    Sách kể hai từ này mượn từ Gulliver's Travels của Jonathan Swift, nơi hai phe cãi nhau nên đập trứng từ đầu nhỏ hay đầu lớn.1 Danny Cohen là người đầu tiên dùng chúng cho thứ tự byte.15

    Không có bên nào “đúng”

    Các ông nhấn mạnh: không có lý do kỹ thuật nào khiến một trật tự tốt hơn trật tự kia — chọn bên nào cũng được, miễn nhất quán.1

Cụm khái niệm 02 Concept cluster 02

Số nguyên: mã hoá không dấu, bù hai và chuyện tràn số Số nguyên trong máy và vì sao đôi khi nó “sai” Integers: unsigned, two's-complement, and overflow

Có hai cách dùng bit để mã hoá số nguyên: một chỉ biểu diễn được số không âm, một biểu diễn được cả số âm, số 0 và số dương. Cả hai liên hệ chặt chẽ cả về tính chất toán học lẫn cài đặt mức máy.1

Máy có hai kiểu “đọc” một dãy bit thành số nguyên: kiểu thứ nhất chỉ đọc ra số dương và 0, kiểu thứ hai đọc được cả số âm. Cùng dãy bit, chọn kiểu khác là ra số khác. Nhớ nhé: cùng các bit, đọc “không dấu” hay “có dấu” sẽ ra hai số.

There are two ways to use bits to encode integers: one represents only nonnegative numbers, the other represents negative, zero, and positive numbers. The two are closely related in both their mathematical properties and their machine-level implementation.1

Định nghĩa. Với véc-tơ bit w chữ số, cách diễn giải không dấu cho giá trị bằng tổng các 2i tại những vị trí bit bằng 1; giá trị lớn nhất là UMax = 2w−1.1 Cách diễn giải bù hai giống hệt, chỉ khác bit cao nhất (bit dấu) mang trọng số âm −2w−1.1

Nói đơn giản. Đọc “không dấu” thì mọi bit đều cộng vào. Đọc “bù hai” thì bit ngoài cùng bên trái bị trừ đi thay vì cộng — nhờ vậy mới có số âm. Nhớ nhé: bù hai = bit đầu tiên mang dấu trừ.

Definition. For a w-bit vector, the unsigned interpretation is the sum of 2i over the bit positions equal to 1; the largest value is UMax = 2w−1.1 The two's-complement interpretation is identical except that the most significant bit (the sign bit) carries a negative weight of −2w−1.1

unsigned:
B2U = Σ xᵢ·2ⁱ
TMax = 2^(w−1) − 1
TMin = −2^(w−1)

không dấu: cộng hết
bù hai: bit đầu trừ
âm nhiều hơn dương 1

unsigned:
B2U = Σ xᵢ·2ⁱ
TMax = 2^(w−1) − 1
TMin = −2^(w−1)

  1. unsigned

    Không dấu — mọi bit đều cộng vào Không dấu — chỉ số dương và 0 Unsigned — every bit adds up

    Trong mã hoá không dấu, mỗi bit xᵢ bằng 1 đóng góp giá trị 2i vào con số. Các ông chứng minh đây là một song ánh: mỗi số từ 0 đến 2w−1 có đúng một mẫu bit w chữ số, và ngược lại.1

    Đọc không dấu thì cứ bit nào bằng 1 là cộng thêm phần của nó. Vì chỉ cộng, không bao giờ có số âm. Mỗi số có đúng một cách viết. Nhớ nhé: không dấu chỉ biết cộng, nên không có số âm.

    In the unsigned encoding, each bit xᵢ equal to 1 contributes 2i to the number. The authors prove this is a bijection: every number from 0 to 2w−1 has exactly one w-bit pattern, and vice versa.1

    Bạn gặp nó ở đâuWhere you meet it Kích thước tệp, chỉ số mảng, mặt nạ bit — tất cả đều là số không dấu. Cỡ file hay số thứ tự trong danh sách đều là số không dấu. File sizes, array indices, and bit masks are all unsigned numbers.
  2. two's-complement

    Bù hai — dải giá trị lệch một bậc Bù hai — có số âm, và âm nhiều hơn dương một Two's-complement — an asymmetric range

    Vì bit dấu mang trọng số −2w−1, giá trị nhỏ nhất là TMin = −2w−1 và lớn nhất là TMax = 2w−1−1. Dải này không đối xứng: phía âm luôn dài hơn phía dương đúng một đơn vị.13 Với int 32-bit, dải chạy từ −2.147.483.648 đến 2.147.483.647.1

    Vì bit đầu bị trừ đi, số âm đi xuống được xa hơn số dương đi lên một bước. Nên với 4 bit: thấp nhất là −8 nhưng cao nhất chỉ là 7. Nhớ nhé: bù hai luôn có một số âm không có số dương đối xứng.

    Because the sign bit carries weight −2w−1, the smallest value is TMin = −2w−1 and the largest is TMax = 2w−1−1. The range is asymmetric: the negative side always extends one step further than the positive side.13 For a 32-bit int, the range runs from −2,147,483,648 to 2,147,483,647.1

    Bạn gặp nó ở đâuWhere you meet it Lấy giá trị tuyệt đối của TMin lại cho ra chính TMin — một cái bẫy kinh điển vì không có số dương đối xứng. Đổi dấu số âm nhỏ nhất lại ra chính nó — một cái bẫy quen thuộc. Taking the absolute value of TMin yields TMin again — a classic trap, since there is no symmetric positive counterpart.

    Ví dụ với 4 bit

    Sách tính B2T₄([1011]) = −8 + 0 + 2 + 1 = −5 và TMin₄ = B2T₄([1000]) = −8, TMax₄ = B2T₄([0111]) = 7.1

    Vì sao bù hai thắng thế

    Cùng một mạch cộng dùng được cho cả số có dấu lẫn không dấu — đó là lý do phần cứng chọn bù hai thay vì “dấu–độ lớn”.13

  3. overflow

    Tràn số — khi phép nhân cho kết quả âm Tràn số — nhân ra số âm một cách vô lý Overflow — when a product turns negative

    Vì số bit hữu hạn, phép toán có thể tràn khi kết quả quá lớn. Các ông nêu ví dụ gây sốc: trên máy dùng int 32-bit, biểu thức 200 * 300 * 400 * 500 cho ra −884.901.888 — tích của các số dương lại thành số âm.1

    Chỗ chứa chỉ có bấy nhiêu bit, nên khi kết quả quá to nó “tràn” và quay vòng. Nhân bốn số dương với nhau mà máy trả về số âm — nghe vô lý nhưng thật. Nhớ nhé: số quá to thì tràn, và có thể đổi dấu.

    Because the number of bits is finite, an operation can overflow when the result is too large. The authors give a startling example: on a machine using 32-bit int, the expression 200 * 300 * 400 * 500 yields −884,901,888 — a product of positive numbers coming out negative.1

    Bạn gặp nó ở đâuWhere you meet it Nhiều lỗ hổng bảo mật sinh ra từ tràn số nguyên: một kích thước bộ đệm bị tính sai cho phép kẻ tấn công ghi đè bộ nhớ.1 Nhiều lỗi bảo mật nghiêm trọng bắt nguồn từ chuyện tràn số này. Many security vulnerabilities arise from integer overflow: a miscomputed buffer size lets an attacker overwrite memory.1

Cụm khái niệm 03 Concept cluster 03

Dấu phẩy động: ký pháp khoa học cơ số 2 và chuẩn IEEE 754 Số có phần lẻ, và vì sao máy chỉ giữ gần đúng Floating point: base-2 scientific notation and IEEE 754

Biểu diễn dấu phẩy động mã hoá số hữu tỉ dạng V = x × 2y, hữu ích khi tính với số rất lớn, số rất gần 0, và nói chung để xấp xỉ số thực.1 Nhưng giống như số thập phân không viết được 1/3 một cách hữu hạn, nhị phân phân số cũng không viết được mọi số một cách chính xác.1

Số có phần thập phân (như 3,14) được máy ghi theo kiểu “ký pháp khoa học” bằng cơ số 2. Nhờ vậy ghi được số cực lớn và cực nhỏ. Cái giá là đa phần chỉ gần đúng, không khít. Nhớ nhé: số lẻ trong máy thường chỉ gần đúng.

A floating-point representation encodes rational numbers of the form V = x × 2y, useful for very large numbers, numbers very close to 0, and more generally for approximating reals.1 But just as decimal cannot write 1/3 in finitely many digits, fractional binary cannot write every number exactly.1

Định nghĩa. Chuẩn IEEE 754 biểu diễn một số dưới dạng V = (−1)s × M × 2E: bit dấu s, phần định trị M (significand) và số mũ E.1 Số mũ được lưu ở dạng lệch (biased): E = e − Bias, với Bias = 2k−1−1 (bằng 127 cho đơn chính xác, 1023 cho kép).14

Nói đơn giản. Mỗi số thực được tách làm ba mẩu: dấu (âm hay dương), phần số chính, và phần mũ (dời dấu phẩy đi bao xa). Ghép ba mẩu lại là ra số. Nhớ nhé: một số thực = dấu + phần chính + số mũ.

Definition. IEEE 754 represents a number as V = (−1)s × M × 2E: a sign bit s, a significand M, and an exponent E.1 The exponent is stored in biased form: E = e − Bias, with Bias = 2k−1−1 (127 for single precision, 1023 for double).14

V = (−1)ˢ · M · 2ᴱ
single: 1 + 8 + 23 bit
double: 1 + 11 + 52 bit
Bias = 2^(k−1) − 1

số = dấu · phần chính · 2^mũ
float: 32 bit
double: 64 bit

V = (−1)ˢ · M · 2ᴱ
single: 1 + 8 + 23 bits
double: 1 + 11 + 52 bits
Bias = 2^(k−1) − 1

  1. fractional binary

    Nhị phân phân số — vì sao 0,1 không bao giờ khít Vì sao 0,1 trong máy không tròn Fractional binary — why 0.1 is never exact

    Với nhị phân phân số, chỉ những số viết được dạng x × 2y mới biểu diễn chính xác; các số khác chỉ xấp xỉ được. Ví dụ 1/5 (tức 0,20 trong thập phân) không có biểu diễn nhị phân hữu hạn.1

    Trong hệ 10, số 1/3 = 0,333… kéo dài mãi. Trong hệ 2 của máy, chính số 0,1 lại kéo dài mãi như thế, nên máy phải cắt bớt và giữ gần đúng. Nhớ nhé: 0,1 trong máy chỉ là số gần bằng 0,1.

    In fractional binary, only numbers expressible as x × 2y are exact; others can only be approximated. For instance, 1/5 (that is, decimal 0.20) has no finite binary representation.1

    Bạn gặp nó ở đâuWhere you meet it Khi 0.1 + 0.2 không bằng đúng 0.3 trong gần như mọi ngôn ngữ, bạn đang chạm vào giới hạn này. Lúc máy tính 0,1 + 0,2 ra 0,30000…04 là vì chuyện này. When 0.1 + 0.2 is not exactly 0.3 in almost every language, you are hitting this limit.
  2. IEEE 754

    IEEE 754 — chuẩn chung do William Kahan dẫn dắt IEEE 754 — luật chung cho số lẻ IEEE 754 — the shared standard led by William Kahan

    Trước thập niên 1980, mỗi hãng tự đặt quy ước riêng cho số thực. Khoảng năm 1985, chuẩn IEEE 754 ra đời và thống nhất tất cả; nỗ lực bắt đầu từ 1976 khi Intel thuê William Kahan — giáo sư Đại học California, Berkeley — thiết kế chuẩn cho chip 8087.14 Nay gần như mọi máy đều hỗ trợ IEEE 754, giúp chương trình khoa học chạy giống nhau trên các máy khác nhau.1

    Ngày xưa mỗi hãng máy tính tính số lẻ theo kiểu riêng, nên cùng phép tính mà ra kết quả khác nhau. Từ khoảng 1985 mọi người theo chung một luật tên IEEE 754, nhờ đó máy nào cũng tính giống nhau. Nhớ nhé: nhờ luật chung, số lẻ tính giống nhau trên mọi máy.

    Before the 1980s, each manufacturer devised its own conventions for real numbers. Around 1985 the IEEE 754 standard unified them; the effort began in 1976 when Intel hired William Kahan — a professor at the University of California, Berkeley — to design a standard for the 8087 chip.14 Today virtually all machines support IEEE 754, letting scientific programs run alike across machines.1

    Bạn gặp nó ở đâuWhere you meet it Kiểu float (32 bit) và double (64 bit) trong hầu hết ngôn ngữ chính là hai định dạng của IEEE 754. Kiểu float và double bạn vẫn dùng chính là IEEE 754. The float (32-bit) and double (64-bit) types in most languages are exactly the two IEEE 754 formats.

    Ba trường bit

    Đơn chính xác gói 1 bit dấu, 8 bit mũ và 23 bit phần lẻ vào 32 bit; kép dùng 1 + 11 + 52 bit thành 64 bit.1

    23 hay 24 bit định trị?

    Sách lưu rằng với giá trị chuẩn hoá, trường lẻ 23 bit được hiểu kèm một bit “1” ẩn phía trước, nên độ chính xác thực tế là 24 bit dù chỉ 23 bit được lưu — nguồn khác nhau đôi khi đếm theo một trong hai con số này.14

  3. rounding

    Làm tròn — vì sao phép cộng không còn kết hợp Làm tròn — cộng theo thứ tự khác ra kết quả khác Rounding — why addition stops being associative

    Vì mỗi kết quả phải làm tròn về số biểu diễn được gần nhất, phép cộng dấu phẩy động không có tính kết hợp. Các ông chỉ ra: (3.14+1e20)-1e20 cho 0.0 trên hầu hết máy, trong khi 3.14+(1e20-1e20) cho 3.14.1

    Vì mỗi bước đều làm tròn, đổi thứ tự cộng là có thể ra kết quả khác. Cộng số nhỏ vào số khổng lồ, số nhỏ có thể “biến mất”. Nhớ nhé: với số lẻ, thứ tự cộng cũng ảnh hưởng kết quả.

    Because each result must round to the nearest representable number, floating-point addition is not associative. The authors show: (3.14+1e20)-1e20 gives 0.0 on most machines, while 3.14+(1e20-1e20) gives 3.14.1

    Bạn gặp nó ở đâuWhere you meet it Ngày 25/2/1991, một khẩu đội Patriot ở Dhahran trượt tên lửa Scud vì sai số tích luỹ khi xấp xỉ 0,1; vụ tấn công làm 28 binh sĩ thiệt mạng.16 Một hệ phòng thủ tên lửa từng bắn trượt vì cộng dồn sai số 0,1 suốt nhiều giờ. On 25 February 1991, a Patriot battery at Dhahran missed a Scud missile due to accumulated error in approximating 0.1; the attack killed 28 soldiers.16

Ba ngộ nhận thường gặp

Three common misconceptions

“Số nguyên trong máy hành xử như số nguyên trong toán” "Machine integers behave like math integers"

Ngộ nhận: nhân mãi thì số chỉ càng lớn; tích các số dương phải dương.

Thực tế: vì dải hữu hạn, phép toán có thể tràn — 200 * 300 * 400 * 500 ra −884.901.888 trên int 32-bit.1

Myth: keep multiplying and the number just grows; a product of positives must be positive.

Reality: with a finite range, operations overflow — 200 * 300 * 400 * 500 gives −884,901,888 on a 32-bit int.1

“Trộn số có dấu với không dấu thì vô hại” "Mixing signed and unsigned is harmless"

Ngộ nhận: so sánh một int với một giá trị không dấu cho kết quả “tự nhiên”.

Thực tế: các ông cảnh báo kiểu unsigned, tuy đơn giản về khái niệm, lại sinh ra hành vi mà cả lập trình viên dày dạn cũng không ngờ — nhất là khi số âm bị ngầm đổi thành số không dấu rất lớn.1

Myth: comparing an int with an unsigned value gives the "natural" answer.

Reality: the authors warn that the unsigned type, though conceptually simple, leads to behaviour even experienced programmers do not expect — especially when a negative is implicitly converted to a huge unsigned value.1

“So sánh bằng với số dấu phẩy động là an toàn” "Testing floats for equality is safe"

Ngộ nhận: nếu phép toán “đúng” thì a == b với số thực sẽ cho kết quả mong đợi.

Thực tế: vì làm tròn, phép cộng không kết hợp — (3.14+1e20)-1e20 ra 0.0 còn 3.14+(1e20-1e20) ra 3.14; so sánh bằng trực tiếp là mong manh.1

Myth: if the math is "right", a == b on floats gives the expected answer.

Reality: rounding makes addition non-associative — (3.14+1e20)-1e20 is 0.0 while 3.14+(1e20-1e20) is 3.14; direct equality is fragile.1

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm chương này chưa Năm câu hỏi kiểm tra nhanh Five questions to test whether the chapter landed

Trả lời được năm câu dưới đây — không cần nhìn lại — nghĩa là bạn đã nắm trục chính của chương: bit cần diễn giải, số nguyên có dải hữu hạn, và số thực chỉ là xấp xỉ.

Thử trả lời năm câu này mà không xem lại nhé.

Answering the five questions below — without looking back — means you have the chapter's spine: bits need interpretation, integers have a finite range, and reals are only approximate.

  1. Vì sao một mẫu bit đơn lẻ không mang ý nghĩa cho đến khi ta chọn cách diễn giải?

    Hãy nêu ít nhất hai cách diễn giải khác nhau cho cùng 32 bit.

  2. Mã hoá không dấu và bù hai khác nhau ở đúng điểm nào về trọng số bit?

    Suy ra TMin và TMax theo w, và giải thích vì sao dải không đối xứng.

  3. Vì sao 200 * 300 * 400 * 500 lại cho kết quả âm trên int 32-bit?

    Hiện tượng này liên quan thế nào tới các lỗ hổng bảo mật do tràn số?

  4. Vì sao số 0,1 không được dấu phẩy động biểu diễn chính xác?

    Liên hệ với vụ tên lửa Patriot ở Dhahran năm 1991.

  5. Trong IEEE 754, ba trường dấu – mũ – định trị ghép lại thành giá trị bằng công thức nào?

    Bias bằng bao nhiêu cho đơn chính xác và cho kép, và vì sao dùng dạng lệch?

  1. Vì sao số 0 và 1 chỉ có nghĩa khi ta nói chúng nghĩa là gì?

  2. Đọc “không dấu” và “có dấu” khác nhau ở chỗ nào?

  3. “Tràn số” là gì, và vì sao nhân bốn số dương lại ra số âm?

  4. Vì sao máy tính 0,1 + 0,2 không ra đúng 0,3?

  5. Máy 32-bit và 64-bit khác nhau ở điều gì quan trọng nhất?

  1. Why does a single bit pattern carry no meaning until you choose an interpretation?

  2. At exactly which bit's weight do unsigned and two's-complement encodings differ?

  3. Why does 200 * 300 * 400 * 500 come out negative on a 32-bit int?

  4. Why can't floating point represent 0.1 exactly?

  5. In IEEE 754, what formula combines the sign, exponent, and significand fields into a value?

Khép lại chương Closing the chapter

Máy tính mã hoá mọi thứ bằng bit, nhưng bit chỉ có nghĩa khi ta chọn cách diễn giải; và vì số bit luôn hữu hạn, mỗi con số đều mang theo một đường ranh giới — nơi phép toán tràn, nơi số thực chỉ còn gần đúng. Hiểu ranh giới ấy là điều phân biệt một chương trình chạy được với một chương trình chạy đúng.1

Máy chỉ biết 0 và 1, nhưng 0 và 1 cần ta quy ước nghĩa; và vì chỗ chứa có hạn, con số nào cũng có mép giới hạn — quá mép là sai. Biết mép ở đâu thì viết chương trình mới yên tâm. Nhớ nhé: biết giới hạn của con số thì mới viết đúng.

Computers encode everything in bits, but bits mean nothing until you choose an interpretation; and because the bits are always finite, every number carries an edge — where operations overflow, where reals become approximate. Knowing that edge is what separates a program that runs from one that runs correctly.1