Chuyển đến nội dung
MINH VO Ghi chép từ công việc
của một kỹ sư tại Việt Nam
Cơ bản12 phút đọc

Phân biệt bit nhớ và tràn có dấu trong bộ cộng tám bit

Theo dõi phép cộng và trừ tám bit, chứng minh quy tắc tràn có dấu và kiểm tra trước khi thu hẹp kết quả trong C.

Minh họa bảng mạch đặt trên giấy vẽ với các nét phác kỹ thuật mờ

Bit nhớ và tràn số có dấu trả lời hai câu hỏi khác nhau về cùng một phép cộng. Bit nhớ cho biết tổng không dấu cần thêm một bit. Tràn số có dấu cho biết kết quả toán học nằm ngoài miền có dấu đã chọn. Một bộ cộng tám bit có thể tạo ra hiện tượng này mà không có hiện tượng kia, vì vậy lập trình viên không thể dùng chúng thay thế nhau khi kiểm tra số học.

Giữ độ rộng cố định trong toàn bộ ví dụ. Tám bit không dấu biểu diễn các số từ không đến 255. Cùng những mẫu bit đó, khi được hiểu là số nguyên có dấu dạng bù hai, biểu diễn các số từ âm 128 đến dương 127. Tám bit thấp mà phần cứng lưu lại giống nhau trong cả hai cách hiểu; ý nghĩa của chúng thay đổi.

Cộng 127 với một

Biểu diễn tám bit của 127 là 01111111. Cộng thêm 00000001 cho kết quả 10000000. Không cần bit thứ chín, nên không có bit nhớ ra đối với phép cộng không dấu. Kết quả không dấu là 128 và vẫn biểu diễn được.

Cách hiểu có dấu dẫn đến kết luận khác. Cả hai đầu vào đều không âm, nhưng mẫu bit kết quả lại biểu diễn âm 128. Tổng toán học dương 128 nằm ngoài miền số có dấu tám bit. Đây là tràn số có dấu dù bit nhớ ra bằng không.

Bây giờ cộng 255 với một. Tổng nhị phân đầy đủ là 1 00000000: tám bit thấp bằng không và bit thứ chín bằng một. Số học không dấu vượt miền biểu diễn. Theo cách hiểu có dấu, hai đầu vào là âm một và dương một, có tổng bằng không. Không có tràn số có dấu.

Mẫu bit đầu vàoTám bit thấp của kết quảBit nhớ raTràn có dấu
0x7F + 0x010x8001
0xFF + 0x010x0010
0x80 + 0xFF0x7F11
0x20 + 0x100x3000

Dòng thứ ba biểu diễn âm 128 cộng âm một nếu đọc các toán hạng là số có dấu. Kết quả toán học âm 129 không biểu diễn được. Trong trường hợp này, việc hai toán hạng âm tạo ra kết quả dương là dấu hiệu có thể quan sát của tràn số.

Các phép cộng tám bit cho thấy 127 cộng một bị tràn có dấu nhưng không có nhớ ra, còn 255 cộng một có nhớ ra nhưng không tràn có dấuMở ảnh kích thước đầy đủ ↗

Suy ra phép kiểm tra từ các bit dấu

Với phép cộng, tràn có dấu xảy ra khi hai toán hạng cùng dấu nhưng kết quả sau khi bỏ các bit cao lại mang dấu ngược lại. Nếu hai toán hạng khác dấu, tổng nằm giữa chúng và không thể vượt qua hai đầu mút của miền có dấu. Quy tắc này dành cho phép cộng; phép trừ cần phân tích dấu tương ứng.

Gọi mẫu bit của hai toán hạng là A và B, kết quả đã giới hạn độ rộng là R, và mặt nạ bit dấu là 0x80. Biểu thức ~(A ^ B) có bit một tại vị trí dấu khi hai dấu đầu vào giống nhau. Biểu thức (A ^ R) có bit một tại đó khi dấu kết quả khác dấu A. Thực hiện AND hai giá trị này với mặt nạ bit dấu sẽ phát hiện tràn.

def signed8(bits):
    return bits if bits < 128 else bits - 256

for a in range(256):
    for b in range(256):
        wide = a + b
        result = wide & 0xff
        carry = wide > 0xff
        overflow = bool((~(a ^ b) & (a ^ result)) & 0x80)
        exact_signed = signed8(a) + signed8(b)
        assert overflow == (not -128 <= exact_signed <= 127)
        assert carry == (a + b >= 256)
print("65536 additions passed")

Phép cộng số nguyên độ chính xác tùy ý của Python cung cấp giá trị toán học độc lập để đối chiếu. Phép lấy mặt nạ tạo ra kết quả phần cứng có độ rộng hẹp; cách diễn giải các mẫu bit ban đầu tạo ra hai toán hạng có dấu. Tách riêng các bước này giúp tránh nhầm rằng số nguyên không giới hạn của Python tự hành xử như thanh ghi tám bit.

Ngôn ngữ lập trình có thể quy định khác

Lệnh của bộ xử lý và biểu thức trong ngôn ngữ lập trình có các quy tắc riêng. Đặc tả lệnh số nguyên RV32I của RISC-V quy định lệnh số học nguyên ghi các bit thấp trong phạm vi XLEN và bỏ qua tràn số học. Tập lệnh số nguyên cơ sở của RISC-V không cung cấp thanh ghi cờ điều kiện giống một số kiến trúc khác.

Quy tắc đó không khiến một biểu thức C có dấu bị tràn tự động trở nên hợp lệ. Số học không dấu trong C tuân theo quy tắc modulo, còn biểu thức có dấu cho kết quả không biểu diễn được có thể dẫn đến hành vi không xác định. Bản dự thảo ủy ban C11 N1570, mục 6.2.5 và đoạn 5 của mục 6.5, nêu hai quy tắc này. Trình biên dịch có thể suy luận dựa trên ngữ nghĩa ngôn ngữ trước khi chọn lệnh máy. Nếu ứng dụng cần phép tính có kiểm tra, bão hòa hoặc quay vòng theo độ rộng có dấu, hãy thể hiện chính sách đó bằng các thao tác được ngôn ngữ hỗ trợ hoặc kiểu rộng hơn có giới hạn đã được chứng minh.

Ngay cả kiểu rộng hơn cũng cần một giới hạn. Tổng hai số tám bit có thể nằm an toàn trong một kiểu nguyên đủ rộng, nhưng nhân hai giá trị lớn rồi cộng dồn hàng nghìn tích có thể vượt cả một bộ tích lũy tưởng như dư dả. Hãy xác định số lượng số hạng và miền giá trị của từng số hạng trước khi chọn cách biểu diễn.

Suy ra tràn từ tầng nhớ cuối cùng

Quy tắc bit dấu có một dạng tương đương ở mức cổng: tràn có dấu bằng XOR giữa bit nhớ đi vào bit có trọng số lớn nhất và bit nhớ đi ra khỏi bit đó. Với bộ cộng tám bit, gọi hai bit nhớ này là C7 và C8. Khi đó tín hiệu tràn là C7 XOR C8. Bit nhớ không dấu chỉ là C8.

Xét lại 127 cộng một. Bảy bit thấp cộng lại thành 128, tạo một bit nhớ vào vị trí dấu. Cả hai bit dấu đầu vào đều bằng không, nên cộng thêm bit nhớ tạo ra bit dấu một mà không có nhớ ra. C7 bằng một, C8 bằng không, và XOR của chúng bằng một. Với 255 cộng một, cũng bit nhớ vào đó gặp một bit dấu đầu vào bằng một; bit dấu kết quả bằng không và nhớ ra bằng một. Cả hai bit nhớ đều bằng một, nên tràn có dấu bằng không.

Tầng cộng ở bit cao nhất đưa bit nhớ vào và bit nhớ ra đến cổng XOR để phát hiện tràn có dấu; riêng nhớ ra cho biết vượt miền không dấuMở ảnh kích thước đầy đủ ↗

Một cách chứng minh đẳng thức này là liệt kê đầu vào của tầng bit dấu: hai bit dấu toán hạng và bit nhớ từ các bit thấp hơn. Có tám trường hợp. Với mỗi trường hợp, tính bit dấu kết quả và bit nhớ ra, rồi so sánh quy tắc hai đầu vào cùng dấu nhưng kết quả khác dấu với phép XOR hai bit nhớ. Chứng minh này chỉ xét tầng cộng đầy đủ cuối cùng; nó không cần giả định cách bảy bit thấp hơn tạo ra nhớ vào.

from itertools import product

for sign_a, sign_b, carry_in in product((0, 1), repeat=3):
    total = sign_a + sign_b + carry_in
    sign_result = total & 1
    carry_out = total >> 1
    sign_rule = (sign_a == sign_b) and (sign_result != sign_a)
    assert sign_rule == bool(carry_in ^ carry_out)
print("8 sign-stage cases passed")

Lập luận tương tự áp dụng cho độ rộng khác khi chuyển vị trí bit dấu. Nó không có nghĩa mọi tập lệnh đều cho phần mềm truy cập hai tín hiệu nhớ này. Một số kiến trúc có cờ điều kiện; mã dùng tập lệnh số nguyên cơ sở RISC-V thực hiện kiểm tra bằng các thao tác khác.

Phép trừ thay đổi điều kiện về dấu

Bộ trừ có độ rộng cố định có thể tính A trừ B bằng A cộng phần đảo bit của B cộng một. Phép đảo phải nằm trong độ rộng đã chọn. Bit nhớ ra của phép cộng này thường cho biết phép trừ không dấu không cần mượn, nhưng cờ mang tên carry hoặc borrow của từng kiến trúc phải được hiểu theo tài liệu riêng của kiến trúc đó.

Với đầu vào tám bit, 0x00 trừ 0x01 tạo ra các bit thấp 0xFF và không có nhớ ra từ phép cộng với phần đảo. Phép tính 0 - 1 theo cách hiểu không dấu cần mượn. Theo số học có dấu, kết quả chính xác là âm một và biểu diễn được, nên không có tràn có dấu.

Bây giờ trừ một khỏi 0x80. Kết quả thấp là 0x7F, và phép trừ không dấu 128 trừ một không cần mượn. Cách hiểu có dấu yêu cầu tính âm 128 trừ một, tức âm 129, nằm ngoài miền biểu diễn. Với phép trừ, tràn có dấu xảy ra khi hai toán hạng khác dấu và dấu kết quả khác dấu A. Biểu thức bit tương ứng là ((A ^ B) & (A ^ R) & 0x80) != 0.

def signed_byte(bits):
    return bits if bits < 128 else bits - 256

for a in range(256):
    for b in range(256):
        wide = a + (b ^ 0xff) + 1
        result = wide & 0xff
        borrow = not bool(wide & 0x100)
        overflow = bool((a ^ b) & (a ^ result) & 0x80)
        exact = signed_byte(a) - signed_byte(b)
        assert borrow == (a < b)
        assert overflow == (not -128 <= exact <= 127)
print("65536 subtractions passed")

Nếu dùng nguyên biểu thức phát hiện tràn của phép cộng cho phép trừ, phép kiểm tra này sẽ thất bại. Tên hoặc tài liệu của hàm kiểm tra nên ghi rõ phép toán, độ rộng lưu trữ và cách diễn giải, để người gọi sau này không nhầm các quy tắc với nhau.

Kiểm tra trước khi thu hẹp trong mã ứng dụng

Giá trị trung gian rộng hơn giúp biểu đạt chính sách mong muốn rõ hơn khi đã biết giới hạn của chính nó. Tổng hai số có dấu tám bit nằm từ âm 256 đến dương 254. Kiểu int thông thường của một triển khai C có thể biểu diễn miền đó, nên chuyển cả hai toán hạng sang int trước khi cộng sẽ tránh tràn có dấu ở bước trung gian.

#include <stdbool.h>
#include <stdint.h>
#include <limits.h>

bool add_checked_i8(int8_t a, int8_t b, int8_t *out) {
    int sum = (int)a + (int)b;
    if (sum < INT8_MIN || sum > INT8_MAX) {
        return false;
    }
    *out = (int8_t)sum;
    return true;
}

Các mục 5.2.4.2.1 và 7.20.1.1 của bản dự thảo C11 quy định miền tối thiểu của int và yêu cầu đối với kiểu có độ rộng chính xác. Hàm này giả định triển khai có cung cấp int8_t và out trỏ tới vùng nhớ có thể ghi. Khi thất bại, hàm giữ nguyên vùng đích. Hành vi tường minh đó hữu ích cho bên gọi: kiểm tra thất bại không âm thầm công bố một kết quả đã quay vòng. Phép ép kiểu chỉ xảy ra sau khi đã chứng minh giá trị biểu diễn được bằng kiểu đích.

Biểu thức số học lớn hơn cần giới hạn mới. Tổng của một nghìn tích có thể vượt một kiểu vốn đủ an toàn để chứa từng tích riêng lẻ. Với bộ tích lũy phục vụ suy luận mô hình hoặc phép tính số byte, hãy chặn miền cho toàn bộ biểu thức, kể cả số hạng độ lệch và các giá trị cộng thêm, trước khi chọn kiểu trung gian.

Mở rộng bài học thành một ALU nhỏ

Một bài tập tiếp theo có thể tự kiểm tra là thêm đầu ra trạng thái bằng không và âm cho kết quả đã giới hạn độ rộng. Trạng thái bằng không đúng khi cả tám bit kết quả đều bằng không; trạng thái âm chính là bit dấu được lưu. Hãy xét lại bốn phép cộng trong bảng và ghi thêm hai trạng thái này bên cạnh nhớ ra và tràn. Với 127 cộng một, trạng thái âm là đúng dù tổng toán học dương: nó mô tả kết quả được lưu, còn tràn cảnh báo rằng cách hiểu có dấu của mẫu bit đó không thể đại diện cho đáp án chính xác.

Dự án 2 của Nand2Tetris là bài tập tiếp nối phù hợp vì dự án ALU tách kết quả chính khỏi hai đầu ra trạng thái bằng không và âm, đồng thời cung cấp tệp kết quả đối chiếu cho cả hai giai đoạn. Hai trạng thái này tự chúng không tạo thành cờ tràn có dấu. Trang dự án ALU của Ben Eater trình bày một bộ cộng/trừ cụ thể và liên kết đến tài liệu linh kiện. Bạn có thể dùng trang dự án và sơ đồ để liên hệ phép tính với một mạch có thể lắp ráp, rồi tra đặc tả linh kiện để biết giới hạn điện. Các phép kiểm tra hữu hạn bằng Python trong bài không phải phép đo trên bo mạch đó.

Chọn cách xử lý sau khi phát hiện tràn

Phép tính checksum thường chủ động dùng số học modulo. Đại lượng vật lý như nhiệt độ thường cần chính sách khác. Để một giá trị cảm biến dương lớn quay vòng thành số âm có thể che giấu đầu vào không hợp lệ. Số học bão hòa sẽ chặn kết quả ở đầu mút gần nhất; số học có kiểm tra sẽ báo thất bại; cách biểu diễn rộng hơn sẽ giữ được kết quả nếu miền của nó đủ lớn.

Bão hòa cũng làm mất thông tin. Sau khi nhiều giá trị cùng bị chặn ở 127, không thể khôi phục độ lớn ban đầu từ các byte đã lưu. Đánh đổi này hữu ích trong một số nhân tính toán suy luận lượng tử hóa nhưng có thể gây hại trong phép tính kế toán. Phát hiện tràn cung cấp thông tin để áp dụng chính sách; nó không tự chọn chính sách thay bạn.

Tài liệu logic tổ hợp của Computation Structures liên hệ phép cộng nhị phân với các cổng và sự lan truyền bit nhớ. Ở mức đó, phép cộng bù hai dùng lại cùng bộ cộng của số không dấu. Phần việc thực tế nằm ở ranh giới giữa các cách hiểu: giữ đúng độ rộng, diễn giải kết quả nhất quán và xác định rõ cách phản ứng khi đáp án toán học không biểu diễn được.

Nguồn tham khảo & đọc thêm

  1. Computation Structures: Combinational logic
  2. RISC-V unprivileged ISA: RV32I base integer instruction set
  3. ISO C11 committee draft N1570: integer ranges, expressions and fixed-width types
  4. Nand2Tetris Project 2: Boolean Arithmetic
  5. Ben Eater: 8-bit computer arithmetic logic unit
← Về trang bài viết

Hình minh họa

100%