Bài giảng Kĩ thuật lập trình - Chương 21: Các kỹ thuật thao tác trên BIT - Đặng Bình Phương
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kĩ thuật lập trình - Chương 21: Các kỹ thuật thao tác trên BIT - Đặng Bình Phương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_ki_thuat_lap_trinh_chuong_21_cac_ky_thuat_thao_tac.ppt
Nội dung text: Bài giảng Kĩ thuật lập trình - Chương 21: Các kỹ thuật thao tác trên BIT - Đặng Bình Phương
- 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
- & 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 Các kỹ thuật thao tác trên bit 2
- & VC BB Đơn vị đo thông tin ❖Hai trạng thái tắt-0 và mở-1 (nhị phân). ❖Ký số nhị phân (Binary Digit) – bit ❖bit - Đơn vị chứa thông tin nhỏ nhất. ❖Cá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 Các kỹ thuật thao tác trên bit 3
- & 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 Các kỹ thuật thao tác trên bit 4
- & VC BB Biểu diễn thông tin trong MTĐT ❖Đặ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ự. ❖Hai 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) Các kỹ thuật thao tác trên bit 5
- & VC BB Biểu diễn số nguyên không dấu ❖Đặ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ẻ. Các kỹ thuật thao tác trên bit 6
- & VC BB Biểu diễn số nguyên có dấu ❖Đặ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. Các kỹ thuật thao tác trên bit 7
- & 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 Các kỹ thuật thao tác trên bit 8
- & VC BB Biểu diễn số nguyên có dấu ❖Nhậ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. Các kỹ thuật thao tác trên bit 9
- & VC BB Tính giá trị có dấu và không dấu ❖Tí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. 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 ❖Bả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 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 msb = FE 254 –2 FFFE 65534 –2 FF 255 –1 FFFF 65535 –1 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 ❖Nhậ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). ❖Tí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. Các kỹ thuật thao tác trên bit 12
- & VC BB Các toán tử trên bit ❖Toán tử & (and) & 0 1 0 0 0 1 0 1 ❖Ví 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 Các kỹ thuật thao tác trên bit 13
- & VC BB Các toán tử trên bit ❖Toán tử | (or) | 0 1 0 0 1 1 1 1 ❖Ví 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 Các kỹ thuật thao tác trên bit 14
- & VC BB Các toán tử trên bit ❖Toán tử ^ (xor) ^ 0 1 0 0 1 1 1 0 ❖Ví 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 Các kỹ thuật thao tác trên bit 15
- & VC BB Các toán tử trên bit ❖Toán tử ~ (not) ~ 0 1 1 0 ❖Ví 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 Các kỹ thuật thao tác trên bit 16
- & VC BB Các toán tử trên bit ❖Toá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. ❖Ví 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 Các kỹ thuật thao tác trên bit 17
- & VC BB Các toán tử trên bit ❖Toá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ố ❖Ví 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 Các kỹ thuật thao tác trên bit 18
- & VC BB Các toán tử trên bit ❖Lư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, ) Các kỹ thuật thao tác trên bit 19
- & VC BB Ứng dụng trên số nguyên ❖Ứ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) ❖Ứ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) Các kỹ thuật thao tác trên bit 20
- & 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); } Các kỹ thuật thao tác trên bit 21
- & 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)); } Các kỹ thuật thao tác trên bit 22
- & 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; } Các kỹ thuật thao tác trên bit 23
- & 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; } Các kỹ thuật thao tác trên bit 24
- & VC i BB Nhân n với 2 ❖Đặ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; } Các kỹ thuật thao tác trên bit 25
- & VC i BB Chia n với 2 ❖Đặ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; } Các kỹ thuật thao tác trên bit 26
- & VC BB Bài tập ❖Bài 1: Viết hàm thực hiện các thao tác trên bit. ❖Bài 2: Viết bitcount đếm số lượng bit 1 của một số nguyên dương n. ❖Bà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} ❖Bà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) Các kỹ thuật thao tác trên bit 27
- & VC BB Bài tập ❖Bà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 ❖Bài 6: Tương tự bài 2 nhưng viết hàm RotateRight(n, i) để xoay bit sang phải. Các kỹ thuật thao tác trên bit 28
- & 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 } Các kỹ thuật thao tác trên bit 29