Bài 31.226 phút đọc

Sáu toán tử bit và ba cạm bẫy

Sau bài này bạn sẽ làm được

Dùng sáu toán tử bit và biết bảng chân trị của từng cái
Nêu ba trường hợp dịch bit gây hành vi không xác định
Giải thích vì sao thao tác bit phải dùng kiểu không dấu
Nhớ rằng toán tử bit có độ ưu tiên thấp hơn phép so sánh

Sáu toán tử, mỗi cái một dòng để học. Rồi ba trường hợp hành vi không xác định và một cái bẫy độ ưu tiên, và ba thứ đó chiếm phần lớn thời gian gỡ lỗi của người mới làm việc với bit.

#Sáu toán tử

Bốn phép toán trên cùng một cặp giá trị. AND giữ bit chung, OR gộp, XOR giữ bit khác nhau.

Toán tử	Tên	Ví dụ với a=12, b=10	Kết quả	Bit ra bằng 1 khi
&	AND	1100 & 1010 = 1000	8	Cả hai bit vào bằng 1
\|	OR	1100 \| 1010 = 1110	14	Ít nhất một bit bằng 1
^	XOR	1100 ^ 1010 = 0110	6	Đúng một bit bằng 1
~	NOT	~1100 = ...0011	-13	Bit vào bằng 0
<<	Dịch trái	1100 << 1 = 11000	24	Đẩy sang trái, chèn 0 vào phải
>>	Dịch phải	1100 >> 1 = 110	6	Đẩy sang phải

Bốn tính chất đáng nhớ

x & 0     == 0            /* AND voi 0 xoa het   */
x & ~0    == x            /* AND voi toan 1 giu nguyen */
x | 0     == x            /* OR voi 0 giu nguyen */
x | ~0    == ~0           /* OR voi toan 1 bat het */

x ^ 0     == x            /* XOR voi 0 giu nguyen */
x ^ ~0    == ~x           /* XOR voi toan 1 dao het */
x ^ x     == 0            /* XOR voi chinh no cho 0 */

/* Tinh chat cuoi la nen cua nhieu thu thuat:
     - tim so xuat hien le lan trong mang: XOR tat ca
     - hoan doi khong dung bien tam (nhung dung lam, xem Bai 31.5)
     - ma hoa XOR don gian */

Đừng nhầm & với && và | với ||

int a = 2, b = 4;

a & b        /* 0010 & 0100 = 0000 = 0  -> "sai" */
a && b       /* ca hai khac 0           -> 1, "dung" */

a | b        /* 0110 = 6 */
a || b       /* 1 */

/* Bon khac biet:
     1. & lam viec tren TUNG BIT, && tren gia tri dung sai
     2. && danh gia ngan mach, & luon tinh ca hai ve
     3. && luon tra ve 0 hoac 1, & tra ve mot mau bit
     4. && la diem tuan tu, & thi khong

   Loi hay gap: */

if (co & CO_GHI && co & CO_DOC)      /* chay dung nho do uu tien,
                                        nhung rat kho doc */

if ((co & CO_GHI) && (co & CO_DOC))  /* viet the nay */

#Dịch trái và dịch phải

x << n      /* dich trai n bit, chen 0 vao ben phai */
x >> n      /* dich phai n bit */

/* Voi so KHONG AM va khong tran: */
x << n   ==  x * 2^n
x >> n   ==  x / 2^n

Biểu thức	Giá trị	Tương đương	Ghi chú
12 << 1	24	12 * 2	Nhân đôi
12 << 3	96	12 * 8	Nhân 8
12 >> 1	6	12 / 2	Chia đôi
13 >> 1	6	13 / 2	Cắt bỏ phần lẻ
1u << 31	2147483648	2^31	Bit cao nhất của uint32
1 << 31	hành vi không xác định		int không chứa được 2^31

Dịch phải số âm do cài đặt quy định

terminal

./dich

(-8) >> 1               : -4   (do cai dat quy dinh)
0x80000000u >> 1        : 0x40000000   (luon dinh nghia ro)

int x = -8;
x >> 1;

/* Hai cach cai dat kha di:

   1. DICH SO HOC: chen ban sao cua bit dau vao ben trai
      11111000 >> 1 = 11111100 = -4
      Ket qua bang -8 / 2 = -4. Moi trinh bien dich hien dai
      deu lam the nay.

   2. DICH LOGIC: chen 0 vao ben trai
      11111000 >> 1 = 01111100 = 124
      Ket qua vo nghia voi so am.

   Chuan noi ket qua DO CAI DAT QUY DINH, tuc la trinh bien dich
   phai chon mot cach va ghi vao tai lieu. No KHONG phai hanh vi
   khong xac dinh: chuong trinh khong duoc phep lam bat ky dieu gi.

   Tu C23, dich phai so am duoc chuan hoa thanh dich so hoc. */

Trình biên dịch tự đổi phép chia thành dịch khi được

unsigned f(unsigned x) { return x / 8; }

/* gcc -O2 sinh ra: shr eax, 3     <- mot lenh dich */

int g(int x) { return x / 8; }

/* gcc -O2 sinh ra BON lenh, vi voi so AM thi phep chia trong C
   lam tron VE PHIA 0, con dich phai lam tron XUONG.

     -9 / 8   = -1   (lam tron ve 0)
     -9 >> 3  = -2   (lam tron xuong)

   Nen trinh bien dich phai them lenh dieu chinh. Ket luan:
   viet x / 8 cho ro nghia, va de trinh bien dich toi uu.
   Chi viet x >> 3 khi ban that su muon THAO TAC BIT. */

#Ba cạm bẫy dịch bit

Một: dịch bằng hoặc quá độ rộng kiểu

int y = 1;
y << 32;         /* HANH VI KHONG XAC DINH voi int 32 bit */

/* Chuan: neu so lan dich am, hoac lon hon hoac BANG so bit
   cua kieu sau khi thang hang, thi hanh vi khong xac dinh. */

terminal

./dich-ub

y << 32 voi int 32 bit : 1   (UB, ket qua tuy CPU)

Kết quả là 1, không phải 0, và đó là điều đáng sợ

/* Nhieu nguoi doan rang 1 << 32 cho 0, vi bit da bi day het ra.
   Thuc te tren x86:

   Lenh SHL cua x86 CHE so lan dich xuong 5 bit (voi toan hang 32 bit):
     32 & 31 = 0
   nen "dich 32 lan" thanh "dich 0 lan", va ket qua la 1.

   Tren ARM thi ket qua la 0.
   Tren mot so kien truc khac lai khac nua.
   Va neu trinh bien dich tinh duoc luc BIEN DICH, no co the
   cho ra so thu ba, hoac xoa han doan ma do.

   Do la ban chat cua hanh vi khong xac dinh: khong phai
   "gia tri nao do", ma la "khong co gi bao dam ca". */

/* Cach viet dung khi so lan dich la bien: */
uint32_t dich_an_toan(uint32_t x, unsigned n) {
    return n >= 32 ? 0 : x << n;
}

Hai: dịch trái số âm

int z = -1;
z << 1;          /* HANH VI KHONG XAC DINH truoc C23 */

/* Ly do lich su: chuan dinh nghia dich trai theo phep nhan 2^n
   tren gia tri, va voi so am thi ket qua co the khong bieu dien
   duoc trong kieu do.

   Tu C23, dich trai duoc dinh nghia lai theo MAU BIT, nen
   -1 << 1 la hop le va cho -2.

   Nhung ma cua ban con phai chay tren trinh bien dich cu.
   Quy tac an toan: KHONG dich so co dau. */

terminal

./dich-ub

(-1) << 1               : -2   (UB truoc C23)

Ba: tràn khi dịch trái số có dấu

int x = 1;
x << 31;         /* HANH VI KHONG XAC DINH: 2^31 khong nam trong int */

unsigned u = 1;
u << 31;         /* dung: 2147483648u, kieu khong dau khong tran */

/* Voi kieu KHONG DAU thi khong co tran: chuan dinh nghia moi phep
   toan la mod 2^n. Voi kieu CO DAU thi tran la hanh vi khong xac dinh.
   Bai 3.5 da noi ve khac biet nay, va o day no quay lai. */

#Vì sao phải dùng kiểu không dấu

Kiểu có dấu cho thao tác bit

int  co = 0;
co |= 1 << 31;           /* UB: tran int */
co &= ~(1 << 5);         /* ~(1 << 5) la so am, va >> sau do
                            se dich so hoc */

int x = -8;
x >> 1;                  /* do cai dat quy dinh */

Kiểu không dấu, và hằng số có hậu tố u

uint32_t co = 0;
co |= 1u << 31;          /* dung */
co &= ~(1u << 5);        /* dung */

uint32_t x = 0xFFFFFFF8u;
x >> 1;                  /* luon la dich logic, chen 0 */

Thao tác	Kiểu có dấu	Kiểu không dấu
Tràn	Hành vi không xác định	Định nghĩa rõ, mod 2^n
Dịch phải	Do cài đặt quy định	Luôn chèn 0
Dịch trái số âm	UB trước C23	Không có khái niệm số âm
Bit dấu	Có, và nó phá mọi thứ	Không có
~x	Cho số âm, khó đọc	Cho mẫu bit, dễ đọc

Thăng hạng nguyên biến uint8_t và uint16_t thành int

uint8_t a = 0xFF;

uint8_t b = ~a;          /* ~a duoc tinh tren INT:
                            a thang hang thanh int 255
                            ~255 = -256 (int)
                            gan vao uint8_t -> cat con 0. Dung tinh co. */

uint16_t c = 0xFFFF;
uint32_t d = c << 16;    /* c thang hang thanh int (32 bit co dau)
                            0xFFFF << 16 = 0xFFFF0000
                            gia tri do KHONG nam trong int
                            -> HANH VI KHONG XAC DINH */

uint32_t e = (uint32_t)c << 16;    /* dung: ep truoc khi dich */

/* Quy tac: MOI kieu nho hon int deu thang hang thanh int truoc khi
   tinh toan. Voi thao tac bit tren uint8_t va uint16_t, hay ep
   sang uint32_t hoac unsigned truoc.

   Bai 3.6 goi day la thang hang nguyen, va day la cho no gay hai nhat. */

Dùng kiểu có kích thước cố định

#include <stdint.h>

uint8_t   co8;           /* dung 8 bit, moi noi */
uint16_t  co16;
uint32_t  co32;
uint64_t  co64;

unsigned  u;             /* 16 bit tren mot so vi dieu khien,
                            32 bit tren may tinh */
unsigned long ul;        /* 32 bit tren Windows, 64 tren Linux */

/* Voi thao tac bit, so bit PHAI biet chinh xac. Dung stdint.h.

   Va nho hau to dung khi viet hang: */
uint64_t mat_na = 1ULL << 40;     /* dung */
uint64_t sai    = 1 << 40;        /* UB: 1 la int, dich 40 lan */

#Độ ưu tiên thấp hơn phép so sánh

if (x & 1 == 0)       /* KHONG phai y ban muon */

/* Do uu tien trong C, tu cao xuong thap:
     ...
     <<  >>
     <   <=  >   >=
     ==  !=
     &
     ^
     |
     &&
     ||

   Nen "x & 1 == 0" duoc doc la "x & (1 == 0)" = "x & 0" = 0. */

terminal

gcc -std=c11 -Wall -o uu-tien uu-tien.c && ./uu-tien

v = 3:  v & 1 == 0 -> 0      (v & 1) == 0 -> 0
v = 4:  v & 1 == 0 -> 0      (v & 1) == 0 -> 1
v = 5:  v & 1 == 0 -> 0      (v & 1) == 0 -> 0
v = 6:  v & 1 == 0 -> 0      (v & 1) == 0 -> 1

Bản sai luôn trả về 0, tức là luôn nói số nào cũng lẻ

if (x & 1 == 0) printf("chan\n");

/* Voi MOI gia tri cua x, dieu kien nay deu sai.
   Chuong trinh khong bao gio in "chan".

   Doc bang kem theo: cot thu hai luon la 0, con cot thu ba
   dung bang 1 voi 4 va 6. */

if ((x & 1) == 0) printf("chan\n");     /* dung */

if (!(x & 1))     printf("chan\n");      /* cung dung, va gon hon */

terminal

gcc -Wall -c uu-tien.c

uu-tien.c:5:34: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
    5 |                v, v & 1 == 0, (v & 1) == 0);
      |                     ~~^~~~~~

Cảnh báo -Wparentheses nằm trong -Wall, nên nếu bạn bật -Wall như Bài 1.4 đã dặn thì lỗi này bị bắt ngay.

Lịch sử của cái bẫy này

/* Trong C nguyen thuy, & va | duoc thiet ke TRUOC khi co
   && va ||. Luc do "if (a & b)" nghia la ca hai dung sai,
   nen do uu tien thap hon so sanh la hop ly.

   Khi && va || ra doi, do uu tien cua & va | khong doi duoc nua
   vi se pha ma da co. Dennis Ritchie da noi day la mot trong
   nhung dieu ong tiec nhat ve C.

   He qua: mai mai phai nho bo ngoac. */

Quy tắc thực dụng: bọc ngoặc mọi biểu thức bit

/* Khong can nho bang do uu tien. Chi can mot quy tac: */

(x & MAT_NA) == GIA_TRI
(x | CO) != 0
((x >> 4) & 0xF) == 3
(a & b) | (c & d)

/* Bo ngoac thua khong bao gio sai, va no lam nguoi doc
   khong phai tra bang. Ke ca khi ban CHAC CHAN ve do uu tien,
   nguoi doc ma cua ban thi khong. */

Tự làm thử

Tính bằng tay 12 & 10, 12 | 10, 12 ^ 10 rồi kiểm bằng chương trình.
In ~12 dạng nhị phân bằng hàm ở Bài 31.1 và giải thích vì sao nó bằng -13.
Chạy 1 << 32 trên máy bạn và so kết quả với bài.
Viết if (x & 1 == 0) và chạy với bốn giá trị, xác nhận nó luôn sai.
Viết uint16_t c = 0xFFFF; uint32_t d = c << 16; rồi chạy dưới UBSan nếu có.
So hợp ngữ của x / 8 với unsigned và với int, đếm số lệnh.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Sáu toán tử: AND giữ bit chung, OR gộp, XOR giữ bit khác nhau, NOT đảo, và hai phép dịch.
Ba cạm bẫy dịch bit đều là hành vi không xác định: dịch quá độ rộng kiểu, dịch trái số âm, và tràn khi dịch số có dấu.
1 << 32 trên x86 cho ra 1 chứ không phải 0, vì CPU che số lần dịch xuống năm bit.
Thao tác bit phải dùng kiểu không dấu có kích thước cố định, và hằng số phải có hậu tố u.
& và | có độ ưu tiên thấp hơn ==, nên x & 1 == 0 luôn cho 0. Bọc ngoặc mọi biểu thức bit.