NMLT_C21_CacKyThuatThaoTacTrenBIT_#REF

NHẬP MÔN LẬP TRÌNH
CÁC KỸ THUẬT
THAO TÁC TRÊN BIT
Nội dung
Các kỹ thuật thao tác trên bit
Đơn vị đo thông tin
Các kỹ thuật thao tác trên bit
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:
Đơn vị đo thông tin
Các kỹ thuật thao tác trên bit
1 bit
2 bit
3 bit
n bit
…
0
0
1
0
1
2
0
1
3
4
5
n-1
2
2
22
23
2n
0…000  1…111 = 2n – 1
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
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à 1111 11112 = 28 – 1 = 25510.
Số nguyên không dấu 1 word lớn nhất là
1111 1111 1111 11112 = 216 – 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
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
Số bù 1 và số bù 2
Các kỹ thuật thao tác trên bit
0
0
0
0
0
1
0
1
Số 5 (byte)
1
1
1
1
1
0
1
0
Số bù 1 của 5
1
1
1
1
1
0
1
1
Số bù 2 của 5
1
+
0
0
0
0
0
1
0
1
+ Số 5
0
0
0
0
0
0
0
0
1
Kết quả
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
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
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)
Các kỹ thuật thao tác trên bit
msb = 0
msb = 1
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
Các toán tử trên bit
Toán tử & (and)


Ví dụ
int x = 2912, y = 1706, z = x & y;
Các kỹ thuật thao tác trên bit
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
&
1
1
1
1
1
1
544
Các toán tử trên bit
Toán tử | (or)


Ví dụ
int x = 2912, y = 1706, z = x | y;
Các kỹ thuật thao tác trên bit
1
1
1
0
1
0
1
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
|
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4074
Các toán tử trên bit
Toán tử ^ (xor)


Ví dụ
int x = 2912, y = 1706, z = x ^ y;
Các kỹ thuật thao tác trên bit
1
1
0
0
1
0
1
0
0
0
0
0
1
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
^
0
1
1
0
0
1
1
0
0
1
1
0
0
1
3530
Các toán tử trên bit
Toán tử ~ (not)


Ví dụ
int x = 2912, z = ~x;
Các kỹ thuật thao tác trên bit
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
1
0
0
1
1
1
1
1
1
1
1
1
0
1
0
0
~
-2913
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;
Các kỹ thuật thao tác trên bit
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
0
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
11648
5824
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;
Các kỹ thuật thao tác trên bit
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
0
1
1
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1456
728
msb
0
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
Ứng dụng trên số nguyên
Ứng dụng của các toán tử &, |, ^, ~
Bật bit thứ i của biến n (onbit)
Tắt bit thứ i của biến n (offbit)
Lấy giá trị của bit thứ i của biến n (getbit)
Gán giá trị 0 cho biến n (setzero)
Ứng dụng của các toán tử dịch bit << và >>
Nhân n với 2i (mul2pow)
Chia n với 2i (div2pow)
Các kỹ thuật thao tác trên bit
Bật bit thứ i của biến n
Các kỹ thuật thao tác trên bit
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n9
n8
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
n
i = 9
n9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
|
1
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n8
1
void onbit(int &n, int i)
{
n = n | (0x1 << i);
}
Tắt bit thứ i của biến n
Các kỹ thuật thao tác trên bit
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n9
n8
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
n
i = 9
n9
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
&
0
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n8
0
void offbit(int &n, int i)
{
n = n & (~(0x1 << i));
}
Lấy giá trị bit thứ i của biến n
Các kỹ thuật thao tác trên bit
n15
n14
n13
n12
n11
n10
n9
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
n
i = 9
n9
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
&
0
0
0
0
0
0
0
0
n9
0
0
0
0
0
0
0
0
int getbit(int n, int i)
{
return (n >> i) & 0x1;
}
Gán giá trị 0 cho biến n
Các kỹ thuật thao tác trên bit
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n9
n8
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
n
^
void setzero(int &n)
{
n = n ^ n;
}
n7
n6
n5
n4
n3
n2
n1
n0
n15
n14
n13
n12
n11
n10
n9
n8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Nhân n với 2i
Đặc điểm toán tử <<
n = ∑(nj2j) 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
 n << i = ∑(nj2j+i) = 2i∑(nj2j) = 2in
Vậy, dịch trái i bit  nhân với 2i
Các kỹ thuật thao tác trên bit
int mul2powi(int n, int i)
{
return n << i;
}
Chia n với 2i
Đặc điểm toán tử >>
n = ∑(nj2j) 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
 n << i = ∑(nj2j–i) = 2–i∑(nj2j) = 2–in = n/2i
Vậy, dịch phải i bit  chia cho 2i
Các kỹ thuật thao tác trên bit
int div2powi(int n, int i)
{
return n >> i;
}
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
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);


Bài 6: Tương tự bài 2 nhưng viết hàm RotateRight(n, i) để xoay bit sang phải.
Bài tập
Các kỹ thuật thao tác trên bit
13
12
11
10
9
8
7
6
5
4
3
2
1
0
15
14
1
1
0
0
0
0
1
0
1
1
1
0
0
0
1
0
???
Bài 3
Các kỹ thuật thao tác trên bit
0
a
b
c
0
0
1
0
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
0
1
2
3
4
5
6
7
c
b
b
c
a
a
c
a
b
a
b
c
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}