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 3. Một số ví dụ sử dụng các phép toán xử lý bita. 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); } Á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); 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 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; } |
