Bài 31.528 phút đọc

Thủ thuật bit và hàm dựng sẵn

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

Kiểm tra lũy thừa của hai, xóa bit thấp nhất, lấy bit thấp nhất
Đếm bit một bằng ba cách và đo tốc độ
Đảo thứ tự byte và kiểm tra thứ tự byte của máy
Dùng các hàm dựng sẵn của GCC và biết điều kiện của chúng

Mười biểu thức mà mỗi cái thay được một vòng lặp. Chúng xuất hiện trong thư viện chuẩn, trong nhân hệ điều hành, và trong mọi bài phỏng vấn về thao tác bit. Bài này giải thích vì sao chúng chạy, chứ không chỉ liệt kê.

#Bit một thấp nhất

x & (x - 1)      /* XOA bit 1 thap nhat */
x & (-x)         /* LAY rieng bit 1 thap nhat */
x | (x + 1)      /* BAT bit 0 thap nhat */

terminal

./thu-thuat

  y            = 0xB4 = 180
  y & (y-1)    = 0xB0  (xoa bit 1 thap nhat)
  y & (-y)     = 0x04  (lay bit 1 thap nhat)

Vì sao x & (x - 1) xóa bit một thấp nhất

x     = 1011 0100
x - 1 = 1011 0011

/* Phep tru 1 lam gi:
     - bit 1 THAP NHAT (o vi tri 2) thanh 0
     - moi bit 0 BEN PHAI no thanh 1
     - moi bit BEN TRAI no khong doi

   Nen AND hai cai:
     bit ben trai:   giong nhau, giu nguyen
     bit thap nhat:  1 AND 0 = 0        <- bi xoa
     bit ben phai:   0 AND 1 = 0        <- van la 0

x & (x-1) = 1011 0000 */

Vì sao x & (-x) lấy riêng bit một thấp nhất

x  = 1011 0100
-x = 0100 1100        /* bu hai: dao het roi cong 1 */

/* -x = ~x + 1, va:
     ~x     = 0100 1011
     ~x + 1 = 0100 1100

   Phep cong 1 lan qua moi bit 1 o cuoi cua ~x, tuc moi bit 0
   o cuoi cua x, roi dung lai o bit 1 thap nhat cua x va lat no.

   Ket qua: -x co bit thap nhat GIONG x, moi bit ben trai NGUOC lai.

x & (-x) = 0000 0100    <- chi con dung bit do */

x & (-x) với kiểu có dấu là hành vi không xác định

int x = INT_MIN;

x & (-x)         /* -INT_MIN TRAN int -> hanh vi khong xac dinh */

/* Voi kieu KHONG DAU thi khong co tran, phep toan la mod 2^n: */

uint32_t u = 0x80000000u;
u & (0u - u)     /* 0 - 0x80000000 = 0x80000000, hop le */

/* Nen viet: */
#define BIT_THAP_NHAT(x) ((x) & (0u - (x)))     /* voi unsigned */

/* Hoac ep tuong minh: */
uint32_t t = y & (uint32_t)(-(int32_t)y);       /* van UB neu y la INT_MIN */

/* Cach an toan nhat: khai bao bien la unsigned tu dau. */

Kiểm tra lũy thừa của hai

int la_luy_thua_2(uint32_t x) {
    return x && !(x & (x - 1));
}

/* Luy thua cua 2 co DUNG MOT bit bang 1.
   Xoa bit do di thi con 0.

   Dieu kien "x &&" o dau la bat buoc: voi x = 0 thi
   0 & (0-1) = 0 & 0xFFFFFFFF = 0, nen ve phai la dung,
   nhung 0 KHONG phai luy thua cua 2. */

terminal

./thu-thuat --luy-thua

  0 -> khong
  1 -> co
  2 -> co
  3 -> khong
  4 -> co
  5 -> khong
  6 -> khong
  7 -> khong
  8 -> co
  9 -> khong
  1024 -> co

Làm tròn lên lũy thừa của hai gần nhất

uint32_t lam_tron_len(uint32_t x) {
    if (x == 0) return 1;

    --x;                 /* de x da la luy thua 2 thi giu nguyen */

    x |= x >> 1;         /* bat bit ben phai bit cao nhat */
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;        /* gio moi bit tu bit cao nhat tro xuong deu la 1 */

    return x + 1;        /* cong 1 lan qua het, cho luy thua ke tiep */
}

/* Nam dong dich: 1 + 2 + 4 + 8 + 16 = 31, du de lan het 32 bit.
   Voi uint64_t thi them mot dong "x |= x >> 32". */

terminal

./thu-thuat --lam-tron

  0 -> 1
  1 -> 1
  2 -> 2
  3 -> 4
  4 -> 4
  5 -> 8
  6 -> 8
  7 -> 8
  8 -> 8
  9 -> 16
  1000 -> 1024

#Đếm bit một, bốn cách

/* Cach 1: duyet 32 bit, luon 32 vong */
int dem_duyet(uint32_t x) {
    int c = 0;

    for (int i = 0; i < 32; ++i) c += (x >> i) & 1u;

    return c;
}

/* Cach 2: Brian Kernighan, so vong bang so bit 1 */
int dem_kern(uint32_t x) {
    int c = 0;

    while (x) { x &= x - 1; ++c; }

    return c;
}

/* Cach 3: tra bang 256 muc, bon lan tra */
static unsigned char BANG[256];

void dung_bang(void) {
    for (int i = 0; i < 256; ++i) BANG[i] = (unsigned char)dem_kern((uint32_t)i);
}

int dem_bang(uint32_t x) {
    return BANG[x & 0xFF] + BANG[(x >> 8) & 0xFF]
         + BANG[(x >> 16) & 0xFF] + BANG[x >> 24];
}

/* Cach 4: ham dung san, dung lenh CPU neu co */
int dem_builtin(uint32_t x) { return __builtin_popcount(x); }

terminal

./dem-bit

gia tri      duyet kern bang popcount
0x00000000     0    0    0    0
0x00000001     1    1    1    1
0x00000007     3    3    3    3
0x000000FF     8    8    8    8
0xF0F0F0F0    16   16   16   16
0xFFFFFFFF    32   32   32   32
0x00003039     6    6    6    6

terminal

# Ba mươi triệu lần đếm, gcc -O2

gcc -std=c11 -O2 -o bench bench.c && ./bench

duyet tung bit : 0.519 giay
Kernighan      : 0.147 giay
tra bang 256   : 0.041 giay
popcount       : 0.102 giay

# Cùng chương trình, thêm cờ nói với gcc rằng CPU có lệnh POPCNT

gcc -std=c11 -O2 -mpopcnt -o bench bench.c && ./bench

tra bang 256   : 0.040 giay
popcount       : 0.038 giay

popcount không tự động nhanh, phải nói với trình biên dịch

terminal

# Không có cờ: gcc sinh ra sáu lệnh, thuật toán phần mềm

gcc -O2 -S -masm=intel -o - pc.c | grep -c '^\s*[a-z]'

# Có cờ: một lệnh duy nhất

gcc -O2 -mpopcnt -S -masm=intel -o - pc.c | grep popcnt

	popcnt	eax, ecx

/* Lenh POPCNT co tu Intel Nehalem nam 2008 va AMD Barcelona nam 2007.
   Nhung gcc mac dinh sinh ma chay duoc tren MOI CPU x86-64,
   ke ca doi dau tien khong co POPCNT.

   Nen __builtin_popcount mac dinh la mot thuat toan PHAN MEM,
   va no cham hon ban tra bang 2.5 lan trong phep do o tren.

   Bat lenh CPU bang mot trong hai cach: */

gcc -mpopcnt ...              /* chi bat POPCNT */
gcc -march=native ...         /* bat moi lenh CPU cua may DANG bien dich */
gcc -march=x86-64-v2 ...      /* bat tap lenh cua CPU tu 2009 tro di */

/* Canh bao: -march=native lam chuong trinh KHONG chay tren
   may cu hon. Voi phan mem phat hanh, dung -march=x86-64-v2
   hoac phat hien luc chay. */

Cách	Thời gian đo được	Số vòng lặp	Dùng khi
Duyệt 32 bit	0,519 s	Luôn 32	Không bao giờ, trừ khi dạy học
Kernighan	0,147 s	Bằng số bit 1	Dữ liệu thưa, ít bit 1
Tra bảng 256	0,041 s	Không có, bốn lần tra	Không có lệnh CPU, và có 256 byte để trống
popcount, không cờ	0,102 s	Không có	Mặc định, khả chuyển
popcount, có -mpopcnt	0,038 s	Một lệnh	Biết chắc CPU đích

Ba mươi triệu lần đếm trên cùng một máy. Con số tùy CPU, hãy tự đo.

Kernighan thắng khi dữ liệu thưa

/* Phep do o tren dem tu 0 den 30 trieu, tuc trung binh
   khoang 12 bit 1 moi so.

   Neu du lieu chi co 1 hoac 2 bit 1, vi du mot bo co, thi
   Kernighan chi lap 1 hoac 2 lan va no nhanh hon ca tra bang.

   Neu du lieu gan nhu day bit 1 thi no lap 30 lan va cham nhat.

   Do la ly do khong co cau tra lai duy nhat: DO tren du lieu
   THAT cua ban. */

#Hàm dựng sẵn của GCC

Hàm	Trả về	Điều kiện	Lệnh CPU tương ứng
__builtin_popcount(x)	Số bit bằng 1	Không có	POPCNT
__builtin_clz(x)	Số bit 0 ở đầu	x PHẢI khác 0	LZCNT hoặc BSR
__builtin_ctz(x)	Số bit 0 ở cuối	x PHẢI khác 0	TZCNT hoặc BSF
__builtin_ffs(x)	Vị trí bit 1 thấp nhất, đếm từ 1	Không có
__builtin_parity(x)	Số bit 1 chẵn hay lẻ	Không có
__builtin_bswap16/32/64(x)	Đảo thứ tự byte	Không có	BSWAP

Thêm hậu tố l cho unsigned long và ll cho unsigned long long, ví dụ __builtin_popcountll.

terminal

./builtin

  clz(1)      = 31,  ctz(1)      = 0
  clz(0x100)  = 23,  ctz(0x100)  = 8
  clz(0x8000) = 16,  ctz(0x8000) = 15

clz và ctz với đối số 0 là hành vi không xác định

__builtin_clz(0)      /* HANH VI KHONG XAC DINH */
__builtin_ctz(0)      /* HANH VI KHONG XAC DINH */

/* Ly do: lenh BSR va BSF cua x86 KHONG dinh nghia ket qua khi
   toan hang bang 0, chung chi dat co ZF. GCC boc chung lai
   nhung khong them lenh kiem tra, vi the se cham hon.

   Cach dung an toan: */

static inline int clz_an_toan(uint32_t x) {
    return x ? __builtin_clz(x) : 32;
}

static inline int ctz_an_toan(uint32_t x) {
    return x ? __builtin_ctz(x) : 32;
}

/* Tu C23 co ham chuan trong <stdbit.h>, va chung CO dinh nghia
   cho gia tri 0: */
#include <stdbit.h>

stdc_leading_zeros(x)      /* tra 32 khi x la 0 */
stdc_trailing_zeros(x)
stdc_count_ones(x)
stdc_bit_width(x)
stdc_bit_ceil(x)           /* chinh la lam_tron_len o tren */

/* Neu trinh bien dich cua ban ho tro C23 thi dung stdbit.h:
   no la chuan, va no khong co cai bay gia tri 0. */

Ba ứng dụng thật của clz và ctz

/* 1. So bit can de bieu dien x, tuc log2 lam tron len */
static inline int so_bit(uint32_t x) {
    return x ? 32 - __builtin_clz(x) : 0;
}

so_bit(1)    /* 1  */
so_bit(255)  /* 8  */
so_bit(256)  /* 9  */

/* 2. log2 nguyen cua mot luy thua 2 */
static inline int log2_luy_thua(uint32_t x) {
    return __builtin_ctz(x);         /* x phai khac 0 va la luy thua 2 */
}

log2_luy_thua(1024)    /* 10 */

/* 3. Duyet moi bit 1 trong mot bo co, khong duyet bit 0 */
uint32_t co = 0x00840020u;

while (co) {
    int n = __builtin_ctz(co);       /* so hieu bit 1 thap nhat */

    xu_ly_co(n);

    co &= co - 1;                    /* xoa bit do */
}

/* Vong lap chay dung 3 lan thay vi 32 lan. Voi bo co thua thi
   day la khac biet lon. */

Hàm dựng sẵn là mở rộng, không phải chuẩn

/* __builtin_* co tren GCC va Clang, KHONG co tren MSVC.
   MSVC co ten khac: */

#ifdef _MSC_VER
  #include <intrin.h>
  static inline int dem_bit(uint32_t x) { return (int)__popcnt(x); }
#else
  static inline int dem_bit(uint32_t x) { return __builtin_popcount(x); }
#endif

/* Hoac dung ban tu viet lam mac dinh: */
#if defined(__GNUC__) || defined(__clang__)
  #define DEM_BIT(x) __builtin_popcount(x)
#else
  #define DEM_BIT(x) dem_bit_tu_viet(x)
#endif

/* Bai 19.6 da noi ve mau phat hien trinh bien dich nay. */

#Thứ tự byte và đảo bit

/* Kiem tra thu tu byte cua may */
static int nho_truoc(void) {
    uint32_t u = 1;

    return *(const unsigned char *)&u == 1;
}

/* Dao thu tu byte cua mot so 32 bit */
uint32_t dao_byte(uint32_t x) {
    return ((x & 0x000000FFu) << 24)
         | ((x & 0x0000FF00u) <<  8)
         | ((x & 0x00FF0000u) >>  8)
         | ((x & 0xFF000000u) >> 24);
}

terminal

./dao

  dao_byte(0x12345678) = 0x78563412
  bswap32 (0x12345678) = 0x78563412

Nhưng cách đúng để đọc dữ liệu là không cần biết thứ tự byte

Đọc rồi đảo theo máy

uint32_t v;
memcpy(&v, bo_dem, 4);

if (!nho_truoc()) v = dao_byte(v);      /* doi neu can */

Ghép byte tường minh

/* Ghep tung byte: KHONG phu thuoc thu tu byte cua may */
uint32_t v = ((uint32_t)b[0] << 24) | ((uint32_t)b[1] << 16)
           | ((uint32_t)b[2] <<  8) |  (uint32_t)b[3];

/* Doc dung tren MOI may, va khong can ham kiem tra nao.
   Bai 18.8 da dung dung cach nay cho dinh dang tep. */

Đảo thứ tự bit, không phải byte

uint32_t dao_bit(uint32_t x) {
    /* Doi cho tung cap bit */
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);

    /* Doi cho tung cap hai bit */
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);

    /* Doi cho tung cap bon bit */
    x = ((x >> 4) & 0x0F0F0F0Fu) | ((x & 0x0F0F0F0Fu) << 4);

    /* Roi doi cho cac byte */
    return __builtin_bswap32(x);
}

terminal

./dao --bit

  dao_bit (0x80000001) = 0x80000001
  dao_bit (0x12345678) = 0x1E6A2C48

Ba hằng số mặt nạ trong hàm trên

0x55555555 = 0101 0101 ... 0101     /* moi bit CHAN, tinh tu 0 */
0x33333333 = 0011 0011 ... 0011     /* moi cap bit chan */
0x0F0F0F0F = 0000 1111 ... 1111     /* moi nua byte thap */

/* Y tuong chung cua ky thuat "chia doi va doi cho":
     buoc 1 doi cho cac bit ke nhau
     buoc 2 doi cho cac cap bit
     buoc 3 doi cho cac nhom bon bit
     buoc 4 doi cho cac byte

   Bon buoc doi cho toan bo 32 bit, va moi buoc chi ba lenh.
   Tong 12 lenh thay cho mot vong lap 32 vong.

   Cung y tuong dung cho popcount ban phan mem, va do la ly do
   ban do o tren chay het 0.102 giay chu khong phai 0.5 giay. */

Kiểm tra hàm đảo bit bằng bốn trường hợp

assert(dao_bit(0x00000000u) == 0x00000000u);
assert(dao_bit(0xFFFFFFFFu) == 0xFFFFFFFFu);
assert(dao_bit(0x80000001u) == 0x80000001u);   /* doi xung, giu nguyen */
assert(dao_bit(0x00000001u) == 0x80000000u);   /* bit dau thanh bit cuoi */

/* Va mot phep kiem manh hon: dao hai lan phai ve nhu cu */
for (uint32_t i = 0; i < 1000000u; ++i)
    assert(dao_bit(dao_bit(i)) == i);

#Bảng mười thủ thuật

Việc	Biểu thức	Ghi chú
Kiểm lẻ	x & 1	Nhanh hơn x % 2 với kiểu có dấu
Nhân 2 mũ n	x << n	Chỉ khi không tràn
Chia 2 mũ n	x >> n	Chỉ với x không âm, hoặc kiểu không dấu
Lấy dư 2 mũ n	x & ((1u << n) - 1)	Chỉ với kiểu không dấu
Xóa bit 1 thấp nhất	x & (x - 1)
Lấy bit 1 thấp nhất	x & (0u - x)	Dùng 0u - x, không dùng -x
Kiểm lũy thừa 2	x && !(x & (x - 1))	Điều kiện x khác 0 bắt buộc
Đảo dấu	(~x) + 1u	Chính là bù hai
Giá trị tuyệt đối không rẽ nhánh	(x + m) ^ m với m = x >> 31	Giả định dịch số học
Đổi hai biến không dùng biến tạm	a ^= b; b ^= a; a ^= b;	HỎNG nếu a và b cùng địa chỉ

Thủ thuật XOR để hoán đổi là một cái bẫy

void hoan_doi_xor(int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int x = 5;
hoan_doi_xor(&x, &x);      /* x thanh 0 */

/* Dien bien:
     *a ^= *b   ->  x = x ^ x = 0
     *b ^= *a   ->  x = 0 ^ 0 = 0
     *a ^= *b   ->  x = 0 ^ 0 = 0

   Mat gia tri. Va no khong nhanh hon: */

void hoan_doi_tam(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Va no khong nhanh hon. gcc -O2 sinh ra:

     xor_hd:                      tam_hd:
         mov  eax, [rcx]              mov  eax, [rcx]
         xor  eax, [rdx]              mov  r8d, [rdx]
         mov  [rcx], eax              mov  [rcx], r8d
         xor  eax, [rdx]              mov  [rdx], eax
         mov  [rdx], eax              ret
         xor  [rcx], eax
         ret

   SAU lenh so voi BON. Ban co bien tam ngan hon, va no khong
   co chuoi phu thuoc noi tiep nhu ban XOR.

   Thu thuat nay ra doi khi thanh ghi CPU rat it. Ngay nay
   no chi con la mot cau hoi phong van, va cau tra loi dung la
   "khong dung no". */

Giá trị tuyệt đối không rẽ nhánh cũng đã lỗi thời

int m = x >> 31;              /* -1 neu x am, 0 neu duong */
int abs_x = (x + m) ^ m;

/* Ba gia dinh:
     1. int co dung 32 bit
     2. dich phai so am la dich SO HOC, chi la do cai dat quy dinh
     3. x khac INT_MIN

   Va gcc -O2 sinh ra CHINH XAC doan ma nay cho "x < 0 ? -x : x".
   Nen viet ban de doc, va de trinh bien dich lo phan con lai. */

int abs_x = x < 0 ? -x : x;   /* van UB voi INT_MIN, nhung ro rang */

terminal

gcc -O2 -S -masm=intel -o - abs.c

f:
    mov  edx, ecx
    mov  eax, ecx
    sar  edx, 31
    xor  eax, edx
    sub  eax, edx
    ret

Tự làm thử

Chạy x & (x-1) và x & (-x) trên 0xB4 rồi vẽ bit ra giấy để kiểm.
Cài bốn cách đếm bit và xác nhận chúng cho cùng kết quả với bảy giá trị trong bài.
Đo tốc độ bốn cách trên máy bạn, rồi thêm -mpopcnt và đo lại.
Gọi __builtin_clz(0) và xem kết quả trên máy bạn.
Cài lam_tron_len và kiểm với 0 tới 9 cùng 1000.
Cài dao_bit và kiểm bằng phép đảo hai lần trên một triệu giá trị.
Gọi hoan_doi_xor(&x, &x) và xác nhận x thành 0.

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

x & (x - 1) xóa bit một thấp nhất, và x & (0u - x) lấy riêng nó.
Bốn cách đếm bit chênh nhau tới mười ba lần, và __builtin_popcount chỉ nhanh nhất khi bạn thêm -mpopcnt.
__builtin_clz và __builtin_ctz với đối số 0 là hành vi không xác định. C23 có stdbit.h không có cái bẫy đó.
Đọc dữ liệu từ tệp hay mạng thì ghép byte tường minh, đừng đọc rồi đảo theo thứ tự byte của máy.
Thủ thuật XOR để hoán đổi hỏng khi hai con trỏ cùng địa chỉ, và nó còn chậm hơn bản dùng biến tạm.