Kỹ thuật xử lý BIT

Mọi số tự nhiên đều có thể biểu diễn được dưới dạng nhị phân. Đối với máy tính, các giá trị số được lưu bởi các biến dưới dạng chuỗi nhị phân có độ dài tương ứng với kiểu biến đó.
    Trong ngôn ngữ Pascal, một số kiểu phổ biến như:
        –    byte : độ dài 8 BIT
        –    integer : độ dài 2*8 = 16 BIT
        –    longint : độ dài 4*8 = 32 BIT
    Các BIT của biến được đánh số từ phải sang trái bắt đầu từ 1.

    Ưu điểm của xử lý BIT:

    1/ Bộ nhớ: Xử lý BIT có thể được dùng làm mảng đánh dấu. Thay vì sử dụng 1 biến Boolean chỉ đánh dấu được 1 phần tử là True hay False, ta có thể xử lý BIT để đánh dấu 8 BIT tương ứng với 8 phần tử.

    2/ Tốc độ: Các phép xử lý BIT có tốc độ nhanh hơn các phép xử lý khác. Ví dụ: Hai phép (x div 2) và (x shr 1) là như nhau nhưng phép (x shr 1) có tốc độ nhanh hơn. Trong các bài toán đòi hỏi việc thay đổi trạng thái nhiều lần thì người ta vẫn hay dùng xử lý BIT để cải thiện tốc độ chương trình.

    Sau đây là một số phép xử lý BIT cơ bản:

    1/ Cộng BIT (or):
    Kết quả bằng tổng giá trị 2 BIT. Trường hợp 2 BIT đều có giá trị bằng 1 thì kết quả là 1.
    Ví dụ:
        x1       = 9  (00001001)
        x2       = 18 (00010010)
        x1 or x2 = 27 (00011011)

    2/ Đảo BIT (not):
    Đảo BIT 0 thành BIT 1 và BIT 1 thành BIT 0.
    Ví dụ:
        x1       = 13  (00001101)
        not (x1) = 242 (11110010)

    3/ Nhân BIT (and):
    Kết quả bằng tích giá trị 2 BIT.
    Ví dụ:
        x1        = 9  (00001001)
        x2        = 12 (00001100)
        x1 and x2 = 8  (00001000)

    4/ Loại trừ BIT (xor):
    Kết quả là 0 nếu 2 BIT có cùng giá trị, là 1 nếu 2 BIT khác giá trị.
    Ví dụ:
        x1        = 9  (00001001)
        x2        = 18 (00010010)
        x1 xor x2 = 27 (00011011)

    5/ Dịch sang trái k BIT (shl):
    Ví dụ:
        x       = 27  (00001101)
        x shl 2 = 108 (01101100)

    6/ Dịch sang phải k BIT (shr):
    Ví dụ:        x       = 27 (00001101)
        x shr 2 = 6  (00000110)

    Từ các phép toán trên, ta có các công thức mở rộng sau:

    7/ Lấy giá trị BIT:
    Cho biết BIT thứ k của số x có giá trị bao nhiêu:

        Function GetBIT(k , x : LongInt) : LongInt;
        begin
          GetBIT := (x shr (k-1)) and 1;
        end;

    8/ Gán giá trị BIT:
    Gán giá trị c cho BIT thứ k của số x:

        Procedure SetBIT(c , k : LongInt; var x : LongInt);
        begin
          if c = 1 then x := x or (1 shl (k-1))
          else x := x and (not (1 shl (k-1)));
        end;