Kỹ thuật lập trình - Các kỹ thuật thao tác trên bit

Nội dung text: Kỹ thuật lập trình - Các kỹ thuật thao tác trên bit

1. Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Khoa học Tự nhiên KỸ THUẬT LẬP TRÌNH ThS. Đặng Bình Phương dbphuong@fit.hcmus.edu.vn CÁC KỸ THUẬT THAO TÁC TRÊN BIT 1
2. & VC BB Nội dung 1 Các toán tử logic 2 Các toán tử dịch bit 3 Các ứng dụng 4 Bài tập 2 Các kỹ thuật thao tác trên bit
3. & VC BB Đơn vị đo thông tin vHai trạng thái tắt-0 và mở-1 (nhị phân). vKý số nhị phân (Binary Digit) – bit vbit - Đơn vị chứa thông tin nhỏ nhất. vCác đơn vị đo thông tin lớn hơn: Tên gọi Ký hiệu Giá trị Byte B 8 bit KiloByte KB 210 B = 1024 Byte MegaByte MB 210 KB = 220 Byte GigaByte GB 210 MB = 230 Byte TeraByte TB 210 GB = 240 Byte PentaByte PB 210 TB = 250 Byte 3 Các kỹ thuật thao tác trên bit
4. & VC BB Đơn vị đo thông tin 0 1 bit 2 1 0 2 bit 22 2 1 0 3 bit 23 n-1 5 4 3 2 1 0 n bit 2n 0 000 1 111 = 2n – 1 4 Các kỹ thuật thao tác trên bit
5. & VC BB Biểu diễn thông tin trong MTĐT vĐặc điểm § Được lưu trong các thanh ghi hoặc trong các ô nhớ. Thanh ghi hoặc ô nhớ có kích thước 1 byte (8 bit) hoặc 1 word (16 bit). § Biểu diễn số nguyên không dấu, số nguyên có dấu, số thực và ký tự. vHai loại bit đặc biệt § msb (most significant bit): bit nặng nhất (bit n) § lsb (least significant bit): bit nhẹ nhất (bit 0) 5 Các kỹ thuật thao tác trên bit
6. & VC BB Biểu diễn số nguyên không dấu vĐặc điểm § Biểu diễn các đại lương luôn dương. § Ví dụ: chiều cao, cân nặng, mã ASCII § Tất cả bit được sử dụng để biểu diễn giá trị. § Số nguyên không dấu 1 byte lớn nhất là 8 1111 11112 = 2 – 1 = 25510. § Số nguyên không dấu 1 word lớn nhất là 16 1111 1111 1111 11112 = 2 – 1 = 6553510. § Tùy nhu cầu có thể sử dụng số 2, 3 word. § lsb = 1 thì số đó là số đó là số lẻ. 6 Các kỹ thuật thao tác trên bit
7. & VC BB Biểu diễn số nguyên có dấu vĐặc điểm § Lưu các số dương hoặc âm. § Bit msb dùng để biểu diễn dấu • msb = 0 biểu diễn số dương. VD: 0101 0011 • msb = 1 biểu diễn số âm. VD: 1101 0011 § Trong máy tính, số âm được biểu diễn ở dạng số bù 2. 7 Các kỹ thuật thao tác trên bit
8. & VC BB Số bù 1 và số bù 2 Số 5 (byte) 0 0 0 0 0 1 0 1 Số bù 1 của 5 1 1 1 1 1 0 1 0 + 1 Số bù 2 của 5 1 1 1 1 1 0 1 1 + Số 5 0 0 0 0 0 1 0 1 Kết quả 1 0 0 0 0 0 0 0 0 8 Các kỹ thuật thao tác trên bit
9. & VC BB Biểu diễn số nguyên có dấu vNhận xét § Số bù 2 của x cộng với x là một dãy toàn bit 0 (không tính bit 1 cao nhất do vượt quá phạm vi lưu trữ). Do đó số bù 2 của x chính là giá trị âm của x hay – x. § Đổi số thập phân âm –5 sang nhị phân? Đổi 5 sang nhị phân rồi lấy số bù 2 của nó. § Thực hiện phép toán a – b? a – b = a + (–b) => Cộng với số bù 2 của b. 9 Các kỹ thuật thao tác trên bit
10. & VC BB Tính giá trị có dấu và không dấu vTính giá trị không dấu và có dấu của 1 số? § Ví dụ số word (16 bit): 1100 1100 1111 0000 § Số nguyên không dấu ? • Tất cả 16 bit lưu giá trị. => giá trị là 52464. § Số nguyên có dấu ? • Bit msb = 1 do đó số này là số âm. => độ lớn là giá trị của số bù 2. • Số bù 2 = 0011 0011 0001 0000 = 13072. => giá trị là –13072. 10 Các kỹ thuật thao tác trên bit
11. & VC BB Tính giá trị có dấu và không dấu vBảng giá trị số không dấu/có dấu (byte & word) HEX Không dấu Có dấu HEX Không dấu Có dấu 00 0 0 0000 0 0 01 1 1 0001 1 1 0 02 2 2 0002 2 2 msb = 7E 126 126 7FFE 32766 32766 7F 127 127 7FFF 32767 32767 80 128 –128 8000 32768 –32768 1 81 129 –127 8001 32769 –32767 msb = FE 254 –2 FFFE 65534 –2 FF 255 –1 FFFF 65535 –1 11 Các kỹ thuật thao tác trên bit
12. & VC BB Tính giá trị có dấu và không dấu vNhận xét § msb=0 giá trị có dấu bằng giá trị không dấu. § msb=1 thì giá trị có dấu bằng giá trị không dấu trừ 28=256 (byte) hay 216=65536 (word). vTính giá trị không dấu và có dấu của 1 số? § Ví dụ số word (16 bit): 1100 1100 1111 0000 § Giá trị không dấu là 52464. § Giá trị có dấu: vì bit msb = 1 nên giá trị có dấu bằng 52464 – 65536 = –13072. 12 Các kỹ thuật thao tác trên bit
13. & VC BB Các toán tử trên bit vToán tử & (and) & 0 1 0 0 0 1 0 1 vVí dụ § int x = 2912, y = 1706, z = x & y; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 & 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 544 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 13 Các kỹ thuật thao tác trên bit
14. & VC BB Các toán tử trên bit vToán tử | (or) | 0 1 0 0 1 1 1 1 vVí dụ § int x = 2912, y = 1706, z = x | y; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 | 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 4074 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 14 Các kỹ thuật thao tác trên bit
15. & VC BB Các toán tử trên bit vToán tử ^ (xor) ^ 0 1 0 0 1 1 1 0 vVí dụ § int x = 2912, y = 1706, z = x ^ y; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 ^ 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 3530 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 15 Các kỹ thuật thao tác trên bit
16. & VC BB Các toán tử trên bit vToán tử ~ (not) ~ 0 1 1 0 vVí dụ § int x = 2912, z = ~x; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ~ 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 -2913 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 16 Các kỹ thuật thao tác trên bit
17. & VC BB Các toán tử trên bit vToán tử << n (shift left) § Dịch các bit sang trái n vị trí. § Các bit vượt quá phạm vi lưu trữ sẽ mất. § Tự động thêm bit 0 vào cuối dãy bit. vVí dụ § int x = 2912, z = x << 2; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 116485824 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 17 Các kỹ thuật thao tác trên bit
18. & VC BB Các toán tử trên bit vToán tử >> n (shift right) § Dịch các bit sang phải n vị trí. § Các bit vượt quá phạm vi lưu trữ sẽ mất. § Giữ lại bit nặng nhất (msb)  dấu của số vVí dụ § int x = 2912, z = x >> 2; 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1456728 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 msb 0 18 Các kỹ thuật thao tác trên bit
19. & VC BB Các toán tử trên bit vLưu ý § Không được nhầm lần các các toán tử trên bit (&, |, ~) với các toán tử kết hợp (&&, || , !) § Các toán tử gộp: &= |= ^= >= § Máy tính làm việc trên bit nên các thao tác trên hệ nhị phân sẽ nhanh hơn rất nhiều so với hệ khác. § Phải luôn nhớ độ dài của dãy bit đang làm việc (8bit, 16bit, 32bit, 64bit, ) 19 Các kỹ thuật thao tác trên bit
20. & VC BB Ứng dụng trên số nguyên vỨng dụng của các toán tử &, |, ^, ~ a. Bật bit thứ i của biến n (onbit) b. Tắt bit thứ i của biến n (offbit) c. Lấy giá trị của bit thứ i của biến n (getbit) d. Gán giá trị 0 cho biến n (setzero) vỨng dụng của các toán tử dịch bit > e. Nhân n với 2i (mul2pow) f. Chia n với 2i (div2pow) 20 Các kỹ thuật thao tác trên bit
21. & VC BB Bật bit thứ i của biến n i = 9 ni | 0 = ni ni | 1 = 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 n n15 n14 n13 n12 n11 n10 n9 n8 n7 n6 n5 n4 n3 n2 n1 n0 | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 n15 n14 n13 n12 n11 n10 1 n8 n7 n6 n5 n4 n3 n2 n1 n0 void onbit(int &n, int i) { n = n | (0x1 << i); } 21 Các kỹ thuật thao tác trên bit
22. & VC BB Tắt bit thứ i của biến n i = 9 ni & 1 = ni ni & 0 = 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 n n15 n14 n13 n12 n11 n10 n9 n8 n7 n6 n5 n4 n3 n2 n1 n0 & 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 n15 n14 n13 n12 n11 n10 0 n8 n7 n6 n5 n4 n3 n2 n1 n0 void offbit(int &n, int i) { n = n & (~(0x1 << i)); } 22 Các kỹ thuật thao tác trên bit
23. & VC BB Lấy giá trị bit thứ i của biến n i = 9 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 n n015 n014 n013 n012 n011 n010 n09 n08 n07 n6 n5 n4 n3 n2 n1 n0 & 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n9 int getbit(int n, int i) { return (n >> i) & 0x1; } 23 Các kỹ thuật thao tác trên bit
24. & VC BB Gán giá trị 0 cho biến n ni ^ ni = 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 n n15 n14 n13 n12 n11 n10 n9 n8 n7 n6 n5 n4 n3 n2 n1 n0 ^ n15 n14 n13 n12 n11 n10 n9 n8 n7 n6 n5 n4 n3 n2 n1 n0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 void setzero(int &n) { n = n ^ n; } 24 Các kỹ thuật thao tác trên bit
25. & VC i BB Nhân n với 2 vĐặc điểm toán tử << j § n = ∑(nj2 ) với j [0, k] (k là chỉ số bit msb) § Dịch trái i bit số mũ mỗi ký số tăng thêm i j+i i j i § n << i = ∑(nj2 ) = 2 ∑(nj2 ) = 2 n § Vậy, dịch trái i bit  nhân với 2i int mul2powi(int n, int i) { return n << i; } 25 Các kỹ thuật thao tác trên bit
26. & VC i BB Chia n với 2 vĐặc điểm toán tử >> j § n = ∑(nj2 ) với j [0, k] (k là chỉ số bit msb) § Dịch phải i bit số mũ mỗi ký số giảm đi i j–i –i j –i i § n > i; } 26 Các kỹ thuật thao tác trên bit
27. & VC BB Bài tập vBài 1: Viết hàm thực hiện các thao tác trên bit. vBài 2: Viết bitcount đếm số lượng bit 1 của một số nguyên dương n. vBài 3: Cho mảng a gồm n số nguyên khác nhau. Viết hàm liệt kê các tổ hợp 1, 2, , n phần tử của số nguyên đó (không cần theo thứ tự) Ví dụ, n = 3, mảng a = {1, 2, 3} {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} vBài 4: Giống bài 3 nhưng chỉ liệt kê các tổ hợp k phần tử (1 ≤ k ≤ n) 27 Các kỹ thuật thao tác trên bit
28. & VC BB Bài tập vBài 5: Viết hàm RotateLeft(n, i) thực hiện thao tác “xoay” các bit của n (kô dấu) sang trái i vị trí và các bit bị mất sẽ được đưa vào cuối dãy bit. Ví dụ: § int n = 291282; n = RotateLeft(n, 2); 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ??? 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 vBài 6: Tương tự bài 2 nhưng viết hàm RotateRight(n, i) để xoay bit sang phải. 28 Các kỹ thuật thao tác trên bit
29. & VC BB Bài 3 a b c 0 0 0 0 { } 1 0 0 1 { c } 2 0 1 0 { b } 3 0 1 1 { b c } 4 1 0 0 { a } 5 1 0 1 { a c } 6 1 1 0 { a b } 7 1 1 1 { a b c } 29 Các kỹ thuật thao tác trên bit