Sunday, 26 February 2012

Bit shifting

Ít khi nói tới vì ít khi dùng tới nếu không động tới phần thấp.
Ai cũng biết mọi dữ liệu đều được biểu diễn trên máy tính ở dạng nhị phân. Hôm nay ta chơi với 2 toán tử bitwise đó là 2 phép dịch bit - bit shifting  >> <<

Có 2 loại toán tử shift bit là arithmetic(số học???) shift và logical shift (lô gíc)
Phép arithmetic shift bảo toàn dấu sau khi shift , logical thì không.

Để mọi chuyện rõ ràng hơn. Ta xét về vấn đề dấu :

A. Cách biểu diễn số nguyên có dấu và không dấu
1. Với unsigned int : KHÔNG DẤU - chỉ toàn số dương.
1 byte = 8 bit và 8 bit này đều để biểu diện ĐỘ LỚN (trị tuyệt đối). Nghĩa là với 1 byte sẽ biểu diễn được các giá trị từ 0 - 255 (cái này làm bài tập mạng máy tính quen rồi nhể)

2. Khác với int : CÓ DẤU (+ - ) gồm cả số âm và số dương.
1 byte lúc này sẽ có 1 bit đầu tiên để biễn diễn dấu, 7 bit còn lại biểu diễn độ lớn. Vì thế, 1byte lúc này sẽ cho các giá trị từ -127 đến 127 (thiếu 1 số là do có 2 cách biểu diễn 0). Với 1 số cách cài đặt khác, ta có khoảng giá trị là -128 đến 127 (số -0 thay bằng 128). Xem thêm ở link dưới.
http://en.wikipedia.org/wiki/Signed_number_representations



Có thể xem bảng dưới:

Binary value Ones' complement Unsigned interpretation
00000000 +0 0
00000001 1 1
... ... ...
01111101 125 125
01111110 126 126
01111111 127 127
10000000 −127 128
10000001 −126 129
10000010 −125 130
... ... ...
11111101 −2 253
11111110 −1 254
11111111 −0 255

Ta thấy có 2 giá trị biểu diễn cho số 0 (+0 và - 0).

B. Phép dịch bit (bit shifting)
Cụ thể thế nào lại phụ thuộc vào ngôn ngữ bạn sử dụng (thậm chí phụ thuộc vào compiler...)
Với Java : phân biệt rõ ràng
 >> : dịch phải (arithmetic)
 >>>: dịch phải (logical)
 << : dịch trái (arithmetic)
 sao không có <<<: vì dịch trái thì không có khái niệm bảo toàn dấu, bit nào bị dịch ra ngoài vùng giá trị sẽ bị mất.

Với C/C++/C#: 
chỉ có << và >> và lại phụ thuộc vào compiler bạn dùng để quyết định nó là arithmetic hay logical. Vì thế, trường hợp sau có 2 khả năng:

char x = -1;
x >>= 1;
x giờ có thể là 127 (01111111) hoặc vẫn là -1 (11111111).
(với ANSI C, kết quả là -1 (chưa test))
 
1. Dịch trái <<
00000110
Đây là dạng bit của số 6. Giờ ta dịch sang trái 1 bit (6 << 1) , kết quả thu được là  12:
00001100
Phép dịch bit sang trái i bit tương ứng với việc nhân số đó với 2^i (tất nhiên là không vượt ra khỏi khoảng giá trị).


2. Dịch phải >>> (logical)
00001100  : 12
12 >> 1 thu được
00000110 : 6
phép dịch bit sang phải i bit tương ứng với việc chia số đó với 2^i.
http://en.wikipedia.org/wiki/Logical_shift


3. Dịch phải >> (arithmetic bảo toàn dấu)
11111111 : -1
-1 >> 1 thu được
11111111 : -1


Ai hỏi sao học cái này làm gì thì có vài câu trả lời :))
1. Tớ làm nén dữ liệu nên phải ghi ra file dạng binary.
2. Có thể tính toán khi nhân với 2^i nhanh hơn với phép dịch bit.
3. Dùng rất nhiều trong xử lý ảnh, lập trình các thiết bị bậc thấp, nhúng...
Sai gì thì các cao thủ bổ sung, đừng ném gạch. Em vừa học được có 30 phút :">