Xor C++

NỘI DUNG BÀI VIẾT

Phép toán thao tác bit cơ bản

Phép toán AND (&)

Kết quả của phép AND sẽ là 1 nếu cả 2 toán hạng là 1. If a in Hai TOÁN HỌC LÀ 0, thì kết quả sẽ là 0, sau đây là bảng chân trị của AND

Ví dụ AND between 2 number of analysis is 5 and 3

1

2

3

0101 (5)

& 0011 (3)

= 0001 (1)

Minh họa với C++

1

2

3

4

5

6

7

8

9

10

#include

sử dụng không gian tên std;

int chính()

{

     int a = 5, b = 3;

     cout << "Đầu ra = " << a&b;

     return 0;

}

Kết quả

1

Đầu ra = 1

Phép toán OR (. )

Kết quả quá được phép HOẶC sẽ là 1 nếu một trong hai toán hạng là 1. Trong C++, allow OR are symbol is. Table of permissions OR

Ví dụ OR of 12 and 25

1

2

3

00001100 (12)

00011001 (25)

= 00011101 (29)

Minh họa với C++

1

2

3

4

5

6

7

8

9

10

#include

sử dụng không gian tên std;

int chính()

{

     int a = 12, b = 25;

     cout << "Đầu ra = " << . a|b;

     return 0;

}

Kết quả

1

Đầu ra = 29

Phép toán XOR  (^)

Kết quả của phép XOR là 1 nếu 2 toán hạng có giá trị khác nhau

1

2

3

00011110 (30)

^ 00001001 (9)

= 00010111 (23)

Minh họa với C++

1

2

3

4

5

6

7

8

9

10

#include

sử dụng không gian tên std;

int chính()

{

     int a = 30, b = 9;

     cout << "Đầu ra = " << a^b;

     return 0;

}

Kết quả

1

Đầu ra = 23

Ngoài ra, có 2 tính chất đặc biệt với phép XOR

• A ^ A = 0 (1 TOÁN XOR XOR with main it will by 0)
• A^0 = A (Bất kỳ phép toán xếp loại XOR nào với 0 đều bằng chính nó)

Phép toán NOT (~)

Toán tử NOT là toán tử 1 ngôi nhà. Nó thay đổi danh mục từ 0 sang 1 và ngược lại

1

2

~ 00011110 (30)

= 11100001 (225)

Minh họa với C++

1

2

3

4

5

6

7

8

9

#include

sử dụng không gian tên std;

int chính()

{

     cout << "Đầu ra = " << ~30;

     return 0;

}

Kết quả

1

Đầu ra = -31

Chúng ta thấy kết quả của ~30 là -31 thay vì 225, tại sao lại như vậy?

Để hiểu được điều này chúng ta sẽ nói qua một chút về bù 2 (2’s bổ sung)

Bù 2 của một số sẽ bằng bù 1 (~) của số đó cộng thêm 1

1

2

3

4

5

Sô thập phân   Số nhị phânBù 2

0               00000000           -(11111111+1) = -00000000 = -0(Số thập phân)

1               00000001           -(11111110+1) = -11111111 = -256(Số thập phân)

12             00001100           -(11110011+1) = -11110100 = -244(Số thập phân)

225             11100001           -(00011110+1) = -00011111 = -31(Số thập phân)

Đối với bất kỳ số nguyên n, thì ~n sẽ bằng -(n+1). Vì ~n được biểu diễn dưới dạng bù 2 và bù 2 của ~n sẽ là -(~(~n)+1)=-(n+1)

Suy ra kết quả đầy đủ sẽ là -31 thay vì 225 vì bù 1 của 30 (~30) là 225, bù 2 của 225 là -31

Bit toán tử

Dịch phải (>>)

Bit giao dịch toán tử sẽ thanh toán tất cả các bit phải được thực hiện bởi một số định sẵn

1

2

3

4

5

212 = 11010100 (Số nhị phân)

212>>2 = 00110101 (Số nhị phân) (Dịch sang phải 2 bit)

212>>7 = 00000001 (Số nhị phân) (Dịch sang phải 7 bit)

212>>8 = 00000000 (Số nhị phân) (Dịch sang phải 8 bit)

212>>0 = 11010100 (Giữ nguyên)

left left bit (<<)

Bit left left TOÁN TOÁN sẽ thanh toán tất cả các bit sang trái theo một số định nghĩa nhất

1

2

3

4

212 = 11010100 (Số nhị phân)

212<<1 = 11010100 (Số nhị phân) (Dịch sang trái 1 bít)

212<<0 = 11010100 (Giữ nguyên)

212<<4 = 11010100 (Số nhị phân) (Dịch sang trái 4 bít)

Minh họa với C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include

sử dụng không gian tên std;

int main() {

int num = 212, i;

cho(i = 0; i<=2; i++) {

cout << "Dịch sang phải " << i << " bits: " << (num>>i) << "\n";

}

cout << "\n";

cho(i = 0; i<=2; i++) {

cout << "Dịch sang trái " << i << " bits: " << (num<<i) << "\n";

}

return 0;

}

Kết quả

1

2

3

4

5

6

7

Dịch sang phải 0 bit. 212

Dịch sang phải 1 bit. 106

Dịch sang phải 2 bit. 53

Dịch sang trái 0 bit. 212

Dịch sang trái 1 bits. 424

Dịch sang trái 2 bit. 848

Bit file Phép toán thao tác

Bạn có thể thực hiện các bài tập liên quan đến phép toán thao tác bit (bitwise) trên nền tảng Luyện mã tại đây. Sau đây sẽ là 2 bài toán kinh điển có sự hỗ trợ của phép toán thao tác bit đi kèm hướng dẫn và lời giải tham khảo sử dụng C++

Check Tra Tra Tính chẵn lẻ của một số

đề bài. Cho 1 số nguyên, kiểm tra xem là hiện hay lẻ?

Chúng ta sẽ thấy 1 điều rằng những số hiện ở dạng nhị phân thì bit ngoài cùng bên phải luôn là bit 0, đối với số lẻ thì bit ngoài cùng bên phải luôn là 1. Dựa vào điều này ta có thể dễ dàng biết được tính ngày lẻ bằng cách truy xuất số đó AND(&) với 1 nếu kết quả bằng 1 thì đó là số lẻ, ngược lại nếu bằng 0 sẽ là số chẵn. Ví dụ

1

2

3

  0100 (4) |   0011 (3)<

& 0001 (1) | & 0001 (1)

= 0000 (0) | = 0001 (1)

Lời giải tham khảo với C++

1

2

3

4

5

6

7

8

9

10

11

12

#include

sử dụng namespce std;

int main() {

    int n = 9;

    nếu(n & 1 == 1) {

        cout << "Lẻ";

    } else {

        cout << "Chẵn";

    }

}

Số xuất hiện tìm kiếm 1 lần duy nhất trong mảng

đề bài. Cho 1 mảng số nguyên, mỗi số trong mảng xuất hiện 2 lần, ngoại trừ 1 số xuất hiện đúng 1 lần, hãy tìm số xuất hiện đúng 1 lần đó?

Đối với bài toán này chúng ta sẽ có khá nhiều cách giải, có thể sử dụng bảng băm, độ phức tạp thời gian sẽ là O(n) nhưng lại yêu cầu nhiều bộ nhớ hơn. Do đó ở đây chúng ta sẽ sử dụng các phép toán bit với độ phức tạp thời gian là O(n) và không gian là O(1)

Như mình đã đề cập ở phần XOR(^), cho phép XOR có 2 tính chất đặc biệt, và ý tưởng cho bài toán này là chúng ta chỉ cần XOR hết tất cả các phần tử trong mảng lại với nhau, 2 phần tử trùng nhau

1

2

3

4

5

6

7

The history has an array arr as after

mảng = [2, 3, 5, 4, 5, 3, 4]

Thực hiện XOR tất cả các phần tử với nhau

2^3^5^4^5^3^4

<=> 2^3^3^4^4^5^5 (đổi vị trí cho dễ nhìn)

<=> 2^0^0^0 (sử dụng tính chất A^A = 0)

<=> 2 (sử dụng tính chất A^0 = A)

Lời giải tham khảo với C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

#include

sử dụng không gian tên std;

int findUnique(int arr[], int n) {

int kết quả = 0;

for(int i=0; i< n; i++) {

kết quả ^= mảng[i];

}

trả về kết quả;

}

int main() {

int arr[] = {2, 3, 5, 4, 5, 3, 4};

int n = sizeof(arr) / sizeof(arr[0]);

cout << "Đầu ra = " << findUnique(arr, n);

return 0;

}

Kết quả

1

Đầu ra = 2

Trên đây là nội dung bài viết về các phép toán thao tác bit đi kèm các ví dụ sử dụng ngôn ngữ C++. Nếu bạn đọc có nhận xét hoặc thắc mắc thì có thể để lại bình luận ở cuối bài viết hoặc đặt câu hỏi tại nhóm Lập Trình Không Khó