Bài viết gốc tại: http://www.catonmat.net/blog/low-level-bit-hacks/
Tác giả: Peter Krumins.
Dịch giả: Togahepi a.k.a Hà Hiệp.
Tôi quyết định viết bài này vì chủ đề này là kĩ năng thứ 2 cần thiết cho một lập trình viên nhúng - embedded - chiêu trò với low level bit. Bit hack là những mẹo lập trình vô cùng khéo léo để xào xáo những số nguyên theo một cách thông minh và hiệu quả vô cùng. Thay vì thực hiện các phép tính (như là đếm số lượng bit 1 của một số nguyên) bằng cách lặp qua từng bit riêng lẻ, những mẹo lập trình này làm điều tương tự chỉ với 1 hoặc 2 toán tử bitwise được lựa chọn kĩ càng.
Để có thể tiếp tục cùng nhau khám phá, tôi mong rằng bạn đã biết cách bù 2 biểu diễn nhị phân của một số nguyên và cũng biết tất cả về toán tử bitwise. Tôi sẽ sử dụng những kí hiệu sau cho những toán tử bitwise được sử dụng trong bài viết:
& - bitwise and
| - bitwise or
^ - bitwise xor
~ - bitwise not
<< - bitwise shift left
>> - bitwise shift rightNhững số được sử dụng trong bài viết này là những số nguyên 8 bit signed -từ -128 đến 127 (các toán tử này có thể hoàn toàn thực hiện với số nguyên với độ dài bit lớn hơn) được biểu diễn bằng phương pháp bù 2 và được đặt tên là 'x'. Kết quả thường là 'y'. Từng bit riêng lẻ của 'x' được đặt tên là b7, b6, b5, b4, b3, b2, b1 và b0. Bit b7 là bit quan trọng nhất và là bit lớn nhất, và b0 là bit nhỏ nhất.
Tôi sẽ bắt đầu từ những mẹo dễ nhất rồi đến cái khó hơn. Và sẽ có ví dụ cụ thể cho mỗi mẹo để giải thích cách chúng hoạt động.
Nào chiến thôi!
Mẹo hack bit #1. Kiểm tra xem số nguyên là số chẵn hay lẻ.
if ((x & 1) == 0) {
x is chẵn
}
else {
x is lẻ
}Tôi chắc rằng mọi người đều đã biết tới trick này. Ý tưởng ở đây là nếu số nguyên đó lẻ khi và chỉ khi bit nhỏ nhất b0 là 1. Ta phải biểu diễn nhị phân 'x' để biết b0 là 1 hay là 0. Bằng phép toán AND & 'x' với 1 chúng ta đã loại bỏ tất cả bit khác ngoài b0. Nếu kết quả phép toán này là 0, thì 'x' sẽ là số chẵn vì bit b0 là 0. Còn lại 'x' sẽ là lẻ.
Hãy nhìn vô ví dụ dưới đây. Ví dụ số nguyên 43, là số lẻ. Dạng nhị phân của 43 là 00101011. Để ý rằng bit nhỏ nhất b0 là 1 (in đậm đó). Bây giờ hãy AND nó với 1:
00101011
& 00000001 (chú ý: 1 biểu diễn nhị phân là 00000001)
--------
00000001Chúng ta thấy toán tử AND đã xóa tất cả các bit cao hơn từ b1-b7 nhưng giữ nguyên bit b0 ? Kết quả là 1 nói cho chúng ta biết rằng số nguyên đó là số lẻ.
Bây giờ lấy -43 làm ví dụ tiếp nào. Nhắc nhẹ các bạn, một cách nhanh để biểu diễn số theo bù 2 là đảo ngược tất cả các bit và thêm 1. Vì thế -43 sẽ là 11010101 trong hệ nhị phân. Chú ý tiếp rằng bit cuối cùng lại là 1, và số nguyên đó là lẻ. (Chú ý nếu chúng ta sử dụng bù 1 thì nó sẽ không còn đúng nữa!).
Bây giờ lấy ví dụ là một số nguyên chẵn 98. Trong hệ nhị phân 98 là 1100010.
01100010
& 00000001
--------
00000000Sau khi thực hiện phép toán AND với 1 ta được kết quả là 0. Nó có nghĩa là bit b0 của số nguyên 98 là 0. Do đó số nguyên đã cho là số chẵn.
Bây giờ số -98 thì sao. Nó là 10011110. Và bit b0 là 0 và sau khi AND với 1 ta lại được kết quả là 0 vì vậy -98 cũng là số chẵn, hiển nhiên voãi :)).
Mẹo hack bit #2. Kiểm tra xem bit thứ n có giá trị không.
if (x & (1<<n)) {
bit thứ n có giá trị //là bit 1 đó
}
else {
bit thứ n không có giá trị
}Ở mẹo hack bit trước chúng ta thấy rằng (x & 1) để kiểm tra xem bit đầu tiên có giá trị hay không. Ở mẹo này chúng ta chỉ cần nâng kết quả lên và kiểm tra xem bit thứ n có giá trị hay không. Nếu ta di chuyển bit 1 n vị trí sang bên trái và thực hiện phép toán AND, để loại bỏ toàn bộ các bit khác trừ bit thứ n.
Đây là cách chúng ta di chuyển 1 vài bước sang trái:
1 00000001 (cũng giống 1<<0)
1<<1 00000010
1<<2 00000100
1<<3 00001000
1<<4 00010000
1<<5 00100000
1<<6 01000000
1<<7 10000000Bây giờ nếu chúng ta AND với 1 mà đã được dịch chuyển n vị trí sang trái thì ta sẽ dễ dàng loại bỏ toàn bộ các bit khác trừ bit thứ n của 'x'. Nếu kết quả là 0 thì bit đó sẽ là 0, còn đâu thì bit đó đã có giá trị.
Hãy thử làm một vài ví dụ khác nhé.
Số 122 có bit thứ 3 là 1 không? Phép toán chúng ta cần thực hiện sẽ là:
122 & (1<<3)122 sẽ là 01111010 trong hệ nhị phân. Và (1<<3) là 00001000
01111010
& 00001000
--------
00001000Chúng ta thấy kết quả không phải là 0 nên 122 có bit thứ 3 có giá trị.
Chú ý: Trong bài viết này đánh thứ tự bit từ 0. Nên nó sẽ có dạng bit thứ 0, thứ 1,..., thứ 7.
Thế còn -33? Nó có bit thứ 5 có giá trị?
11011111 (-33 trong hệ nhị phân)
& 00100000 (1<<5)
--------
00000000Kết quả là 0, vì thế bit thứ 5 không có giá trị.
Mẹo hack bit #3. Đặt giá trị cho bit thứ n.
y = x | (1<<n)Mẹo hack bit này kết hợp mẹo (1<<n) để cài đặt bit thứ n bằng shifting và kết hợp với toán tử OR. Kết quả của việc OR-ing một biến với một giá trị mà bit thứ n được đặt sẽ bật bit thứ n đó lên. Bởi vì nếu OR-ing bất kì giá trị nào với 0 sẽ giữ nguyên giá trị đó; nhưng OR-ing với 1 sẽ đổi nó thành 1 (nếu nó là 0). Hãy xem nó hoạt động ra sao nhé:
Giả sử ta có số 120, và chúng ta muốn bật bit thứ 2 lên. (từ 0 => 1).
01111000 (120 trong hệ nhị phân)
| 00000100 (1<<2)
--------
01111100Thế còn -120 và bit thứ 6 thì sao?
10001000 (-120 trong hệ nhị phân)
| 01000000 (1<<6)
--------
11001000Mẹo hack bit #4. Tắt bit thứ n (1 => 0).
y = x & ~(1<<n)Điểm cốt yếu của mẹo này là ~(1<<n). Nó sẽ bật tất cả các bit trừ bit thứ n.
Đây là cách nó hoạt động:
~1 11111110 ( tương ứng ~(1<<0))
~(1<<1) 11111101
~(1<<2) 11111011
~(1<<3) 11110111
~(1<<4) 11101111
~(1<<5) 11011111
~(1<<6) 10111111
~(1<<7) 01111111Và khi ta AND biến 'x' thì nó sẽ loại bỏ bit thứ n. Ta chẳng cần quan tâm ở bit thứ n là 0 hay 1, với AND với 0 thì sẽ luôn luôn thành 0.
Ví dụ nè. Hãy tắt bit thứ 4 của 127:
01111111 (127 trong hệ nhị phân)
& 11101111 (~(1<<4))
--------
01101111Mẹo hack bit #5. Đảo chiều bit thứ n.
y = x ^ (1<<n)Mẹo hack bit này cũng sử dụng cách tuyệt vời "mẹo đặt bit thứ n bằng shift" nhưng lần này nó sử dụng toán tử XOR với biến 'x'. Kết quả của việc XOR-ing 2 thứ với nhau đó là nếu 2 bit giống nhau thì kết quả là 0, nếu khác nhau thì sẽ là 1. Vậy thì làm cách nào mà nó đảo chiều bit thứ n? Đây nhé, nếu bit thứ n là 1 thì XOR-ing nó với 1 giống nó nên sẽ thành 0; ngược lại nếu nó là 0 thì XOR-ing nó với 1 khác nó nên sẽ thành 1. Đó, bit đó đã bị đảo ngược.
Đây là một ví dụ nè. Giả sử bạn muốn đảo chiều bit thứ 5 của 01110101:
01110101
^ 00100000
--------
01010101Thế còn trường hợp bit thứ 5 vốn là 0 thì sao?
01010101
^ 00100000
--------
01110101Bạn có để ý thấy gì không? XOR-ing cùng một bit 2 lần thì sẽ trả lại giá trị của nó ban đầu. Đặc tính tuyệt vời này của XOR được sử dụng để tính toán tính đối gương trong mảng RAID và sử dụng với mã hóa mật mã đơn giản và trong nhiều vấn đề khác.
Mẹo hack bit #6. Tắt bit-1 gần nhất từ phải sang.
y = x & (x-1)Bắt đầu thú vị hơn rồi đây!!! Mẹo số 1 -> 5 khá là buồn chán đó.
Mẹo hack bit này tắt bit-1 gần nhất từ phải sang. Ví dụ, cho 1 số nguyên 00101010 (bit-1 gần nhất từ phải sang được bôi đậm đó) ta cần chuyển nó thành 00101000. Hoặc là nếu cho 00010000 ta sẽ biến thành 0 bởi bì nó chỉ có duy nhất một bit-1.
Đây là một số ví dụ khác:
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 (x-1 = 127 (with overflow))
--------
00000000
11111111 (x = tất cả bit đều là 1)
& 11111110 (x-1)
--------
11111110
00000000 (x = không có bit nào là 1)
& 11111111 (x-1)
--------
00000000Tại sao lại có điều kì diệu này?
Nếu bạn nhìn vào những ví dụ này và suy ngẫm, bạn sẽ nhận ra rằng có 2 trường hợp có thể xảy ra:
1. Số này có bit-1 gần nhất từ phải sang. Trong trường hợp này nếu ta trừ 1 đi từ nó sẽ chuyển tất cả các bit thấp hơn bit-1 đó thành 1 và bit-1 gần nhất từ phải sang đó sẽ thành 0 (vì thế nếu giờ bạn cộng với 1 bây giờ thì bạn sẽ lấy lại được số gốc). Bước này sẽ giúp ta chỉ điểm được bit-1 gần nhất từ phải sang đó và giờ khi AND-ing nó với giá trị gốc thì sẽ làm biến mất bit-1 gần nhất bên phải đó.
2. Số này không có bit-1 nào cả (tất cả đều 0). Trong trường hợp này trừ 1 sẽ biến đổi số đó (bởi nó là signed có cả âm dương) và đặt tất cả các bit thành 1. AND-ing tất cả 0 với tất cả 1 thì vẫn ra 0 mà thôi.
Mẹo hack bit #7. Tách biệt bit-1 gần nhất bên phải.
y = x & (-x)Mẹo hack bit này tìm ra bit-1 gần nhất bên phải và đặt tất cả các bit khác về 0. Kết quả cuối cùng chỉ còn bit-1 gần nhất bên phải là còn giá trị. Ví dụ, 01010100 (bit-1 gần nhất bên phải bôi đậm) phải biến thành 00000100.
Đây là một vài ví dụ khác:
10111100 (x)
& 01000100 (-x)
--------
00000100
01110000 (x)
& 10010000 (-x)
--------
00010000
00000001 (x)
& 11111111 (-x)
--------
00000001
10000000 (x = -128)
& 10000000 (-x = -128)
--------
10000000
11111111 (x = tất cả bit đều là 1)
& 00000001 (-x)
--------
00000001
00000000 (x = tất cả bit đều là 0, ko có bit-1 nào cả)
& 00000000 (-x)
--------
00000000Mẹo hack bit này hoạt động được bởi "bù 2". Trong hệ "bù 2" -x sẽ bằng là ~x+1. Bây giờ ta sẽ xem xét 2 trường hợp có thể xảy ra sau:
1. Nếu có bit-1 gần nhất bi. Trong hãy xem xét bit này và chia nó thành thành 2 phần - các bit bên phải và các bit bên trái. Nhớ rằng tất cả các bit bên phải bi-1, bi-2, ... b0 đều là 0 (bởi bi là bit-1 gần nhất từ bên phải). Và các bit bên trái thì vẫn giữ nguyên. Hãy gọi chúng là bi+1, ..., bn.
Bây giờ khi ta tính -x, đầu tiên ta tính ~x sẽ làm bit bi thành 0, bi-1, bi-2, ... b0 sẽ thành 1 và sẽ đảo ngược tất cả các bit bi+1, ..., bn và sau đó ta cộng 1 vào kết quả này.
Do các bit bi-1, bi-2, ... b0 đều là 1, cộng thêm 1 sẽ làm chúng chuyển 1 này chạy một mạch tới bit bi, bởi nó là bit-0 đầu tiên từ phải.
Gộp tất cả lại, kết quả của việc -x là các bit từ bi+1, ..., bn sẽ bị đảo ngược, bit bi giữ nguyên và các bit bi-1, bi-2, ... b0 sẽ đều là 0.
Bây giờ khi AND-ing x với -x sẽ làm các bit từ bi+1, ..., bn sẽ thành 0 hết, bit bi sẽ giữ nguyên và các bit bi-1, bi-2, ... b0 sẽ đều là 0. Chỉ còn 1 bit ở lại, đó chính là bit bi là bit-1 gần nhất từ phải sang.
2. Không có bit-1 nào cả. Số đã cho là 0. Âm của 0 trong "bù 2" thì vẫn là 0 do vậy 0&0 = 0. Không có bit nào được bật cả.
Chúng ta đã chứng minh được mẹo hack bit này đúng một cách chặt chẽ rùi đó.
Mẹo hack bit #8. Đặt giá trị cho tất cả các bit bên phải của bit-1 gần nhất bên phải.
y = x | (x-1)Để hiểu mẹo này tốt nhất là làm luôn ví dụ. Cho 1 số 01010000 nó sẽ phải biến thành 01011111. Tất cả bit-0 ở phía bên phải của bit-1 gần nhất bên phải nó đều biến thành 1.
Đây không phải là một mẹo hoàn toàn chuẩn, bởi, nó sẽ tạo ra tất cả 1 nếu x = 0.
Hãy nhìn vào các ví dụ sau:
10111100 (x)
| 10111011 (x-1)
--------
10111111
01110111 (x)
| 01110110 (x-1)
--------
01110111
00000001 (x)
| 00000000 (x-1)
--------
00000001
10000000 (x = -128)
| 01111111 (x-1 = 127)
--------
11111111
11111111 (x = -1)
| 11111110 (x-1 = -2)
--------
11111111
00000000 (x)
| 11111111 (x-1)
--------
11111111Hãy chứng minh nó nào, bởi không chặt chẽ như mẹo hack bit trước (bởi tốn thời gian quá và đây cũng đâu phải báo cáo khoa học gì đâu :v). Lại có 2 trường hợp nè. Hãy bắt đầu với cái dễ hơn trước.
1. Không có bit-1 nào gần nhất bên phải. Tức là x = 0 và x - 1 sẽ là -1. -1 trong "bù 2" sẽ là 11111111. Or-ing 0 với 11111111 sẽ ra 11111111. (Không phải là kết quả mong muốn nhưng mà kệ nó vậy).
2. Có bit-1 gần nhất bên phải ở bit thứ i bi. Lại chia các bit thành 2 nửa (giống ví dụ trước). Làm tính (x-1) sẽ chỉ thay đổi các bit ở bên phải, biến bi thành 0, và tất cả bit dưới nó thành 1. Bây giờ OR-ing x với x-1 sẽ giữa nguyên các bit cao hơn (bên trái), giữ nguyên bit bi bởi nó vốn là 1, và tất cả các bit dưới nó sẽ được bật thành 1 hết. Kết quả là bit-1 gần nhất bên phải sẽ biến tất cả các bit dưới nó thành 1 hết.
Mẹo hack bit #9. Tách biệt bit-0 gần nhất bên phải.
y = ~x & (x+1)Mẹo hack bit này ngược lại với mẹo số 7. Nó sẽ tìm ra bit-0 gần nhất bên phải rồi sẽ tắt tất cả các bit còn lại và đặt cho bit-0 này thành 1. Ví dụ nó sẽ tìm ra 0 được bôi đậm trong số sau 10101011, và tạo ra 00000100.
Thêm các ví dụ:
10111100 (x)
--------
01000011 (~x)
& 10111101 (x+1)
--------
00000001
01110111 (x)
--------
10001000 (~x)
& 01111000 (x+1)
--------
00001000
00000001 (x)
--------
11111110 (~x)
& 00000010 (x+1)
--------
00000010
10000000 (x = -128)
--------
01111111 (~x)
& 10000001 (x+1)
--------
00000001
11111111 (x = không có bit-0 nào cả)
--------
00000000 (~x)
& 00000000 (x+1)
--------
00000000
00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001Chứng minh: Giả sử có bit-0 gần nhất bên phải. Khi ta tính ~x (not x) thì biến bit này từ 0 thành 1. Và cũng như vậy x + 1 (bởi vì các bit bên phải của bit-0 gần nhất bên phải đều là 1). Bây giờ khi AND-ing ~x với x+1 nó sẽ làm bốc hơi tất cả các bit bên trên bit-0 gần nhất bên phải này. Đó là các bit cao hơn nó. Bây giờ còn các bit bên phải của bit-0 này? Chúng cũng bị bốc hơi luôn vì x+1 biến chúng thành 0 hết (vốn đều là 1) và ~x thì cũng biến chúng thành 0. Chúng sẽ AND-ing với 0 do đó sẽ bị bay màu hết.
Mẹo hack bit #10. Bật bit-0 gần nhất bên phải.
y = x | (x+1)Mẹo này biến bit-0 gần nhất bên phải thành 1. Ví dụ cho số nguyên 10100011 nó sẽ biến thành 10100111.
Thêm các ví dụ nè:
10111100 (x)
| 10111101 (x+1)
--------
10111101
01110111 (x)
| 01111000 (x+1)
--------
01111111
00000001 (x)
| 00000010 (x+1)
--------
00000011
10000000 (x = -128)
| 10000001 (x+1)
--------
10000001
11111111 (x = không có bit-0 nào cả)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001Đây là cách chứng minh. OR-ing x với x+1 không làm mất đi số nào cả. Cộng thêm 1 vào x sẽ đổ đầy bit-0 đầu tiên bên phải. Kết quả sẽ là max{x,x+1}. Nếu x+1 bị quá giới hạn thì kết quả chính là x và không có bit-0 nào cả. Nếu không thế nó sẽ là x+1 với tất cả bit bên phải đều lấp đầy bởi 1.
Hàng khuyến mãi.
Nếu bạn muốn chơi đùa nhiều hơn với những mẹo này, đây là hàm để in dạng hệ nhị phân của 1 số nguyên 8 bit signed trong Pert, Python và C:
Perl:
sub int_to_bin {
my $num = shift;
print unpack "B8", pack "c", $num;
}Hoặc là với dòng lệnh:
perl -wle 'print unpack "B8", pack "c", shift' <integer>
# For example:
perl -wle 'print unpack "B8", pack "c", shift' 113
01110001
perl -wle 'print unpack "B8", pack "c", shift' -- -128
10000000Python:
def int_to_bin(num, bits=8):
r = ''
while bits:
r = ('1' if num&1 else '0') + r
bits = bits - 1
num = num >> 1
print rC:
void int_to_bin(int num) {
char str[9] = {0};
int i;
for (i=7; i>=0; i--) {
str[i] = (num&1)?'1':'0';
num >>= 1;
}
printf("%s\n", str);
}Thêm nữa nè: Có một cuốn sách chuyên về bit hack là "Hacker's Delight". Bạn sẽ yêu nó nếu bạn yêu thích vấn đề này.
Bình luận