Phép Toán Bit – Tuoitrekthc

1.     Khái niệm về bit

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).

2.     Các phép toán xử lý bit của các số nguyên

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:

a.  Phép nhân logic trên các bit (toán tử là &) , còn gọi là phép AND

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)

b.  Phép cộng logic trên các bit (toán tử là |), còn gọi là phép OR

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)

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

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)

d. Phép đảo bit (toán tử là ~), còn gọi là phép NOT

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)

e. Phép dịch trái SHL (toán tử là <<)

x << i;  cho x dịch sang trái i bit. 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à >>)

x >> i;  cho x dịch sang phải i bit. Kết quả là số nguyên x được chia cho 2i.

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ý bit 

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);

}

Á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;

}

 

Chia sẻ:

• X
• Facebook

Thích Đang tải...