int minA(int x, int y ){
int m = -(x<y);
return y^((x^y)&m);
}

int minB(int x, int y ){
int m = -(x<y);
return y + ((x-y)&m);
}

Tính đúng đắn coi như bài tập cho bạn đọc. Thủ tục tính max tương tự như tính min. Chi tiết coi như bài tập cho bạn đọc.

Đổi dấu có điều kiện

Giả sử ta có một số nguyên có dấu $x$ và một biến $f$. Nếu $f = 1$ thì ta phải đổi dấu của $x$. Nếu $f = 0$ ta giữ nguyên giá trị $x$.

 
Code C:

/*x is negated or not depends on the flag f that only has value 0/1*/
int cond_negationA(int x, int f){
return (x^(-f))+f;
}

int cond_negationB(int x, int f){
return (x-f)^(-f);
}

Ta chứng minh ConditionalNegationA đúng. Nếu $f = 0$, dễ dàng kiểm tra được thủ tục trả lại giá trị $x$. Nếu $f = 1$, ta có:

$\begin{array} {l} (x \oplus -1) +1 & = \overline{x} +1 \qquad (\mbox{ by } (9)) \\ &= -x \qquad (\mbox{ by } (13))\end{array}$

Tương tự như vậy, ta có thể chứng minh được ConditionalNegationB đúng.

Thao tác với bít 1 tận cùng bên phải

Trong phần này, giả sử số nguyên $x$ có biểu diễn nhị phân như sau:

$x = (\alpha 01^a10^b)_2 \qquad (16)$

trong đó $a,b$ có thể bằng $0$. Ta dễ dàng suy ra:

$\begin{array} {l} \overline{x} & = (\overline{\alpha}10^a01^b)_2 \\ x-1 & = (\alpha11^a01^b)_2 \qquad (17) \\ -x &= (\overline{\alpha}10^a10^b)_2 \end{array}$

Từ đó suy ra $\overline{x}+1 = -x = \overline{x-1}$. Ta lại thu được các đẳng thức ở trên.

Một số thao tác với bít 1 tận cùng bên phải quan trọng nên nhớ:

$\begin{array} {l} x\&(x-1) & = (\alpha01^a00^b)_2 \quad \mbox{[Remove the rightmost 1]} \qquad (18) \\ x\&-x &= (0^{|\alpha|}00^a10^b)_2 \quad \mbox{[Extract the rightmost 1]} \qquad (19) \\ x|-x &= (1^{|\alpha|}11^a10^b)_2 \quad \mbox{[Smear the rightmost 1 to the left]} \qquad (20) \\ x\oplus-x &= (1^{|\alpha|}11^a00^b)_2 \quad \mbox{[Remove and smear it to the left]} \qquad (21) \\ x | (x-1) &= (\alpha01^a11^b)_2 \quad \mbox{[Smear the right most 1 to the right]} \qquad (22) \\ x \oplus (x-1) &= (0^{|\alpha|}00^a11^b)_2 \quad \mbox{[Extract and smear it to the right]} \qquad (23) \\ \overline{x} \& (x-1) &= (0^{|\alpha|}00^a01^b)_2 \quad \mbox{[Extract, remove and smear it to the right]} \qquad (24) \end{array}$

Các mặt nạ thần kì

Các mặt nạ "thần kì" (magic mask) được sử dụng rất rất nhiều trong các thủ tục thao tác bít. Các mặt nạ thần kì được định nghĩa như sau:

$\begin{array} {l} \mu_0 & = (\ldots 01010101010101010101010101010101)_2 \\ \mu_1 & = (\ldots 00110011001100110011001100110011)_2 \qquad (25) \\ \mu_2 & = (\ldots 00001111000011110000111100001111)_2 \\ \ldots \ldots \ldots \end{array}$

Về mặt toán học, $\mu_k$ là khai triển nhị phân của $-\frac{1}{2^{2^k}+1}$ do

$(2^{2^k}+1)\mu_k = \mu_k \ll 2^k + \mu_k = (\ldots 1111111)_2 = -1 $

Ở đây, bạn đọc chỉ cần nhớ $\mu_k$ gồm mỗi dãy lặp lại $2^k$ số $0$ liên tiếp sau đó là $2^k$ số 1 liên tiếp.

Các ví dụ (tiếp)

Kiểm tra lũy thừa 2

Thủ tục IsPowerOf2 ở trên kiểm tra xem có tồn tại $y$ sao cho $x = 2^y$ hay không? Dễ thấy, nếu $x = 2^y$ thì $x$ có đúng 1 bít 1. Theo $(18)$, $x\&(x-1)$ sẽ xóa bít 1 tận cùng bên phải. Do đó, $x\&(x-1)$ trả về 0 khi và chỉ khi $x \not= 0$ và $x = 2^y$ với một số $y$ nào đó.

Đếm số bít 1
Cho một số nguyên $x$ (không dấu), đếm số bít $1$ của $x$. Ta có thể thực hiện sử dụng $2k$ thao tác bít trong đó $k$ là số bít biểu diễn của $x$ như sau:

 
Code C:

int count_onesA(unsigned int x){
int c  = 0, i = 0;
for(i = 0; i < 32; i++){
c += (x&1);
x  >>= 1;
}
return c;
}

Sử dụng thuật toán trên trong trường hợp $x$ có $32$ bít cần khoảng $96$ phép tính. Để tăng tốc thuật toán, ta sẽ sử dụng một bảng $B$, gọi là bảng nhớ, để tính trước. Giả sử ta có bảng $B[0,1,\ldots, 255]$ trong đó $B[i] = j,$ $0 \leq i \leq 255$ nếu trong biểu diễn nhịn phân cuả $i$ có $j$ bít 1. Nếu bảng $B$ đã được tính sẵn, ta có thể đếm số bít 1 của $x$ trong 11 phép tính như sau:

 
Code C:

int B[255];// the lookup table for counting bits

void build_lookup_table(){
B[0] = 0; B[1] = 1;
int i = 0, j = 0,s = 0, t = 0;
for( i = 1; i <= 8; i++){
s = 1 <<i; t = (1 << (i+1))-1;
for(j = s; j <= t; j++){
B[j] =B[j& ((1 <<i)-1)] + (j >> i);
}
}
}
/* Remember to build the lookup table before using this method for counting 1s */
int count_onesB(unsigned int x){
int c  = 0;
c+= B[x&0x000000ff];
x >>= 8;
c+= B[x&0x000000ff];
x >>= 8;
c+= B[x&0x000000ff];
x >>= 8;
c+= B[x&0x000000ff];
return c;
}

Trong trường hợp số lượng bít 1 của $x$ không nhiều, ta có thể sử dụng $(18)$. Cụ thể, nếu $x$ có $t$ bít 1 thì ta chỉ cần $3t$ phép tính.

Code C:

int count_onesC(unsigned int x){
int c  = 0;
while(x != 0){
c++;
x = x&(x-1);
}
return c;
}

Chứng minh thủ tục CountOneC đúng coi như bài tập cho bạn đọc.

Đếm số bít 0 cuối cùng

Cho một số nguyên $x$, gọi $\rho(x)$ là số lượng bít 0 cuối cùng (trailing zeros) của $x$. Tính $\rho(x)$. Ví dụ $x = 120 = (01111000)_2$, ta có $\rho(x) = 3$. Dễ thấy nếu $x$ lẻ thì $\rho(x) = 0$. Ta có công thức đệ quy sau của $\rho(x)$:

$\rho(2x+1) = 0 \qquad \rho(2x) = \rho(x) + 1 \qquad \rho(0) = k$

Trong đó $k$ là số bít biểu diễn của $x$.

Cách đầu tiên ta có thể nghĩ đến là duyệt các bít của $x$ từ trái sang phải để đếm số lượng bít 0 cho đến khi ta bắt gắp bít 1 đầu tiên thì dừng. Cách này cần khoảng $4t$ phép tính trong đó $t$ là số lượng bít 0 cuối cùng. Trong trường hợp tồi nhất, đếm số bít 0 cuối cùng cuả số nguyên không dấu 32 bít cần hơn 150 phép tính. Có thể tăng tốc thuật toán này bằng cách sử dụng bảng nhớ như trên.

Cách khác ta có thể nghĩ tới là sử dụng chia để trị để tìm bít 1 phải nhất. Cách này áp dụng cho mọi số nguyên 32 bít sử dụng 19 phép tính.

 
Code C:

/* this method doesn't work for x = 0, readers must be careful when using it*/

int dc_count_zeros(unsigned int x){
if( (x&1) != 0){
return 0;
}
int c = 0;
if((x& 0x0000ffff) == 0){
c+= 16;
x >>= 16;
}
if((x & 0x000000ff )== 0){
c+= 8;
x >>= 8;
}
if((x & 0x0000000f) == 0){
c += 4;
x >>= 4;
}
if((x & 0x00000003) == 0){
c += 2;
x >>= 2;
}
c+= 1 - (x&1);
return c;
}

Tính đúng đắn coi như bài tập cho bạn đọc.

Ngoài ra ta có thể sử dụng mặt nạ thần kì để tính $\rho(x)$. Nhận thấy nếu $x = 2^y$ với một số $y$ nào đó thì:

$\rho(x) = [x\&\mu_0 = 0] + 2[x\&\mu_1 = 0] + 4[x\&\mu_2 = 0] + 8 [x\&\mu_3 = 0] + \ldots \quad (26)$

trong đó hàm $[I(x)] = 1$ nếu $I(x)$ là TRUE và $0$ nếu ngược lại. Do đó, để áp dụng $(26)$, ta sẽ áp dụng $(19)$ trước để xóa hết các bít 1 bên trái của bít 1 cuối cùng. Nếp áp dụng phương pháp này cho số nguyên có $32$ bít thì mất cỡ 16 phép tính. Giả mã như sau:

Code C:

unsigned int m0 = 0x55555555;
unsigned int m1 = 0x33333333;
unsigned int m2 = 0x0f0f0f0f;
unsigned int m3 = 0x00ff00ff;
unsigned int m4 = 0x0000ffff;

/* this method doesn't work for x = 0, readers must be careful when using it*/

int mm_count_zeros(unsigned int x){
x &= -x;
int c  = 0;
if((x&m4) == 0) c+= 16;
if((x&m3) == 0) c+= 8;
if((x&m2) == 0) c+= 4;
if((x&m1) == 0) c+= 2;
if((x&m0) == 0) c+= 1;
return c;
}

Đảo ngược bít

Cho số nguyên $x$, ví dụ $8$ bít $x = (x_7x_6\ldots x_0)_2$, đảo ngược biểu diễn nhị phân của $x$, i.e, trả lại $(x_0x_1\ldots x_7)_2$.

Cách đơn giản nhất là copy các bít của $x$ sang một số $y$ theo thứ tự đảo ngược. Cách này mất $6t$ phép tính trong đó $t$ là vị trí của bít 1 tận cùng bên trái của $x$. Do đó, khi áp dụng cho số 32 bít, trong trường hợp xấu nhất, tổng số thao tác ta cần sử dụng là hơn 180 phép tính.

 
Code C:

unsigned int bit_reversalA(unsigned int x){
int s = 32;
unsigned int y = 0;
while( x!= 0){
y <<=1;
y |= (x&1);
x >>= 1;
s--;
}
y <<= s;
return y;
}

Trong bài toàn này ta cũng có thể áp dụng chia để trị. Ví dụ với $x$ có 8 bít như trên, ta có thể đảo ngược các bít của $x$ trong 3 bước như sau:

$\begin{array} {l} x_6x_7x_4x_5x_2x_3x_0x_1 \\ x_4x_5x_6x_7x_0x_1x_2x_3 \\ x_0x_1x_2x_3x_4x_5x_6x_7 \end{array} $

Để thực hiện bước 1, ta sẽ làm như sau:

$\begin{array} {l} (x \gg_u 1)\& \mu_0 &= (0x_70x_50x_30x_1)_2 \\ (x \& \mu_0) \ll 1 &= (x_60x_40x_20x_00)_2 \\ ((x \gg_u 1)\& \mu_0) | ( (x \& \mu_0) \ll 1) &= (x_6x_7x_4x_5x_2x_3x_0x_1)_2 \end{array} $

Tương tự như vậy các bước tiếp theo ta thực hiện với mặt nạ thần kì $\mu_1,\mu_2, \ldots$. Giả mã với $x$ là số nguyên 32 bít không dấu như sau:

Code C:

unsigned int m0 = 0x55555555; // a magic mask
unsigned int m1 = 0x33333333; // a magic mask
unsigned int m2 = 0x0f0f0f0f; // a magic mask
unsigned int m3 = 0x00ff00ff; // a magic mask
unsigned int m4 = 0x0000ffff; // a magic mask

unsigned int bit_reversalB(unsigned int x){
x = ((x>>1)&m0)|(((x&m0)<<1));
x = ((x>>2)&m1)|(((x&m1)<<2));
x = ((x>>4)&m2)|(((x&m2)<<4));
x = ((x>>8)&m3)|(((x&m3)<<8));
x = (x >> 16)|(x << 16);
return x;
}

Dễ thấy sử dụng các mặt nạ thần kì, ta có thể đảo bít số nguyên 32 bít trong $23$ phép tính và số nguyên 64 bít trong 26 phép tính. Chứng minh tính đúng đắn của thủ tục trên coi như bài tập cho bạn đọc. Trong ví dụ tiếp theo, ta sẽ áp dụng phương pháp đổi chỗ hai bít để đảo bít số nguyên 64 bít sử dụng 26 phép tính.

Đổi chỗ hai bít

Cho số nguyên không dấu $x = (x_k\ldots x_i \ldots x_j \ldots x_0)_2$, đổi chỗ hai bít $x_i$ và $x_j$ của $x$ ($j$ < $i$).

Đặt $\delta = i - j$, ta tiến hành đổi chỗ như sau:

 
Code C:

/* Swap x_i and x_j (32 > i > j) of an unsigned integer x
* Note x = x_31 x_30 .... x_1 x_0*/
unsigned int swap_bitsA(unsigned int x, int i, int j){
int delta = i - j;
unsigned int y = (x >> delta)& (1 << j);
unsigned int z = (x << delta)&(1<< i);
unsigned int m = ~((1<<i) | (1<<j));
x = (x&m)|y|z;
return x;
}

Trong giả mã trên, bước đầu tiên, ta tách $x_i$ ra khỏi $x$ và đặt vào vị trí thứ $j$. Sau đó, ta tách $x_j$ ra khỏi $x$ và đặt vào bít thứ $i$. Mặt nạ $m$ ở trên có tất cả các bít là 1 ngoại trừ bít thứ $i$ và $j$. Suy ra, $x\&m$ sẽ thiết lập bít $x_i$ và $x_j$ về 0. Như vậy, kết quả cuối cùng sẽ là $(x\&m )| y | z$.

Chú ý trong ví dụ đổi chỗ hai số nguyên không dùng biến thứ 3, ta sử dụng phép XOR. Ở bài toán này, ta có thể thực hiện ý tưởng tương tự.

 
Code C:

/* Swap x_i and x_j (32 > i > j) of an unsigned integer x
* Note x = x_31 x_30 .... x_1 x_0*/

unsigned int swap_bitsB(unsigned int x, int i, int j){
int delta = i - j;
unsigned int y = (x ^(x>>delta))&(1<<j);
x = x^y^(y<< delta);
return x;
}

Đầu tiên ta tính $x_i \oplus x_j$ và đưa kết qủa vào vị trí thứ $j$. sau đó đổi $x_i$ thành $x_i \oplus (x_i \oplus x_j) = x_j$ và $x_j$ thành $x_j \oplus (x_i \oplus x_j) = x_i$. Dễ thấy cách này sử dụng ít thao tác bít hơn cách ở trên.

Ý tưởng của thuật toán SwapBitsB còn có thể được dùng để đổi chỗ vài cặp bít cùng một lúc (giống như cách chúng ta đảo bít ở trên). Thông thường, để thực hiện đảo nhiều cặp bít, ta sẽ dùng mặt nạ $\theta$ thay vì $2^j$ như trên.

$\begin{array} {l} y & \leftarrow (x \oplus (x \gg_u \delta))\&\theta \\ x &\leftarrow x \oplus y \oplus (y \ll \delta)\end{array} \qquad (27)$

Ta sẽ gọi thủ tục này là $\delta$-swap. Sử dụng $\delta$-swap, ta có thể thực hiện đảo bít số nguyên 64 bít không dấu trong 26 phép tính (thay vì 28) như sau:

Chi tiết chứng minh tính đúng đắn của thuật toán trên coi như bài tập cho bạn đọc.

Code: bit-tricks-all-in-one

Tham khảo

[1] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams (12th ed.). Addison-Wesley Professional, 2009.
[2] http://graphics.stanford.edu/~seander/bithacks.html
[3] Warren, Henry S. Hacker's Delight. Pearson Education, 2012.