Phép toán bit

Mức độ: Cơ bản

Máy tính lưu số dưới dạng nhị phân (bài Hệ nhị phân và hệ cơ số). Phép toán bit làm việc trực tiếp trên từng chữ số nhị phân (gọi là bit), rất nhanh và giúp viết gọn nhiều thuật toán: kiểm tra số chẵn lẻ, tìm số xuất hiện một lần, duyệt mọi tập con…

Các phép toán bit

Thực hiện trên từng cặp bit cùng vị trí của hai số:

Phép	Python, C++	Bit kết quả bằng 1 khi	12 (1100) và 10 (1010)
AND	`a & b`	cả hai bit đều 1	1000 = 8
OR	`a \| b`	ít nhất một bit là 1	1110 = 14
XOR	`a ^ b`	hai bit khác nhau	0110 = 6
dịch trái	`a << k`	dời mọi bit sang trái k vị trí (nhân 2^k)	`12 << 1` = 24
dịch phải	`a >> k`	dời sang phải k vị trí (chia 2^k, làm tròn xuống)	`12 >> 2` = 3

Bit thứ i (đếm từ 0, từ phải sang) có giá trị 2ⁱ = 1 << i.

Làm việc với một bit

Việc	Cách viết
bit thứ i của n có bằng 1 không?	`(n >> i) & 1`
bật bit i (thành 1)	`n \| (1 << i)`
tắt bit i (thành 0)	`n & ~(1 << i)`
đảo bit i	`n ^ (1 << i)`
n lẻ?	`n & 1` (giống `n % 2`)

Mẹo n & (n - 1): trừ 1 làm bit 1 thấp nhất của n thành 0 và các bit thấp hơn thành 1. AND với n thì xóa đúng bit 1 thấp nhất. Ví dụ 12 = 1100, 11 = 1011, 12 & 11 = 1000.

n là lũy thừa của 2 khi n > 0 và n & (n - 1) == 0 (chỉ có một bit 1).
Đếm số bit 1: lặp n = n & (n - 1) cho tới khi n = 0, đếm số lần.

Lưu ý trong C++: 1 << i có kiểu int, với i ≥ 31 sẽ sai. Dùng 1LL << i khi làm việc với long long. Thứ tự ưu tiên của &, |, ^ thấp hơn ==, nên luôn đặt ngoặc: (n & 1) == 0, không viết n & 1 == 0.

Tính chất của XOR

a ^ a = 0 và a ^ 0 = a.
XOR có tính giao hoán và kết hợp: đổi thứ tự thế nào kết quả cũng như nhau.

Hệ quả: XOR tất cả các số trong một dãy thì các số xuất hiện chẵn lần tự triệt tiêu. Trong dãy 4 7 2 7 4, kết quả là 2: số duy nhất xuất hiện lẻ lần, tìm được mà không cần sắp xếp hay đếm.

Duyệt mọi tập con bằng số nhị phân

Với n phần tử, mỗi tập con ứng với một số từ 0 đến 2ⁿ - 1: bit thứ i bằng 1 nghĩa là chọn phần tử thứ i. Ví dụ với ba bạn An, Bình, Chi, số 5 = 101 là tập gồm An và Chi.

Python
C++

a = [3, 5, 9]
n = len(a)
for mask in range(1 << n):                        # 2^n tập con
    tap = [a[i] for i in range(n) if mask >> i & 1]
    print(mask, tap, sum(tap))

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {3, 5, 9};
    int n = a.size();
    for (int mask = 0; mask < (1 << n); mask++) {   // 2^n tập con
        int tong = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) tong += a[i];
        cout << mask << " " << tong << endl;
    }
    return 0;
}

Với n = 20 có khoảng 10⁶ tập con, duyệt hết vẫn nhanh. Đây là cách vét cạn chuẩn cho các bài “chọn một số phần tử” khi n nhỏ (đã dùng ở bài Nguyên lý bù trừ).

Luyện tập

Gồm 25 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Phép toán bit cơ bản

Bài 1. AND, OR, XOR

Nhập a, b (0 ≤ a, b ≤ 10¹⁸). In ra a AND b, a OR b, a XOR b trên một dòng.

Ví dụ: nhập 12 10 thì in ra 8 14 6.

Kiểm tra: nhập 2026 1000.

Xem đáp số

1000 2026 1026

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Bit thứ i

Nhập n, i (0 ≤ n ≤ 10¹⁸, 0 ≤ i ≤ 62). In ra bit thứ i của n (0 hoặc 1, đếm từ 0 bên phải).

Ví dụ: nhập 13 2 thì in ra 1.

Kiểm tra: nhập 2026 4.

Xem đáp số

0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Bật, tắt, đảo bit

Nhập n, i (0 ≤ n ≤ 10¹⁸, 0 ≤ i ≤ 61). In ra ba số: n sau khi bật bit i, n sau khi tắt bit i, n sau khi đảo bit i (mỗi phép làm trên n ban đầu).

Ví dụ: nhập 13 1 thì in ra 15 13 15.

Kiểm tra: nhập 2026 5.

Xem đáp số

2026 1994 1994

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Lũy thừa của 2

Nhập n (1 ≤ n ≤ 10¹⁸). In ra YES nếu n là lũy thừa của 2 (1, 2, 4, 8, …), ngược lại NO.

Ví dụ: nhập 64 thì in ra YES.

Kiểm tra: nhập 2026.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Đếm bit 1 nhanh

Nhập n (0 ≤ n ≤ 10¹⁸). Đếm số bit 1 của n bằng cách lặp n = n & (n - 1).

Ví dụ: nhập 13 thì in ra 3.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

24

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Bit 1 thấp nhất

Nhập n (1 ≤ n ≤ 10¹⁸). In ra giá trị của bit 1 thấp nhất của n (ví dụ 12 = 1100 thì in 4).

Ví dụ: nhập 12 thì in ra 4.

Kiểm tra: nhập 2026.

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Số bit để biểu diễn

Nhập n (1 ≤ n ≤ 10¹⁸). In ra số bit cần để viết n trong hệ nhị phân (vị trí bit 1 cao nhất cộng 1).

Ví dụ: nhập 13 thì in ra 4.

Kiểm tra: nhập 2026.

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. XOR

Bài 8. Số xuất hiện lẻ lần

Dòng đầu là n (n ≤ 10⁶, n lẻ). Dòng thứ hai có n số nguyên dương, trong đó đúng một số xuất hiện lẻ lần, các số khác xuất hiện chẵn lần. In ra số đó.

Ví dụ:

Nhập	In ra
`5` `4 7 2 7 4`	`2`

Kiểm tra: nhập

9
5 3 5 8 3 8 8 1 1

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số bị thiếu

Dòng đầu là n (n ≤ 10⁶). Dòng thứ hai có n - 1 số khác nhau trong khoảng 1 đến n (thiếu đúng một số). In ra số bị thiếu.

Ví dụ:

Nhập	In ra
`5` `3 1 5 2`	`4`

Kiểm tra: nhập

10
7 2 9 10 1 3 8 4 5

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. XOR từ 1 đến n

Nhập n (n ≤ 10¹⁸). In ra 1 XOR 2 XOR 3 XOR … XOR n.

Ví dụ: nhập 5 thì in ra 1.

Kiểm tra: nhập 2026.

Xem đáp số

2027

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. XOR đoạn

Dòng đầu có n, q (n, q ≤ 10⁵). Dòng thứ hai có n số nguyên không âm. Mỗi dòng trong q dòng tiếp theo có l, r: in ra a_l XOR … XOR a_r.

Ví dụ:

Nhập	In ra
`5 2` `3 1 4 1 5` `1 3` `2 5`	`6` `1`

Kiểm tra: nhập

8 3
6 2 9 4 7 1 3 8
1 8
3 6
5 5

Xem đáp số

4
11
7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Hai số xuất hiện một lần

Dòng đầu là n (n ≤ 10⁶). Dòng thứ hai có n số nguyên dương, trong đó đúng hai số khác nhau xuất hiện một lần, các số khác xuất hiện đúng hai lần. In ra hai số đó theo thứ tự tăng dần.

Ví dụ:

Nhập	In ra
`6` `4 1 2 1 2 9`	`4 9`

Kiểm tra: nhập

10
7 3 5 4 5 3 8 7 6 4

Xem đáp số

6 8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đếm cặp có XOR bằng k

Dòng đầu có n, k (n ≤ 10⁵). Dòng thứ hai có n số nguyên không âm. Đếm số cặp i nhỏ hơn j với a_i XOR a_j = k.

Ví dụ:

Nhập	In ra
`4 6` `1 7 3 5`	`2`

Kiểm tra: nhập

8 3
1 2 3 0 2 1 4 7

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Duyệt tập con

Bài 14. Đếm tập con có tổng bằng S

Dòng đầu có n, S (n ≤ 20). Dòng thứ hai có n số nguyên dương. Đếm số tập con khác rỗng có tổng đúng bằng S.

Ví dụ:

Nhập	In ra
`4 8` `3 5 2 6`	`2`

Kiểm tra: nhập

10 20
1 2 3 4 5 6 7 8 9 10

Xem đáp số

31

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Chia hai nhóm chênh lệch ít nhất

Dòng đầu là n (n ≤ 20). Dòng thứ hai có n số nguyên dương (khối lượng các món đồ). Chia các món đồ thành hai nhóm sao cho chênh lệch tổng khối lượng hai nhóm nhỏ nhất. In ra chênh lệch đó.

Ví dụ:

Nhập	In ra
`4` `3 1 4 2`	`0`

Kiểm tra: nhập

6
10 20 15 5 25 8

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Chọn quà trong ngân sách

Dòng đầu có n, B (n ≤ 20). n dòng tiếp theo, mỗi dòng có giá tiền và độ yêu thích của một món quà. Chọn một số món có tổng giá không quá B sao cho tổng độ yêu thích lớn nhất. In ra tổng độ yêu thích đó.

Ví dụ:

Nhập	In ra
`3 10` `5 6` `4 5` `6 8`	`13`

Kiểm tra: nhập

Xem đáp số

23

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Đếm tập con có XOR bằng 0

Dòng đầu là n (n ≤ 20). Dòng thứ hai có n số nguyên không âm. Đếm số tập con khác rỗng có XOR các phần tử bằng 0.

Ví dụ:

Nhập	In ra
`3` `1 2 3`	`1`

Kiểm tra: nhập

8
1 2 3 4 5 6 7 8

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Bảng đèn 3 × 3

Bảng 3 × 3 bóng đèn, mỗi bóng sáng (1) hoặc tắt (0). Chạm vào một bóng thì bóng đó và các bóng chung cạnh với nó đều đổi trạng thái. Nhập 3 dòng mô tả bảng, in ra số lần chạm ít nhất để tắt hết các bóng (hoặc -1 nếu không thể).

Ví dụ:

Nhập	In ra
`010` `111` `010`	`1`

Kiểm tra: nhập

101
010
101

Xem đáp số

9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Nhóm bạn quen biết nhau

Có n bạn (n ≤ 18) và m cặp quen nhau. Tìm nhóm đông nhất mà hai bạn bất kỳ trong nhóm đều quen nhau. Dòng đầu có n, m; m dòng tiếp theo mỗi dòng một cặp (đánh số từ 1). In ra số người của nhóm đó.

Ví dụ:

Nhập	In ra
`4 4` `1 2` `2 3` `1 3` `3 4`	`3`

Kiểm tra: nhập

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Mặt nạ bit và ứng dụng

Bài 20. Mã Gray

Mã Gray của n là n XOR (n >> 1). Nhập n (n ≤ 10¹⁸), in ra mã Gray của n.

Ví dụ: nhập 5 thì in ra 7.

Kiểm tra: nhập 2026.

Xem đáp số

1055

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Dãy mã Gray

Nhập k (1 ≤ k ≤ 10). In ra mã Gray của 0, 1, …, 2^k - 1, mỗi mã viết đủ k chữ số nhị phân, mỗi mã một dòng.

Ví dụ:

Nhập	In ra
`2`	`00` `01` `11` `10`

Kiểm tra: nhập 3.

Xem đáp số

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Đảo ngược 32 bit

Nhập n (0 ≤ n nhỏ hơn 2³²). Viết n thành đúng 32 bit (thêm 0 ở đầu), đảo ngược thứ tự 32 bit đó và in ra giá trị mới.

Ví dụ: nhập 1 thì in ra 2147483648.

Kiểm tra: nhập 2026.

Xem đáp số

1474297856

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 23. Số có số bit 1 chẵn

Nhập n (n ≤ 10⁶). Đếm các số từ 0 đến n có số bit 1 là số chẵn.

Ví dụ: nhập 7 thì in ra 4.

Kiểm tra: nhập 2026.

Xem đáp số

1014

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 24. Quyền truy cập tệp

Trên Linux, quyền truy cập một tệp ghi bằng 3 chữ số hệ 8, ví dụ 754: lần lượt cho chủ sở hữu, nhóm, người khác. Mỗi chữ số là tổng của đọc = 4, ghi = 2, chạy = 1. Nhập 3 chữ số, in ra dạng chữ 9 ký tự (r, w, x hoặc -).

Ví dụ: nhập 754 thì in ra rwxr-xr--.

Kiểm tra: nhập 640.

Xem đáp số

rw-r-----

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 25. Chọn món không xung khắc

Có n món ăn (n ≤ 20) và m cặp món không được ăn cùng nhau. Chọn nhiều món nhất mà không có cặp xung khắc nào. Dòng đầu có n, m; m dòng tiếp theo mỗi dòng một cặp (đánh số từ 1). In ra số món nhiều nhất.

Ví dụ:

Nhập	In ra
`4 3` `1 2` `2 3` `3 4`	`2`

Kiểm tra: nhập

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English