Các thao tác xử lý bit trong C/C++

[hailoc12]

Đề tài này sẽ cung cấp cho các bạn những kiến thức về việc sử dụng các phép toán logic từ đó giúp cho việc thiết kế các biểu thức logic dùng rất nhiêu trong các phép toán điều kiện được nhanh chóng, chính xác, hiệu quả.

* Quy ươc về vị trí của các bit;
Mỗi byte bao gồm 8 bit được mã số từ phải sang trái còn gọi là bit thấp đến bit cao. Bit nằm ở bên phải được xem là thấp hơn bit nằm ở bên trái. Các bit được đánh số như sau:
7 6 5 4 3 2 1 0
Mỗi bit có thể nhận 1 trong 2 giá trị là 0 hoặc 1. Tại mỗi thời điểm thực hiện chương trình mỗi bit đươc nhận giá trị xác định. Moi số nguyên trong máy đều biểu diễn dưới dạng nhị phân, thí dụ số 19 được biểu diễn như sau:
Bit 7 6 5 4 3 2 1 0
Giá trị 0 0 0 1 0 0 1 1 (số 19)
* Các phép toán logic
Các phép toán sau đây thực hiện trên các giá trị nguyên và cho kết quả là các giá trị nguyên.
1. Phép đảo bit Not: đổi giá trị của mọi bit từ 0 thành 1 và ngược lại. Trong C phép đảo được kí hiệu là ~ .Ví dụ

char x, y;    x=19; //x=00010011//    y=~x; //y=11101100(236)//

2. Phép cộng logic trên các bit (OR) thực hiện trên từng cặp bit tương ứng của các toán hạng theo bảng cộng sau:

    a    b                 a  OR b    0    0                     0    0    1                     1    1    0                     1    1    1                     1

Quy tắc: Tổng hai bit bằng 0 khi và chỉ khi cả hai bit bằng 0 ngoài ra tổng nhận giá trị 1;
Trong C phép OR được biểu diễn bằng kí hiệu ||
Ví dụ

char x, y, z;    x= 19;//x=00010011//    y= 21;//y=00010101//    z= x||y;//z=00010111(23)//

3. Phép nhân logic trên các bit AND: thực hiện trên từng cặp bit tương ứng của các toán hạng theo bảng nhân sau:

   a   b                  a AND b   0   0                     0   0   1                     0   1   0                     0   1   1                     1

Quy tắc: Tích hai bit bằng 1 khi và chỉ khi cả hai bit bằng 1, ngoài ra tích nhận giá trị 0.
Trong C phép AND được biểu diễn bằng kí hiệu &&
Ví dụ

char x, y, z;x=19;//x=00010011/y=21;//y=00010101//z=x AND y;//z=00010001(17)//

4. Phép cộng loại trừ trên các bit (XOR) : thực hiện trên từng cặp bit tương ứng của các toán hạng theo bảng sau

    a     b                  a XOR b    0     0                       0    0     1                       1    1     0                       1    1     1                       0

Quy tắc: tổng loại trừ của hai bit bằng 1 khi và chỉ khi hai bit đó chứa các giá trị khác nhau, ngoài ra tổng loại trừ nhận giá trị 0.
Phép toán trên cũng còn được gọ là phép so sánh khác (khác nhau là đúng, bằng nhau là sai)
Trong C không có phép toàn này. (Có bạn nào biết cách thể hiện phép XOR bằng phép AND và OR không ?)
Ví dụ

Ví dụ này chỉ là môt tảchar x, y, x;    x= 19;//x=00010011//    y= 21;//y=00010101//    Z=x XOR Y;//z=00000110(6)//

(Còn tiếp)

[hailoc12]

Tiếp tục:
5. Phép dịch trái (Shl): x Shl i cho gái trị nhận được từ số nguyên x sau khi dịch số đó qua trái i bit.
Quy tắc: Muốn nhân 1 số với 2 ta dịch số đó qua trái 1 bit. Tổng quát, muốn nhân một sốnguyene với 2^i ta dịch số đó qua trái i bit;
x Shl i= x*n; với n=2^i
Trong C không hỗ trợ phép toán này nhưng có thể dùng phép chia nguyên cho 2^i để thực hiện
Thí dụ

Chỉ để minh họa{   chả x, y;    x=19;//x=00010011//    y=x Shl 2;//y=01001100=x*4=76// }

6. Phép dịch phải
(Tương tự như phép dịch trái nhưng số nguyên sẽ được dịch sang phải i bit)

MỘT SỐ ỨNG DỤNG
*Ứng dụng 1(lấy bit). Viết hàm getbit(x,i) cho giá trị của bit thứ i(tính từ phải sang) của số nguyên x.

char Getbit(char x, i){   return (x Shr i) && 1;}

*Ứng dụng 2(lấy số) Viết hàm GetNum(x, j, i) cho số tạo bởi các bit tính từ trái qua phải là bit thứ j đến bit thứ i (j>=i). Thí dụ
GetNum(103,5,1)=19 vì 103=0000 0000 0110 0111
do dó GetNum(103,5,1)= 0000 0000 0001 0011 =19
Bài giải: Gọi số lượng bit của x là L(x) , trước hết ta phải hóa 0 các bit nằm ở bên trái bit thứ j. Muốn vậy ta dịch x qua trái k= L(x)-1-j bit. Sau đó ta chuyển giá trị thu được về cấu hình ban đầu tức là dịch phải k bit rồi tiếp tục dịch phải i bit để thu được số cần tìm. Hàm sizeof(x) cho ta số byte trong x. Nhân giá trị này với 8 ta sẽ được số bit trong x. Vì phép nhân 8 tương đuơng với phép dịch trái 3 bit nên sizeof(x) Shl 3 cho ta số bit trong x. Vì các bit được mã số từ phải sang trái bắt đầu từ bit 0 cho nên số hiệu cao nhất trong x sẽ là sizeof(x) Shl 3 -1

char Getnum(char x, j, i){   char k;         k= (sizeof(x) Shl 3)-1-j         return x Shl k Shr k Shr i;}

Đối với 2 hàm Getbit và GetNum ở trên ta sé có được một số ứng dụng như chuyển từ số tự nhiên sang biểu diễn nhị phân, thập lục phân, bát phân.
Ngoài ra dựa vào các phép toán logic cơ bản này ta có thể có một số ứng dụng khác như:
-viết hàm biểu diễn dưới dạng nhị phân mà không có số 0 thừa ở đầu
-Viết hàm đảo trật tự các bit trong 1 số ví dụ: 1011 (11) tahnhf 1101(13)
(Bài tiếp theo: Cách bật tắt các bit trong một số nguyên)

[hailoc12]

Tiếp tục:
5. Phép dịch trái (Shl): x Shl i cho gái trị nhận được từ số nguyên x sau khi dịch số đó qua trái i bit.
Quy tắc: Muốn nhân 1 số với 2 ta dịch số đó qua trái 1 bit. Tổng quát, muốn nhân một sốnguyene với 2^i ta dịch số đó qua trái i bit;
x Shl i= x*n; với n=2^i
Trong C không hỗ trợ phép toán này nhưng có thể dùng phép chia nguyên cho 2^i để thực hiện
Thí dụ

Chỉ để minh họa{   chả x, y;    x=19;//x=00010011//    y=x Shl 2;//y=01001100=x*4=76// }

6. Phép dịch phải
(Tương tự như phép dịch trái nhưng số nguyên sẽ được dịch sang phải i bit)

MỘT SỐ ỨNG DỤNG
*Ứng dụng 1(lấy bit). Viết hàm getbit(x,i) cho giá trị của bit thứ i(tính từ phải sang) của số nguyên x.

char Getbit(char x, i){   return (x Shr i) && 1;}

*Ứng dụng 2(lấy số) Viết hàm GetNum(x, j, i) cho số tạo bởi các bit tính từ trái qua phải là bit thứ j đến bit thứ i (j>=i). Thí dụ
GetNum(103,5,1)=19 vì 103=0000 0000 0110 0111
do dó GetNum(103,5,1)= 0000 0000 0001 0011 =19
Bài giải: Gọi số lượng bit của x là L(x) , trước hết ta phải hóa 0 các bit nằm ở bên trái bit thứ j. Muốn vậy ta dịch x qua trái k= L(x)-1-j bit. Sau đó ta chuyển giá trị thu được về cấu hình ban đầu tức là dịch phải k bit rồi tiếp tục dịch phải i bit để thu được số cần tìm. Hàm sizeof(x) cho ta số byte trong x. Nhân giá trị này với 8 ta sẽ được số bit trong x. Vì phép nhân 8 tương đuơng với phép dịch trái 3 bit nên sizeof(x) Shl 3 cho ta số bit trong x. Vì các bit được mã số từ phải sang trái bắt đầu từ bit 0 cho nên số hiệu cao nhất trong x sẽ là sizeof(x) Shl 3 -1

char Getnum(char x, j, i){   char k;         k= (sizeof(x) Shl 3)-1-j         return x Shl k Shr k Shr i;}

Đối với 2 hàm Getbit và GetNum ở trên ta sé có được một số ứng dụng như chuyển từ số tự nhiên sang biểu diễn nhị phân, thập lục phân, bát phân.
Ngoài ra dựa vào các phép toán logic cơ bản này ta có thể có một số ứng dụng khác như:
-viết hàm biểu diễn dưới dạng nhị phân mà không có số 0 thừa ở đầu
-Viết hàm đảo trật tự các bit trong 1 số ví dụ: 1011 (11) tahnhf 1101(13)
(Bài tiếp theo: Cách bật tắt các bit trong một số nguyên)

[hailoc12]

* Thủ tục Batbit(x,i) gán trị 1 cho bit thứ i trong byte x
Mô tả: Ta chuyển 1 đến vị trí i tương ứng sau đó thực hiện phép cộng logic với byte x

Ví dụ này chỉ mang tính minh họachar Batbit(char x, i)   {      return x OR(1 Shl i);   }

* Thu tục Tatbit(x, i) gán trị 0 cho bit thứ i trong byte
Mô tả: Ta chuyển 1 đến vị trí i tương ứng, sau đó đảo byte này để được byte có 0 ở vị trí i và 1 ở các bit còn lại, cuối cùng thực hiện phép nhân logic với byte x.

Ví dụ này chỉ mang tính minh họaChar Tatbit(char x, i)   {      return NOT(1 Shl i) And x;   }

(Bài tiếp theo: Ứng dụng các phép toán vào trò chơi NIM)

[bete]

Bạn hailoc12 đã có công viết 1 bài dài về thao tác bit => xin ủng hộ 100%

Xin được góp ý vô 1 chút. Về NOT, AND, OR, XOR thì C có 2 loại: thao tác logic và thao tác bit

Thao tác logic: giá trị bằng 0 được coi như là false (sai); giá trị khác 0 được coi như là true (đúng). Các toán tử là '!' (NOT), '&&' (AND), và '||' (OR) (không có toán tử XOR logic; nhưng có thể viết bằng NOT, AND, OR)

Thao tác bit: bit 0 được coi như là false (sai); bit 1 được coi như là true (đúng). Các toán tử là '~' (NOT), '&' (AND), '|' (OR) va` '^' (XOR)

Về phép dịch bit: các toán tử là '>>' (dịch qua phải) và '<<' (dịch qua trái) (tương ứng với phép dịch cho số không dấu trong hợp ngữ; C không có toán tử dịch qua phải có dấu)

Về bật / tắt / đảo bit:

X AND 0 -> 0; X AND 1 -> X: dùng để tắt bit
X OR 0 -> X; X OR 1 -> 1: dùng để bật bit
X XOR 0 -> X; X XOR 1 -> ~X: dùng để đảo bit

(có gì sai sót mong được góp ý, xin cám ơn)

-thân

[hailoc12]

Cám ơn bete lắm, cái này mình chuyên từ ngôn ngữ pascal sang nên chưa rõ lắm trong C nó viết thế nào cả.
Hôm nay mình xin post tiếp bài tiếp theo, là một áp dụng của các thao tác này vào một trò chơi.
* Trò chơi NIM: Có n đống sỏi, mỗi đống có một số viên sỏi. Hai người chơi luân phiên nhau đi như sau. Đến lượt người nào, người đó tùy chọn một đống sỏi để bốc số viên sỏi trong đống đã chọn và buộc phải bốc, ít nhất là 1 viên, nhiều nhất là cả đống. Ai bốc được những viên sỏi cuối cùng sẽ thắng. Lập chương trình tổ chức chơi giữa máy tính và người theo các yêu cầu sau:
- Số lượng sỏi lúc đầu được quy định trước
- Số lượng sỏi trong mỗi đống được sinh ngẫu nhiên
- Máy sẽ gieo xu để xác định máy hoặc người đi trước.
- Có thông báo kết quả mỗi ván.
Bài giải:
Có một lớp trò chơi 2 người thỏa mãn nguyên tắc sau:
Tồn tại một thế có tính chất T sao cho với mọi cách đi đều dẫn đến một thế không có tính chất T mà ta kí hiệu là NT = NOT (T) và từ NT luôn luôn tìm được một cách đi để dẫn đến một thế có tính chất T.
Nếu thế thắng chung cuộc có tính chất T thì ai gặp phải thế đó sẽ thua, do đó ta phải tìm mọi cách "nhường " thế có tính chất T cho đối phương.
Tính chất T nói trên được gọi là bất biến của trò chơi. Khi chung cuộc mọi
đống sỏi đều hết cho nên S=0.
Giả sử ta có n đống sỏi. Gọi ai là số sỏi trong đống thứ i; i=1..n
Ta lấy tổng loại trừ của các ai
S= a1 XOR a2 XOR .... XOR an.
Ta sẽ chứng minh rằng bất biến (tính chất T) của trò chơi NIM chính là S=0.
Ta sẽ sử dụng một số tính chất sau đây của phép XOR:
Tính chất 1: a XOR b =0 khi và chỉ khi a=b (suy từ định nghĩa).
Tính chất 2: a XOR b = b XOR a (tính giao hoán)
Tính chất 3: (a XOR b) XOR c = a XOR (b XOR c) (Tính kết hợp)
Tính chất 4: a XOR 0= a
Ta thừa nhận định lý sau:
Định lý: Nếu S<>0 thì tồn tại một ai thỏa mãn ai XOR S < ai
Ta minh họa định lý trên qua ví dụ sau. Giả sử n= 3 và
a1= 9= B1001
a2= 8= B1000
a3= 3= B0011
S= 2= B0010
Ta có a1 XOR S= 11>9 =a1
a2 XOR S= 10>8 = a2
a3 XOR S= 1< a3
Vậy a3 chính là số tìm được theo định lý trên
Nhận xét: Nếu S=0 và có ít nhất một đống sỏi với số sỏi khác 0 thì với mọi cách đi ta luôn luôn có tổng loai trừ của các đống sỏi là một số khác 0.
Thật vậy, không làm mất tính tổng quát ta giải sử rằng đống sỏi được chọn để bốc là a1. Giả sử rằng sau khi bốc đống a1 ta còn lại b1 viên sỏi. Có thế coi việc bốc sỏi là thay đống a1 bằng b1, vì a1 XOR a1= 0 nên tổng loài trừ thu được sau khi bốc sẽ là:
P= b1 XOR (a2 XOR...XOR an)
Nếu P = 0 thì
b1=(a2 Xor ... Xor an)=0 XOR (a2 Xor...Xor an)
= (a1 Xor a1) Xor (a2 Xor....Xor an)=
= a1 Xor (a1 Xor a2 Xor...Xor an)= a1 Xor S.
Vì S =0 nên b1 = a1 XOR 0= a1.
Điều này chứng tỏ không viên sỏi nào được bốc tại đống a1, trái với luật chơi. Vậy sau khi bốc ta phải có P<>0
hệ quả: Gọi S và P lần lượt là tổng loại trừ của các đống sỏi trước và sau một bước đi. Ta có, nếu S<>0 thì có một cách đi để P= 0;
Thật vậy, theo định lý trên ta tìm được một số ai để (ai XOR S)< ai. Đặt bi = ai- (ai XOR S). Ta bốc bi viên sỏi từ đống ai, đống này sẽ còn (ai XOR S) viên. Khi đó P = (ai XOR S) XOR (ai XOR S)=0 (đpcm).
Từ nhận xét và hệ quả nói trên ta suy ra S=0 chính là bất biến của trò chơi NIM.
Nước đi của đối thủ thông minh khi đó sẽ bao gồm hai bước sau:
Bước 1: Tính S= a1 XOR a2 XOR a3....XOR an
Bước 2: Nếu S <> 0: thực hiện các bước sau:
Bước 2a. Duyệt các đống sỏi để tìm đống ai thỏa điều kiện (ai XOR S)< ai
Bước 2b. Bốc ai - (ai XOR S) viên từ đống ai tìm được . Số sỏi còn lại của đống này sẽ là ( ai XOR S).
Nếu S=0: chọn đống lớn để bốc 1 viên cốt làm cho đối phương khó phát hiện nguy cơ thua của ta.
Như vậy thủ tục NIM - Trò chơi NIM với m đống sỏi gồm các bước sau
Bước 1: Kiểm tra giá trị hợp lệ của m
Bước 2: Khởi trị;
Bước 2a. Sinh ngẫu nhiên các giá trị ai>=1, i=1..n.
Bước 2b. Gieo xu để xác định ai đi trước, người hay máy
Bước 3. Chơi theo sô đồ sau
Repeat
If Ban then Bandi
Else Maydi;
Ban:= NOT Ban;
Xem;
Until Thua;
Bước 4: Thông báo kết quả thắng- thua giữa người và máy.
Trong đó thủ tục Maydi được triển khai theo sơ đồ đối thủ thông minh trình bày ở trên.
Trò chơi này nhìn chung đơn giản, dễ dàng cài đặt, nếu có thêm chút đồ họa vào là quá ngon lành. Chúc các bạn thấy vui vẻ với trò chơi này.


Như vậy đã được một tuần kể từ khi bắt đầu đề tài này, các kĩ thuật cơ bản em đều đã giới thiệu hết, Sau này nếu có điều kiện em sẽ giới thiệu tiếp về biểu thức logic bao gồm cách tạo hàm logic dựa trên các yêu cầu vào ra (giống như bài toán thiết kế mạch điện sao cho bật công tắc này thì những đèn này sáng....), cách biến đổi thành các biểu thức tương đương (cái này người ta gọi là suy luận, được áp dụng trong ngành trí tuệ nhân tạo) và tối ưu biểu thức logic nghĩa là làm sao cho biểu thức có ít nhất thành phần và tương đương với biểu thức ban đầu, áp dụng cho việc thiết kế mạch điện và tối ưu hóa trong lập trình.
Còn bây giờ nếu không bác nào còn ý kiến, em xin tạm dừng vấn đề này tại đây, tuấn sau ta sẽ đi vào vấn đề đồ thị cùng rất nhiều bài toán ứng dụng nó.

(Tuần tiếp: Vấn đề 3: Đồ thị và các bài toán ứng dụng )

[PoPoPoPo]

Rất cảm ơn các bài viết của Anh hailoc12.
em mới là thành viên của diễn đàn, và em rất yêu thích diễn đàn này.

Em có một chương trình chuyển một số hệ thập phân ra hệ nhị phân.

Hay nói tổng quát hơn là chương trình chuyển đổi một số hệ thập phân ra hệ cơ số k bất kì.

void Doicoso(int n,int b){    int s[10],o,j,i=0,k=0;    printf("\nNhap mot so he co so 10(Dec) n=");scanf("%d",&n);    printf("\nNhap co so can chuyen sang (b code): b=");scanf("%d",&b);    o=n;    while(n!=0)       {          k=n%b;n=n/b;          if(0<=k && k<=9) s[i++]= 48+k;          else           s[i++]=(65+k-10);        }//end while    printf("\n\nKet qua la:%d(dec) chuyen sang %d(code) la:",o,b);    for(j=i-1;j>=0;j--)    printf("%c",s[j]);}//end function

[cuongalone]

Theo mình biết thì trong C vẫn có phép XOR. kí hiệu trong C là Z=x^y

[dammelaptrinh]

Rất cảm ơn các bài viết của Anh hailoc12.
em mới là thành viên của diễn đàn, và em rất yêu thích diễn đàn này.

Em có một chương trình chuyển một số hệ thập phân ra hệ nhị phân.

Hay nói tổng quát hơn là chương trình chuyển đổi một số hệ thập phân ra hệ cơ số k bất kì.

void Doicoso(int n,int b){    int s[10],o,j,i=0,k=0;    printf("\nNhap mot so he co so 10(Dec) n=");scanf("%d",&n);    printf("\nNhap co so can chuyen sang (b code): b=");scanf("%d",&b);    o=n;    while(n!=0)       {          k=n%b;n=n/b;          if(0<=k && k<=9) s[i++]= 48+k;          else           s[i++]=(65+k-10);        }//end while    printf("\n\nKet qua la:%d(dec) chuyen sang %d(code) la:",o,b);    for(j=i-1;j>=0;j--)    printf("%c",s[j]);}//end function

anh ơi! anh giải thích thuật toán bài này cho em được không? em không hiểu lắm! 48 với 65 ở đâu ra vây?
nhất là chổ này

k=n%b;n=n/b;
	      if(0<=k && k<=9) s[i++]= 48+k;
	      else
	       s[i++]=(65+k-10);

[pkthanh92]

48 là mã ascii của 0, để chuyển số 1 thành ký tự '1' thì cộng 1 với 48