Xử lý bit - Pascal

Steven_Luu · July 30, 2016, 7:40am

(Nguồn: http://ptthlamson.net/forums/showthread.php?t=8802)

Trong một số bài toán cần đánh dấu, ta thường phải dùng 1 biến logic, mất đi 1 byte bộ nhớ. Trong khi thực ra ta chỉ cần dùng 1 bit để ghi nhận trạng thái. Như vậy là ta đã lãng phí đi mất 7 bít còn lại. Có một cách để không bị lãng phí đi 7 bit kia là xử lí bit nghĩa là ta sẽ truy cập trực tiếp vào từng bit một của mỗi byte.

Ta xét bài toán sau đây:

Với 1 dãy số ta có 2 phép toán

Thêm số x vào dãy số

Đưa ra xem số x có xuất hiện trong dãy hay chưa. (1: có, 0: không)
Ban đầu dãy số rỗng.
Hãy thực hiện lần lượt 1 số phép toán trên dãy.

Input:

Dòng đầu là số m - số phép toán cần thực hiện. (m <= 100000)

m dòng sau mỗi dòng gồm 2 số nguyên k, x. k là loại phép toán, x là giá trị tương ứng (0 <= x <= 450000);

Output

Đưa ra kết quả tương ứng với phép toán 2.

Bài này m và x khá lớn. Nếu ta đánh dấu thông thường thì chỉ chạy được với x <= 65000. Nhưng nếu xử lý bit thì ta có thể chạy được hết dữ liệu. ^^
Cụ thể:
Ta có 1 mảng byte 60000 phần tử => có 480000 bit. Mỗi bit sẽ tương ứng với 1 số x.
Ban đầu khởi tạo mảng là 0 hết vì chưa có số nào xuất hiện.
Với 1 số x thì ta sẽ xác định vị trí của nó là bit thứ (x mod 8) của phần tử (x div 8).
(chú ý các bit trong máy tính đánh số từ 0)
Giờ khi thêm 1 số x vào dãy thì ta bật bit tương ứng của x lên.
Khi kiểm tra xem x có trong dãy hay không thì ta chỉ việc lấy giá trị của bit tương ứng với x.

Ta có 2 phép toán sau trên 1 số:

x shl k: dịch dãy bit của x sang trái k vị trí
x shr k: dịch dãy bit của x sang phải k vị trí

Thủ tục bật bit thứ k của 1 số a.

procedure BatBit(k: byte; var a: byte);
begin
a := a or (1 shl k);
end;

Hàm lấy bit thứ k của 1 số a.

function GetBit(k, a: byte): byte;
begin
GetBit := 1 and (a shr k);
end;

Như vậy là ta đã có thể giải quyết xong bài toán này.

Ngoài ra ta còn có thể tắt bit của số a:

procedure TatBit(k: byte; var a: byte);
begin
a := a and not (1 shl k);
end;

Đảo bit

procedure DaoBit(k: byte; var a: byte);
begin
a := a xor (1 shl k);
end;

Không chỉ có tác dụng giảm bộ nhớ. Việc xử lý bit còn có thể giúp ta cài đặt dễ dàng hơn trong 1 số bài toán cụ thể như khi cần ghi nhận trạng thái của 1 dãy 15 bóng đèn (sáng tắt) thì đó chính là 1 dãy 15 bit tương ứng với cách biểu diễn 1 số kiểu integer trong hệ nhị phân. Từ đó có thể dễ dàng đánh dấu trạng thái để giải quyết bài toán!