Hướng dẫn dùng bitshifting trong PHP

Í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 valueOnes' complementUnsigned interpretation00000000+000000000111.........01111101125125011111101261260111111112712710000000−12712810000001−12612910000010−125130.........11111101−225311111110−125411111111−0255
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 :">

cvht

19-09-2013, 08:05 PM

p/s:
ai có thể cho mình tham khảo đoạn code để swap byte n với byte m trong 1 biến 32 bit không? (cách của mình cùi quá)
mình tin chắc chắn là chỉ cần 1 dòng code sử dụng & ^ | thôi nhưng không nghĩ ra

Sử dụng tính chất b2 = b1 ^ (b1 ^ b2), b1 = b2 ^ (b1 ^ b2). Tính chất này cũng đã được sử dụng để đổi giá trị hai biến không dùng biến trung gian.



uint32_t x;

/* Đổi byte thứ nhất và byte thứ 3 của x. */
uint32_t tmp = ((x >> 8) ^ (x >> 24)) & 0xff; // lấy xor byte thứ nhất và byte thứ 3 của x
x ^= ((tmp << 8) | (tmp << 24)); // dùng tính chất ở trên để đổi giá trị của hai bytes này


Và đây là một dòng code để đổi byte 1 và byte 3 của x.


x ^= ((x ^= (((x ^= ((x & 0xff00) << 16)) >> 16) & 0xff00)) & 0xff00) << 16;


Đoạn code trên sẽ gây ra undefined behavior, do x bị thay đổi nhiều hơn 1 lần trong một câu lệnh (sequence points: http://diendan.congdongcviet.com/showthread.php?p=628671#post628671). Có thể viết lại (vẫn 1 dòng, nhưng "cheating" một chút vì dùng comma operator)


x ^= (x & 0xff00) << 16, x ^= x >> 16 & 0xff00, x ^= (x & 0xff00) << 16;

quano1

20-09-2013, 11:24 AM

nhìn ảo quá
lúc này sẽ là:


x = x ^ ((x & 0xff00) << 16); //bit3 = bit 3 ^ bit 1
x = x ^ ((x >> 16) & 0xff00); //bit 1 = bit 1 ^ bit 3 <=> bit 1 ^ (bit 3 ^ bit 1) = bit 3
x = x ^ (x & 0xff00) << 16; //bit 3 = bit 3 ^ bit 1 <=> (bit 3 ^ bit1) ^ bit 3 = bit 1

vậy khi swap 2 biến mà không dùng biến tạm thì quá trình sẽ như sau:


x1 = x1 ^ x2;
x2 = x2 ^ x1;
x1 = x1 ^ x2;

cách này hay vậy mà trong lúc học ở trường không ai giới thiệu cho mình cả :|

hehe và đây là đoạn code để swap (thank cvht)

unsigned int byteSwap(unsigned int src, unsigned int des, unsigned int x) {
if(sizeof(x) <= src || sizeof(x) <= des) {
return 0;
}
int spos = src < des ? src : des;
int dpos = src == spos ? des : src;
x = x ^ ((x & 0xff<<(spos * BITPERBYTE)) << (dpos-spos)*BITPERBYTE);
x = x ^ ((x >> (dpos-spos)*BITPERBYTE) & 0xff<<(spos*BITPERBYTE));
x = x ^ (x & 0xff<<(spos*BITPERBYTE)) << (dpos-spos)*BITPERBYTE;
return x;
}

quano1

20-09-2013, 12:33 PM

mình có 1 câu hỏi nữa. định lập topic mới nhưng do nó cũng liên quan chặt chẽ đến kỹ thuật sử dụng bit nên mình post luôn ở đây. hy vọng không vấn đề gì

đề bài là: "tìm string trong string mà bắt đầu startString và kết thúc = endString"

ví dụ:
startString = "start", endString = "end";
=> string: "hahaha start day la string se in ra end het mat roi"
kết quả: "day la string se in ra"

mình thấy nếu dùng string lib như string.find thì đơn giản rồi
tuy nhiên mình muốn hỏi là có cách nào mà sử dụng các phép toán với bit để tìm ra đoạn string đó không?

@prog: có vẻ bạn (anh) đúng. hồi trước khi mình làm đồ án, post hỏi nhiều người cách thiết kế class, mà bài toán là có đến hàng triệu, thậm trí hàng tỉ Object, mà mỗi object có thể là 1 thread.
thì có 1 người vn du học bên Sing, khuyên mình là nên làm theo DOD (data oriented design) bài toán sẽ được xử lý đơn giản và hiểu quả hơn nhiều.
thấy nhiều người cũng lên án OOP lắm. thậm trí còn trích dẫn cả 1 câu nói gì đó của Dijsktra cũng "mắng" OOP thậm tệ.