Mỗi byte bao gồm 8 bit được mã số từ phải sang trái là từ bit thấp (số 0) đến bit cao (số 7). Các bit được đánh số từ trái qua phải là: 7 6 5 4 3 2 1 0 Mỗi bit có thể nhận 1 trong 2 giá trị là 0 hoặc 1. Tại mỗi thời điểm thực hiện chương trình mỗi bit đươc nhận một giá trị xác định. Mọi số nguyên trong máy đều biểu diễn dưới dạng nhị phân, thí dụ số
19 được biểu diễn nhị phân là: 0 0 0 1 0 0 1 1 (vì 19=16+2+1). Các phép toán sau đây thực hiện trên các số nguyên và cho kết quả là số nguyên: Thực hiện với hai số nguyên trên từng cặp bit tương ứng theo quy tắc: AND hai bit bằng 1 khi và chỉ khi cả hai bit bằng 1, còn lại là 0. (Chú ý phép AND hai biểu
thức logic là &&) x=19; //x=00010011 y=21; //y=00010101 z=x & y; //z=00010001(17) Thực hiện với hai số nguyên trên từng cặp bit tương ứng theo quy tắc: OR hai bit bằng 0 khi và chỉ khi cả hai bit cùng bằng 0, còn lại là1. (Chú ý phép cộng hai biểu thức logic là hai gạch đứng ||) x= 19; //x=00010011 y= 21; //y=00010101 z= x|y; //z=00010111(23) Thực hiện với hai số nguyên trên từng cặp bit tương ứng theo quy tắc: XOR hai bit bằng 1 khi và chỉ khi hai bit khác nhau, ngược lại bằng 0 khi hai bit bằng nhau. x= 19; //x=00010011 y= 21;
//y=00010101 Z= x^y; //z=00000110(6) Thực hiện trên một số nguyên sẽ đảo mọi bit của số nguyên từ 0 thành 1 và ngược lại (Chú ý phép đảo giá trị biểu thức logic là !) x= 19; //x=00010011 y= ~x; //y=11101100 (236=128+64+32+8+4, lấy bù 2 thành -20) x << i; cho x dịch sang trái i bit. x >> i; cho x dịch sang phải i bit. Sau đây là chương trình kiểm nghiệm: #include <iostream> using namespace std; int main () { int x=19, y=21; int a=~x, b=x&y, c=x|y, d=x^y, e = x << 2, f= e>>2; cout << a << ” ” << b << ” ” << c <<” ”
<< d << endl; cout << e << ” ” << f << endl; system (“pause”); return 0; } Kết quả sẽ là: -20 17 23 6 76 19 a. Hàm getbit(x,i) cho giá trị bit i của số nguyên x. int getbit(long x, int i){ return ((x>>i)&1);
1. Khái niệm về bit
2. Các phép toán xử lý bit của các số nguyên
a. Phép nhân logic trên các bit (toán tử là &) , còn gọi là phép AND
b. Phép cộng logic trên các bit (toán tử là |), còn gọi là phép OR
c. Phép cộng loại trừ trên các bit (toán tử là ^), còn gọi là phép XOR
d. Phép đảo bit (toán tử là ~), còn gọi là phép NOT
e. Phép dịch trái SHL (toán tử là <<)
Kết quả là số nguyên x
được nhân với 2i.f. Phép dịch phải SHR (toán tử là >>)
Kết quả là số nguyên x được chia cho 2i.3. Một số ví dụ sử dụng các phép toán xử lý bit
}
Áp dụng: Biểu diễn x dưới dạng nhị phân
for (int i=15; i>=0; i–) cout << getbit(x,i);
b. Hàm getnum(x,i,j) cho số tạo bởi các bit từ i đến j tính từ trái qua phải (i>= j)
long getnum(long x, int i, int j){
int k= (sizeof(x)<<3)-1-i; //số lượng bít cao hơn bit i
x = x << k; //xóa bỏ các bít cao hơn bít i
x=(unsigned long) x >> (k+j); // xóa bỏ các bít thấp hơn bít j
return x;
}
Áp dụng: Sử dụng GetNum có thể chuyển từ số tự nhiên sang biểu diễn thập lục phân (tương tự cho bát phân):
#include <iostream>
using namespace std;
char H[16]={‘0′,’1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’A’,’B’,’C’,’D’,’E’,’F’};
long getnum(long x, int i, int j){
int k= (sizeof(x)<<3)-1-i;
x = x << k;
x=(unsigned long) x >> (k+j);
return x;
}
int main() {
long x = 23456781;
i=15;
while (i>=0){
cout << H[getnum(x,i, i-3)];
i = i-4;
}
cout << endl;
system(“pause”);
return 0;
}
c) Hàm Batbit(x, i) trả lại giá trị mới của x sau khi bit i của x được gán bằng 1
Mô tả: Ta chuyển 1 đến vị trí
i tương ứng sau đó thực hiện phép cộng logic với byte x. Ví dụ:
long Batbit(long x, int i) {
return (x | (1 << i));
}
d) Hàm Daobit(x, i) trả về giá trị mới của x sau khi đã đảo bít i của x (từ 0 thành 1 hoặc ngược lại từ 1 thành 0)
long Daobit(long x, int i){
return (x ^ (1 << i));
}
Bài tập về nhà. Đọc và phân tích bài Ném đá (OLP’21 2012)
#include <iostream>
#include <fstream>
#include <vector>
#define maxM 1000005
#define maxN 100005
using namespace std;
ifstream fi (“stone.inp”);
ofstream fo (“stone.out”);
long m,n;
long a, b;
int p, q, k;
vector<int> v;
int getbit(long x, int i){ // Lay bit i cua x
return ((x>>i)&1);
}
int getnum(int x, int i, int j) {
int k= (sizeof(x)<<3)-1-i;
x = x << k;
x=(unsigned int) x>> (k+j);
return (x);
}
void init(long a, int p, long b, int q) {
if (a==b) {
int x= getnum(v[a], p, q);
v[a] -= x; }
else { // a<b
for (int i=a+1; i<b; i++) v[i]=0;
int x= getnum(v[a], p, 0);
v[a] -= x;
int k= (sizeof(v[b])<<3)-q;
v[b] = v[b] << k;
v[b]=(unsigned int) v[b]>>k;
}
}
bool anser(long a, int p, long b, int q) {
if (a==b) {
int x= getnum(v[a], p, q);
if (v[a]-x) return true; }
else {
for (int i=a+1; i<b; i++)
if (v[i])
return true;
int x= getnum(v[a], p, 0);
if (x)
return true;
int y=v[b];
int k= (sizeof(y)<<3)-q;
y = y << k;
y=(unsigned int) y>>k;
if (v[b]>y)
return true;
}
return false;
}
int main() {
int vi;
fi >> m >> n >> k;
v.reserve(n);
for (long i=0; i<m; i++){
fi >> vi;
v.push_back(vi);
}
for (long i=0; i<n; i++) {
fi >> a >> p >> b >> q;
init(a,p,b,q);
}
for (long i=0; i<k; i++) {
fi >> a >> p >> b >> q;
if (anser(a,p,b,q))
fo << “YES” << endl;
else fo << “PASS” << endl;
}
return 0;
}