Xử lý bit!

[Mr. Pitô]

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
1. Thêm số x vào dãy số
2. Đư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!

P/s: Hôm nào rỗi sẽ đưa một số bài tập về xử lý bit cho các bạn luyện tập.

[congiun_vodanh]

Bác thiệt là cao thủ. Em đọc hổng có hiểu :-o :-o

[hotboyLS_BK]

Dạo này mới lên trên forum xem thế nào
Mình chợt có ý kiến rằng sao mọi ngừoi không tạo một topic về C++ nhỉ
thực ra thì ngôn ngữ nào thì thuật toán cũng như nhau nhưng mà bi giờ ParCan chỉ dùng để học là chủ yếu thhôi chứ còn úng dụng của nó thì không mạnh như C++ và Java
theo mình thì nên tạo một cái topic về C++:9:

[Mr. Pitô]

Em chẳng biết tí gì về C hay Java cả. Chưa có thời gian để học. Ở trường các thầy cũng chỉ dạy qua Pascal rồi nghiên cứu thuật toán là chủ yếu.
Anh hotboyLS_BK lập đi topic về C++ đi để bọn em mở mang thêm ^^. Hy vọng box tin sẽ ngày càng phát triển.

[NTX]

....

Một biến logic như BOOL trong bộ vi xử lý 32bit chiếm 4bytes

[Mr. Pitô]

Một biến logic như BOOL trong bộ vi xử lý 32bit chiếm 4bytes
Bao nhiêu bytes thì còn tuỳ thuộc vào ngôn ngữ lập trình chứ, biết đâu sau này bộ vi xử lý 64bit nó lại là 8 byte thì sao?
Quan trọng là ta biết cách sử dụng nó và áp dụng trong các bài toán cụ thể. Bộ nhớ hiện tại cũng không còn quan trọng lắm nhưng xử lý bit đâu nhất thiết là để tiết kiệm bộ nhớ. Luôn nhớ rằng phép toán với bit là phép toán thực hiện nhanh nhất. Việc chuyển các phép toán đơn giản trong chương trình thành một phép toán xử lý bit có thể đẩy tốc độ chương trình lên rất nhiều.
Vd:
1. x := x div (2^k) thì chuyển thành x := x shr k;
2. Hoán vị 2 số nguyên x và y
Thông thường là
z := x;
x := y;
y := z;
Chuyển thành xử lý bit
x := x xor y;
y := x xor y;
x := x xor y;

Ngoài ra phép xor còn dùng trong cả các bài toán trò chơi (Dùng Grundy).

[TChuTich]

Bao nhiêu bytes thì còn tuỳ thuộc vào ngôn ngữ lập trình chứ, biết đâu sau này bộ vi xử lý 64bit nó lại là 8 byte thì sao?
Quan trọng là ta biết cách sử dụng nó và áp dụng trong các bài toán cụ thể. Bộ nhớ hiện tại cũng không còn quan trọng lắm nhưng xử lý bit đâu nhất thiết là để tiết kiệm bộ nhớ. Luôn nhớ rằng phép toán với bit là phép toán thực hiện nhanh nhất. Việc chuyển các phép toán đơn giản trong chương trình thành một phép toán xử lý bit có thể đẩy tốc độ chương trình lên rất nhiều.
Vd:
1. x := x div (2^k) thì chuyển thành x := x shr k;
2. Hoán vị 2 số nguyên x và y
Thông thường là
z := x;
x := y;
y := z;
Chuyển thành xử lý bit
x := x xor y;
y := x xor y;
x := x xor y;

Ngoài ra phép xor còn dùng trong cả các bài toán trò chơi (Dùng Grundy).
Nhầm rồi em à, ko hẳn là tùy ngôn ngữ đâu.

[NTX]

Bao nhiêu bytes thì còn tuỳ thuộc vào ngôn ngữ lập trình chứ, biết đâu sau này bộ vi xử lý 64bit nó lại là 8 byte thì sao?
Quan trọng là ta biết cách sử dụng nó và áp dụng trong các bài toán cụ thể. Bộ nhớ hiện tại cũng không còn quan trọng lắm nhưng xử lý bit đâu nhất thiết là để tiết kiệm bộ nhớ. Luôn nhớ rằng phép toán với bit là phép toán thực hiện nhanh nhất. Việc chuyển các phép toán đơn giản trong chương trình thành một phép toán xử lý bit có thể đẩy tốc độ chương trình lên rất nhiều.
Vd:
1. x := x div (2^k) thì chuyển thành x := x shr k;
2. Hoán vị 2 số nguyên x và y
Thông thường là
z := x;
x := y;
y := z;
Chuyển thành xử lý bit
x := x xor y;
y := x xor y;
x := x xor y;

Ngoài ra phép xor còn dùng trong cả các bài toán trò chơi (Dùng Grundy).
Không phải đâu bạn ơi, cái này tùy thuộc hệ thống đang sử dụng
Ở đây tôi chỉ bàn đên WinXP
Kích thước giá trị logic bằng kích thước thanh ghi (tính theo bit)
Ngôn ngữ nào cũng vậy thôi pascal, delphi, C/C++...nếu gặp một hàm API trả về giá trị boolean hay giá trị nào đó thường thì là nằm ở thanh ghi EAX hay ở stack (bằng cách push vào stack)
Trường hợp nào cũng 32bit thôi, nói một cách đơn giản nếu pascal qui định boolean là 1 byte gặp một hàm API cũng trả về boolean những 4bytes (32bits) thì...Cái này còn phụ thuôc Intel, AMD...

[Mr. Pitô]

^^ mấy cái đó em cũng không rõ lắm. Thanks các anh. Kiến thức phổ thông hạn hẹp quá :(

[tomatoblack]

Anh có thể cho 1 vài bài tập cơ bản về phần Xử Lý Bit không ạ???

[tomatoblack]

Anh cho 1 số bài tập +phần giải bài này với ạ!:10:10

[NTX]

Mình chẳng còn giữ tài liệu nào cả, mình biết đến chúng qua asm từ thời 16bits khi mà bộ nhớ còn hạn hẹp.
Tôt nhất là bạn nên hỏi nếu vướng mắc, mình hoặc ai đó nếu biết sẽ trả lời bạn

[Ktun]

Bài 1. Biến đổi
Cho một dãy a = 010111011.. (dãy các bit 0, 1 có độ dài 64). Có n điều khiển c1, c2,…, cn. Trong đó ci i cũng là một dãy các bit 0,1 có độ dài 64. Ta định nghĩa: tác động điều khiển ci lên a chính là thay đổi trạng thái (0 thành 1, 1 thành 0) các bit tương ứng với bit ci bằng 1.
Ví dụ: a = 010111011, c1 = 011001010, c2 = 000000001.
Tác động c1 vào a, khi đó a = 001110001.
Tác động c2 vào a, khi đó a = 001110000.
Yêu cầu: Hãy tìm một số ít nhất cách tác động để đưa trạng thái a về trạng thái b.

Input: Nhập vào từ file BIENDOI.INP:
- Dòng đầu tiên chứa số N. N<30.
- N dòng tiếp theo mỗi dòng chứa điều khiển ci.
- Dòng N+1 chứa dãy a.
- Dòng N+2 chứa dãy b.
- a, b, c là các dãy gồm 64 bit.

Output: Ghi ra file BIENDOI.OUT:
- Dòng đầu tiên ghi số k là số cách tác động ít nhất để chuyển a về b.
- Dòng tiếp theo ghi k số lần lượt là số hiệu của các điều khiển ci đã được sử dụng.

Bài 2. Bắn bi
Chúng ta hãy xem xét trò chơi bắn bi như sau: Trên bảng gồm M hàng và N cột, các hàng đánh số từ 1 theo chiều từ trên xuống, các cột từ trái sang phải. Trên đó có một số chướng ngại vật, chướng ngại vật ở một trong hai trạng thái 1 và 2. Đích là một vị trí bên ngoài phía phải của bảng tại hàng h, tức là kề phía phải của ô (h,N). Trò chơi bắn bi diễn ra như sau: một người bắn bi từ một ô tuỳ ý ở cột 1, theo chiều ngang. Bi cứ di chuyển cho đến khi ra ngoài bảng, nếu trên đường gặp chướng ngại vật thì tuỳ từng trạng thái chướng ngại vật:
- Nếu chướng ngại vật ở trạng thái 1: Bi rẽ trái và chướng ngại vật chuyển sang trạng thái 2, ngược lại, bi rẽ phải và chướng ngại vật chuyển sang trạng thái 1.
- Nếu bi lăn đến vị trí đích thì trò chơi kết thúc, ngược lại nếu ra ngoài bảng mà không đến đích thì phải tiếp tục lần chơi mới.
Yêu cầu: Hãy chỉ ra các bước bắn bi sao cho sau số ít nhất lần bắn thì trò chơi kết thúc.

Dữ liệu: Vào từ file MARBLES.INP:
- Dòng đầu ghi hai số nguyên dương m, n, h (m,n <= 100; 1 <= h <= m)
- Dòng thứ hai ghi k là số các ô có chướng ngại vật (1 <= k <= 15)
- K dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương u,v,s cho biết ô u,v có chướng ngại vật ban đầu ở trạng thái s.

Kết quả: Ghi ra file MARBLES.OUT:
- Dòng đầu ghi P là số bước bắn tối thiểu.
- P dòng tiếp theo, mỗi dòng ghi một số thể hiện các nước bắn lần lượt từ nước 1 cho đến nước cuối cùng, gồm một số nguyên dương u thể hiện bắt đầu bắn từ ô (u,1).

[Ktun]

Ngoài ra, các bạn có thể tham khảo thêm về lí thuyết xử lí bit và bài tập tại đây:
http://www.diendantinhoc.com/index.php?showtopic=13414&pid=49063&mode=threaded&start=#entry49063