Hệ đếm nhị phân - Xử lý bit

Hệ đếm nhị phân - Xử lý bit.
Con người thường xử lý những bài toán bằng hệ đếm thập phân, nhưng có lẽ hệ đếm nhị phân lại là hệ đếm được ưa thích hơn với những chiếc máy tính. Trong PC của bạn, các con số được thể hiện bằng các bit dưới dạng nhị phân (0,1). Khi chúng ta nhập các con số duới dạng thập phân, máy sẽ xẽ xử lý và đưa về hệ nhị phân dưới dạng các bit mà chúng ta có thể tạm hiểu là 0 và 1. Và chỉ tới khi xuất dữ liệu ra (màn hình hoặc tệp văn bản), các số mới được thể hiện lại ở dạng thập phân. Mọi tệp trong máy thực chất là dòng các byte, trong đó có những byte giữ vị trí đặc biệt dùng để điều khiển việc hiển thị.
Một số người có thể đã hiểu ít nhiều về bit và các bài toán xử lý bit, một số người thì không. Nhưng điều đó không phải là quan trọng, khi mà điều quan trọng là chúng ta sẽ đề cập đến một vấn đề tưởng chừng như rất phức tạp (đối với những người chưa biết nhiều về nó), nhưng thật ra lại thật là đơn giản mà hiệu quả lại rất cao trong khi xử lý những bài toán hay và khó. Sau đây là những thông tin sơ lược về bit trong PC.
- Trong PC, mỗi số nguyên đều được biểu diễn ở hệ nhị phân bởi một dãy các bit 0 và 1.
- Các bit được mã số với những số hiệu từ phải sang trái.
7 6 5 4 3 2 1 0
- 1byte=8bit
- 1word=16bit
- Hàm sizeof (x) = số byte của số nguyên x.
- Các phép toán xử lý bit:
+ NOT x : phép đảo bit, đổi các giá trị trong mỗi bit của x từ 0->1,1->0.
+ x OR y : Phép cộng logic trên các bit.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.
X
Y
x or y

1
1
1

1
0
1

0
1
1

0
0
0

+ x AND y : Phép nhân logic trên các bit. 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.
X
Y
x and y

1
1
1

1
0
0

0
1
0

0
0
0

 
+ x XOR y : Phép cộng logic trên các bit.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.
X
Y
x xor y

1
1
0

1
0
1

0
1
1

0
0
0

 
+ x SHR i : Phép dịch phải, cho giá trị có được từ số nguyên x sau khi dịch sang phải i bit.
+ x SHL i : Phép dịch trái, cho giá trị có được từ số nguyên x sau khi dịch sang trái i bit.
Trên đây là một số phép toán làm việc trên các bit mà ta hay dùng, trên cơ sở đó, ta xây dựng được một số hàm, thủ tục hay dùng sau.
- Hàm lấy bit.
Function LayBit(x:word; i:byte):byte; Begin   LayBit:=(x SHR i) and 1 End;
Hàm trả về giá trị là bit thứ i của số nguyên x.
- Thủ tục bật bit.
Procedure BatBit(Var x:word; i:byte); Begin   X:=x OR (1 SHL i) End;
Thủ tục gán trị 1 cho bit thứ i trong số nguyên x.
- Thủ tục tắt bit.
Procedure TatBit(Var x:word; i:byte); Begin   X:=x AND (NOT(1 SHL i)) End;
Thủ tục gán trị 0 cho bit thứ i trong số nguyên x.
- Hàm Lấy số.
Function LaySo(x:word;j,i:byte):byte; Var K:byte; Begin   K:= (8*sizeof(x) - j - 1);   LaySo := (x SHL k) SHR (i+k) End;
Hàm trả về giá trị là số tạo bởi các bit từ trái sang phải, từ j -> i của số x với điều kiện 8*sizeof(x)> j >= i >= 0.
Tiếp đến, chúng ta sẽ giải quyết một số bài toán khá hay về xử lý bit.
Bài toán: Sắp xếp dãy.
Cho tệp Data.dat gồm các số nguyên không âm nhỏ hơn 500 000 đôi một khác nhau. Hãy xắp tệp theo thứ tự tăng dần và đưa ra tệp Result.dat.
Bài toán trên khiến ta cảm thấy khó chịu về giới hạn dữ liệu của nó, nếu ta nghĩ đến việc