Bitwise Operations

Dãy công tắc

Số nguyên không âm $x$ được lưu dưới dạng nhị phân, $x = \sum_i d_i 2^i$ với $d_i \in \{0, 1\}$. Ta gọi $d_i$ là bit thứ $i$ và đánh số từ 0, bắt đầu ở bit nhỏ nhất, tức bên phải. Số $13 = 8 + 4 + 1$ viết là $1101_2$, có $d_0 = 1$, $d_1 = 0$, $d_2 = 1$, $d_3 = 1$.

Ba phép toán hai ngôi dưới đây làm việc theo từng cột: bit thứ $i$ của kết quả chỉ phụ thuộc bit thứ $i$ của hai toán hạng.

• a & b (AND) có bit 1 ở những cột mà cả hai bit đều là 1.
• a | b (OR) có bit 1 ở những cột mà ít nhất một bit là 1.
• a ^ b (XOR) có bit 1 ở những cột mà hai bit khác nhau.

Phép ~a (NOT) đảo mọi bit; với số có dấu, ~a bằng -a - 1, nên sau khi đảo ta thường phải AND với một mặt nạ để cắt các bit thừa phía trên.

Phép dịch x << k thêm $k$ bit 0 vào cuối, nên bằng $x \cdot 2^k$ khi không tràn. Phép dịch x >> k bỏ $k$ bit cuối, nên bằng $\lfloor x / 2^k \rfloor$ khi $x \ge 0$. Với số âm, >> làm tròn xuống (-7 >> 1 bằng $-4$) còn / làm tròn về 0; trong bài thi ta chỉ dịch số không âm.

Có hai bẫy mà ai cũng vấp ít nhất một lần. Bẫy thứ nhất là kiểu của hằng số: số 1 là int 32 bit, nên 1 << 40 dịch quá độ rộng của kiểu, một hành vi không xác định; gán kết quả vào biến long long cũng không cứu được vì phép dịch đã hỏng từ trước khi gán. Mặt nạ đi với số 64 bit phải viết 1LL << 40. Bẫy thứ hai là độ ưu tiên: các phép &, ^, | yếu hơn ==, !=, còn +, - mạnh hơn <<, >>. Vì vậy x & 1 == 0 được hiểu là x & (1 == 0), còn 1 << k + 1 là 1 << (k + 1). Quy tắc an toàn: bọc ngoặc quanh mọi biểu thức bit, như (x & 1) == 0.

Đọc, ghi và đếm bit. Mọi thao tác trên một bit riêng đều là AND, OR hoặc XOR với một mặt nạ (mask), số chỉ có đúng bit đó bật, 1LL << i: đọc bit (x >> i) & 1; bật x | (1LL << i); tắt x & ~(1LL << i); đảo x ^ (1LL << i); giữ $k$ bit thấp x & ((1LL << k) - 1), chính là $x \bmod 2^k$.

Hai biểu thức quan trọng nhất xoay quanh bit 1 thấp nhất. Viết $x > 0$ thành phần đầu $P$, một bit 1, rồi $k$ bit 0:

Phép trừ 1 mượn từ bit 1 thấp nhất, giống $1000 - 1 = 999$ trong hệ thập phân. Từ đó x & (x - 1) bằng $(P\,0\,0 \dots 0)_2$: nó xóa bit 1 thấp nhất. Còn số âm được máy lưu theo cách gọi là bù hai: $-x$ là $x$ đảo mọi bit (viết $\bar x$) rồi cộng 1, nên $-x = \bar x + 1 = (\bar P\,1\,0 \dots 0)_2$, nên x & -x giữ riêng bit 1 thấp nhất, bằng $2^k$; giá trị này hay gọi là lowbit(x), và cây Fenwick (bài 16) di chuyển giữa các nút bằng cách cộng hoặc trừ chính nó.

Số $x > 0$ là lũy thừa của hai khi chỉ có một bit 1, tức (x & (x - 1)) == 0. GCC có sẵn __builtin_popcountll(x) (số bit 1), __builtin_ctzll(x) (vị trí bit 1 thấp nhất) và __builtin_clzll(x) (số bit 0 đứng đầu trong 64 bit; độ dài nhị phân là 64 - __builtin_clzll(x)). Hai hàm ctz và clz không xác định khi $x = 0$. Chương trình sau in số bit 1, lowbit, độ dài nhị phân và kết quả kiểm tra lũy thừa của hai cho từng số dương.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll q, x;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> q;
    while (q--) {
        cin >> x;
        cout << __builtin_popcountll(x) << ' ' << (x & -x) << ' ' << 64 - __builtin_clzll(x) << ' '
             << ((x & (x - 1)) == 0 ? "yes" : "no") << '\n';
    }
}

ChạyInput4
13
44
64
1000000000000

Output3 1 4 no
3 4 6 no
1 64 7 yes
13 4096 40 no

Bản có đuôi ll là có chủ ý. Các hàm không đuôi, như __builtin_popcount, nhận unsigned int 32 bit; đưa vào đó một số long long thì 32 bit cao bị cắt âm thầm, và trình biên dịch thường không cảnh báo.

Ví dụNuôi Đủ Số Lượng

Đề. Hộp ban đầu rỗng. Mỗi sáng được thêm bao nhiêu vi khuẩn tùy ý, mỗi tối mọi vi khuẩn chia đôi. Muốn có lúc hộp chứa đúng $x \le 10^9$ con; in tổng số vi khuẩn ít nhất phải tự tay thêm vào.

Lời giải. Một con thêm vào sáng ngày nào đó, sau $k$ đêm thành $2^k$ con. Vậy số vi khuẩn lúc dừng là tổng các lũy thừa của hai, mỗi con thêm vào góp một số hạng, và đáp án là số số hạng ít nhất để viết $x$ thành tổng các lũy thừa của hai. Viết nhị phân là cách ít nhất: hai số hạng bằng nhau $2^k + 2^k$ luôn gộp được thành $2^{k+1}$, nên một cách viết tối ưu không có số hạng lặp, tức chính là biểu diễn nhị phân. Đáp án là số bit 1 của $x$: $13 = 1101_2$ cần 3 con.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll x;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> x;
    cout << __builtin_popcountll(x) << '\n';
}

ChạyInput13

Output3

Số nguyên là tập hợp

Một tập con của $\{0, 1, \dots, n - 1\}$ ứng với một số trong $[0, 2^n)$: phần tử $i$ thuộc tập khi bit thứ $i$ bật. Tập $\{0, 2, 3\}$ ứng với $1101_2 = 13$. Có đúng $2^n$ tập con và $2^n$ số, mỗi tập ứng với đúng một số. Số nguyên đóng vai tập hợp như vậy cũng gọi là mặt nạ (bitmask).

Mọi phép toán tập hợp trở thành một phép toán bit, và xử lý cả tập, tối đa 64 phần tử, trong một lệnh:

• giao A & B, hợp A | B, hiệu $A \setminus B$ là A & ~B, hiệu đối xứng A ^ B;
• phần bù trong $\{0, \dots, n - 1\}$ là A ^ full, với full = (1 << n) - 1;
• $A \subseteq B$ khi và chỉ khi (A & B) == A; số phần tử $|A|$ là popcount;
• phần tử $i$ thuộc $A$ khi (A >> i) & 1; thêm hay bỏ phần tử là bật hay tắt bit.

Duyệt mọi tập con là vòng for (ll mask = 0; mask < (1 << n); mask++). Với $n = 20$ có hơn một triệu mặt nạ; nếu mỗi mặt nạ tốn thêm $O(n)$ để xem từng phần tử thì tổng là $n \cdot 2^n \approx 2 \cdot 10^7$, vẫn nhẹ. Mảng lưu một giá trị cho mỗi mặt nạ tốn $2^n$ ô: $2^{20}$ số long long là 8 MB, còn $2^{24}$ số đã là 134 MB, nên $n$ thường không vượt quá 20 đến 22. Khi tập có hơn 64 phần tử, ta vẫn cần giao và hợp nhanh; lúc đó dùng bitset (bài 27) với cùng bộ phép toán.

Bài toán nhỏ: cho $n \le 20$ số và một giá trị $S$, đếm số tập con khác rỗng có tổng bằng $S$. Tính tổng riêng cho từng mặt nạ tốn $O(n)$ mỗi mặt nạ. Có cách tốt hơn: tổng của mask bằng tổng của mask bỏ phần tử nhỏ nhất, cộng thêm phần tử đó. Mặt nạ mask & (mask - 1) luôn nhỏ hơn mask, nên khi duyệt mask tăng dần thì nó đã được tính xong.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, S, a[20], sum[1 << 20];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> S;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll cnt = 0;
    for (ll mask = 1; mask < (1 << n); mask++) {
        sum[mask] = sum[mask & (mask - 1)] + a[__builtin_ctzll(mask)];
        if (sum[mask] == S) cnt++;
    }
    cout << cnt << '\n';
}

ChạyInput5 10
1 2 3 4 5

Output3

Ba tập thỏa mãn là $\{1, 4, 5\}$, $\{2, 3, 5\}$ và $\{1, 2, 3, 4\}$. Cả bài tốn $O(2^n)$. Khác biệt với cách duyệt lại từng bit, $O(n \cdot 2^n)$, thấy rõ khi $n$ lên 22:

Lấy từ mặt nạ nhỏ hơn nhanh gấp khoảng 12 lần. Cách tính một mặt nạ từ mặt nạ nhỏ hơn chính là khuôn của quy hoạch động trên tập con ở bài 15.

Ví dụChọn Bộ Bài Cân Đối

Đề. Có $n \le 15$ bài, bài $i$ có độ khó $c_i$. Đếm số tập gồm ít nhất hai bài có tổng độ khó trong $[l, r]$ và hiệu giữa độ khó lớn nhất với nhỏ nhất không nhỏ hơn $x$.

Lời giải. $2^{15} = 32768$ tập, duyệt hết. Với mỗi mặt nạ, đi qua 15 bit: bit nào bật thì cộng độ khó vào tổng và cập nhật lớn nhất, nhỏ nhất; rồi kiểm ba điều kiện, kể cả popcount ít nhất 2. Tổng cộng $15 \cdot 2^{15} \approx 5 \cdot 10^5$ phép. Tập một phần tử bị điều kiện hiệu loại luôn (hiệu 0 nhỏ hơn $x \ge 1$), nhưng kiểm popcount thì không phải nghĩ.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, l, r, x, c[15];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> l >> r >> x;
    for (ll i = 0; i < n; i++) cin >> c[i];
    ll ans = 0;
    for (ll mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcountll(mask) < 2) continue;
        ll s = 0, mx = 0, mn = 1e18;
        for (ll i = 0; i < n; i++)
            if ((mask >> i) & 1) {
                s += c[i];
                mx = max(mx, c[i]);
                mn = min(mn, c[i]);
            }
        if (l <= s && s <= r && mx - mn >= x) ans++;
    }
    cout << ans << '\n';
}

ChạyInput5 21 61 19
1 10 20 30 40

Output13

Mặt nạ con

Bây giờ cho một mặt nạ $m$ và cần liệt kê mọi tập con $s \subseteq m$, gọi là mặt nạ con (submask). Cách ngây thơ là cho $s$ chạy từ 0 tới $m$ rồi kiểm (s & m) == s. Cách này tốn $m + 1$ bước, kể cả khi $m$ chỉ có hai bit bật ở vị trí 59 và 3 và chỉ có bốn tập con để duyệt.

Ý tưởng: từ một mặt nạ con $s$, nhảy thẳng tới mặt nạ con lớn nhất nhỏ hơn $s$ bằng một phép toán:

Vì sao đúng? Viết $s = (P\,1\,0 \dots 0)_2$ với $k$ bit 0 ở cuối. Một mặt nạ con $t < s$ khác $s$ lần đầu (tính từ bit cao xuống) ở một vị trí mà $s$ có bit 1 còn $t$ có bit 0. Muốn $t$ lớn nhất thì vị trí khác nhau phải thấp nhất có thể, tức đúng là bit 1 thấp nhất của $s$; sau đó các bit phía dưới được tự do chọn, nên ta bật mọi bit mà $m$ cho phép. Đó chính xác là $(s - 1) \mathbin{\&} m$: $s - 1$ cho $(P\,0\,1 \dots 1)_2$, và AND với $m$ loại các bit nằm ngoài $m$ mà vẫn giữ nguyên $P$, vì $s \subseteq m$.

Bắt đầu từ $s = m$ rồi lặp phép nhảy, dãy giảm ngặt và đi qua mọi mặt nạ con đúng một lần, dừng ở 0. Với $m = 1010_2 = 10$, dãy là $10, 8, 2, 0$ như trong hình. Tập rỗng $s = 0$ cần chú ý: nếu quên dừng ở đó, phép $(0 - 1) \mathbin{\&} m$ trả về $m$ và vòng lặp chạy mãi. Vòng ngắn for (s = m; s; s = (s - 1) & m) thì bỏ qua 0 và bạn phải xử lý nó riêng.

Mặt nạ $m$ có $p$ bit bật thì có $2^p$ mặt nạ con. Duyệt mọi $m \in [0, 2^n)$ rồi mọi mặt nạ con của nó, tổng số bước là $3^n$. Lý do: mỗi cặp $s \subseteq m$ ứng với việc gán cho từng phần tử một trong ba trạng thái, “ngoài $m$”, “trong $m$ nhưng ngoài $s$”, “trong cả hai”. Vậy $3^n$ chứ không phải $4^n$. Với $n = 15$ đó là $1{,}4 \cdot 10^7$, với $n = 18$ là $3{,}9 \cdot 10^8$ (sát giới hạn), còn $n = 20$ là $3{,}5 \cdot 10^9$, quá chậm. Vì vậy các bài kiểu “chia tập thành các nhóm, mỗi nhóm $s$ tốn $f(s)$”, giải bằng $\mathrm{dp}_m = \min_{s \subseteq m} \bigl(\mathrm{dp}_{m \oplus s} + f(s)\bigr)$, chỉ chạy được khi $n$ cỡ 16 tới 18. Chương trình dưới đếm tổng số bước với $n = 10$ và in đúng $3^{10}$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll steps = 0;
    for (ll mask = 0; mask < (1 << n); mask++)
        for (ll s = mask;; s = (s - 1) & mask) {
            steps++;
            if (s == 0) break;
        }
    cout << steps << '\n';
}

ChạyInput10

Output59049

Theo từng bit

Đây là cách nghĩ được dùng nhiều nhất trong các bài về bit. Vì bit thứ $b$ của x & y, x | y, x ^ y chỉ phụ thuộc bit thứ $b$ của $x$ và $y$, một bài toán chỉ gồm các phép đó tách được thành 30 hay 60 bài toán độc lập trên các số 0 và 1. Mỗi bài con dễ hơn nhiều, và đáp án ghép lại bằng cách nhân kết quả ở bit thứ $b$ với trọng số $2^b$ rồi cộng.

Ví dụ: tính $\sum_{i<j} (a_i \oplus a_j)$ cho $n$ số. Với mỗi bit $b$, đặt $c_1$ là số phần tử có bit thứ $b$ bật và $c_0 = n - c_1$. Cặp $(i, j)$ đóng góp $2^b$ khi và chỉ khi hai bit khác nhau, nên có đúng $c_1 c_0$ cặp như vậy:

Với bốn số $5, 3, 6, 1$, tức $101_2, 011_2, 110_2, 001_2$: bit 2 bật ở hai số, bit 1 bật ở hai số, bit 0 bật ở ba số. Số cặp khác nhau là $4$, $4$ và $3$, nên tổng là $4 \cdot 4 + 4 \cdot 2 + 3 \cdot 1 = 27$. Kiểm trực tiếp sáu cặp: $6 + 3 + 4 + 5 + 2 + 7 = 27$.

Cùng khuôn đó cho các phép khác. Số cặp có bit $b$ của AND bật là $\binom{c_1}{2}$; của OR là $\binom{n}{2} - \binom{c_0}{2}$. Muốn AND, OR, XOR của một đoạn $[l, r]$ với nhiều truy vấn, ta giữ 30 mảng tổng tiền tố đếm số bit 1 của từng cột (bài 02): bit $b$ của OR bật khi số lượng trong đoạn lớn hơn 0, của AND khi số lượng bằng độ dài đoạn, của XOR khi số lượng lẻ.

Khi các số là $0, 1, \dots, n - 1$ liên tiếp thì không cần duyệt: cột $b$ lặp tuần hoàn với chu kỳ $2^{b+1}$, gồm $2^b$ số 0 rồi $2^b$ số 1. Do đó số số trong $[0, n)$ có bit $b$ bật là

Thử với $n = 11$, $b = 1$: chu kỳ 4, có $\lfloor 11/4 \rfloor \cdot 2 = 4$ số từ các chu kỳ đầy, cộng $\max(0, 3 - 2) = 1$ số từ chu kỳ dở, tổng 5; đúng là các số $2, 3, 6, 7, 10$.

Cách nghĩ này chỉ áp dụng cho &, |, ^, ~. Phép cộng, trừ, nhân và so sánh không tách được theo cột, vì bit thứ $b$ của $x + y$ còn phụ thuộc số nhớ từ các bit thấp hơn. Mục cuối sẽ cho thấy cách đưa phép cộng về XOR và AND.

Ví dụTổng XOR Của Mọi Cặp

Đề. Cho $N \le 3 \cdot 10^5$ số nguyên không âm $A_i < 2^{60}$. In $\sum_{i<j} (A_i \oplus A_j)$ theo modulo $10^9 + 7$.

Lời giải. Đúng công thức trên: với mỗi bit $b$ từ 0 tới 59, đếm $c_1$ phần tử có bit $b$ bật, cộng $2^b \cdot c_1 (N - c_1)$. Đếm bit mất $60N \approx 1{,}8 \cdot 10^7$ phép thay cho $4{,}5 \cdot 10^{10}$ cặp. Chỗ dễ sai là tràn số: $c_1 c_0$ tới $2{,}3 \cdot 10^{10}$, vẫn vừa ll, nhưng nhân tiếp với $2^b \bmod p$ cỡ $10^9$ thì vượt $9{,}2 \cdot 10^{18}$. Phải lấy modulo của $c_1 c_0$ trước khi nhân với trọng số. Với ví dụ $(0, 1, 4)$: bit 0 cho $1 \cdot 2 = 2$ cặp, đóng góp 2; bit 2 cho 2 cặp, đóng góp 8; tổng 10.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MOD = 1e9 + 7;
ll n, x, c[60];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> x;
        for (ll b = 0; b < 60; b++) c[b] += (x >> b) & 1;
    }
    ll ans = 0, w = 1;
    for (ll b = 0; b < 60; b++) {
        ans = (ans + c[b] * (n - c[b]) % MOD * w) % MOD;
        w = w * 2 % MOD;
    }
    cout << ans << '\n';
}

ChạyInput3
0 1 4

Output10

Bit cao trước

Bit càng cao càng nặng: $2^b$ lớn hơn mọi bit thấp cộng lại, vì $2^{b-1} + \dots + 2 + 1 = 2^b - 1$. Hệ quả cho các bài hỏi giá trị lớn nhất của một số ghép từ các bit: ta quyết định từng bit từ cao xuống thấp, bit nào còn đặt được bằng 1 thì đặt, và không bao giờ phải hối tiếc, vì bỏ một bit cao để đổi lấy cả loạt bit thấp luôn là lỗ.

Ví dụ: cho $n$ số nhỏ hơn $2^{30}$, tìm giá trị lớn nhất của $a_i \mathbin{\&} a_j$ với $i \ne j$. Duyệt mọi cặp tốn $O(n^2)$. Cách khác: giữ ans, thử từng bit $b$ từ 29 xuống 0. Đặt c = ans | (1LL << b) rồi đếm số phần tử $x$ chứa mọi bit của c, tức (x & c) == c. Nếu có ít nhất hai phần tử như vậy thì AND của chúng chứa c, nên ta giữ ans = c.

Vì sao đúng? Gọi $c$ là khả thi nếu có ít nhất hai phần tử chứa mọi bit của $c$. Đáp án $M$ là số khả thi lớn nhất. Giả sử các bit từ cao tới bit $b + 1$ của ans đã trùng với $M$. Nếu ans | (1LL << b) khả thi thì $M$ không nhỏ hơn nó, mà $M$ có cùng các bit cao, nên $M$ buộc phải có bit $b$. Ngược lại nếu $M$ có bit $b$ thì ans | (1LL << b) chỉ gồm các bit của $M$, nên vẫn khả thi. Vậy thử rồi giữ bit $b$ khi khả thi luôn đặt đúng bit của $M$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5;
ll n, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll ans = 0;
    for (ll b = 29; b >= 0; b--) {
        ll c = ans | (1LL << b), cnt = 0;
        for (ll i = 0; i < n; i++)
            if ((a[i] & c) == c) cnt++;
        if (cnt >= 2) ans = c;
    }
    cout << ans << '\n';
}

ChạyInput5
12 8 6 14 3

Output12

Chạy tay: bit 3 có ba số chứa $1000_2$ (là $12, 8, 14$) nên giữ, ans $= 8$; bit 2 có hai số chứa $1100_2$ nên giữ, ans $= 12$; bit 1 chỉ có $14$ chứa $1110_2$ nên bỏ; bit 0 không có số nào chứa $1101_2$. Đáp án $12 = 12 \mathbin{\&} 14$, trong $O(30 n)$. Mẫu “thử bit cao, giữ nếu còn khả thi” xuất hiện rất nhiều: XOR lớn nhất của hai số (trie ở bài 20, cơ sở XOR ở bài 61), tối đa hóa AND sau một số thao tác, chọn $X \le K$ để tối đa hóa một tổng.

Ví dụAND Lớn Nhất Sau Khi Bật Bit

Đề. Cho dãy $n$ số $a_i < 2^{31}$ (tổng $n$ qua các test tới $2 \cdot 10^5$) và $k \le 10^9$. Mỗi thao tác bật một bit (vị trí 0 tới 30) của một phần tử. Với không quá $k$ thao tác, in AND lớn nhất có thể của cả dãy.

Lời giải. Bit $b$ có mặt trong AND khi mọi phần tử đều mang nó, và muốn vậy phải bật bit $b$ ở mọi phần tử còn thiếu, tốn đúng số phần tử thiếu. Chi phí của các bit độc lập với nhau, vì bật bit này không ảnh hưởng bit kia. Vậy duyệt $b$ từ 30 xuống 0: nếu số phần tử thiếu bit $b$ không vượt ngân sách còn lại thì trả và bật bit $b$ trong đáp án. Tham lam đúng vì một bit cao đáng giá hơn mọi bit thấp cộng lại. Với test đầu, bit 1 thiếu ở số 1 và bit 0 thiếu ở số 2: tốn 2 thao tác, AND bằng 3.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5;
ll t, n, k, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (ll i = 0; i < n; i++) cin >> a[i];
        ll ans = 0;
        for (ll b = 30; b >= 0; b--) {
            ll need = 0;
            for (ll i = 0; i < n; i++)
                if (!((a[i] >> b) & 1)) need++;
            if (need <= k) {
                k -= need;
                ans |= 1LL << b;
            }
        }
        cout << ans << '\n';
    }
}

ChạyInput2
3 2
1 2 3
3 0
7 3 5

Output3
1

XOR và phép cộng

XOR là phép cộng từng bit theo modulo 2, không có nhớ. Bốn tính chất làm nên gần như mọi mẹo với XOR: giao hoán, kết hợp, $x \oplus 0 = x$ và $x \oplus x = 0$. Tính chất cuối nói rằng XOR là phép ngược của chính nó, nên ta chuyển vế được: $a \oplus b = c$ khi và chỉ khi $a = b \oplus c$. Ba hệ quả hay dùng:

• Hai số bằng nhau triệt tiêu. Nếu trong dãy mọi giá trị xuất hiện chẵn lần, trừ đúng một giá trị xuất hiện lẻ lần, thì XOR cả dãy cho ra giá trị ấy.
• XOR có phép ngược nên có tiền tố, như tổng ở bài 02: với $\mathrm{px}_i = a_1 \oplus \dots \oplus a_i$ thì XOR của đoạn $[l, r]$ là $\mathrm{px}_r \oplus \mathrm{px}_{l-1}$.
• XOR của mọi phần tử trừ phần tử $i$ là $T \oplus a_i$, với $T$ là XOR của cả dãy.

Phép cộng khác ở chỗ có nhớ, nhưng vẫn quy về XOR và AND được. Ở cột thứ $i$ với hai bit $u, v$, ta có $u + v = (u \oplus v) + 2\,(u \mathbin{\&} v)$, thử ngay được trong ba trường hợp $0 + 0$, $1 + 0$ và $1 + 1 = 0 + 2 \cdot 1$. Cộng mọi cột lại:

XOR là tổng khi bỏ qua nhớ, còn AND chỉ ra các cột sinh nhớ, mỗi nhớ sang cột bên cạnh nên nhân đôi. Từ đây: $a + b \ge a \oplus b$; hai vế bằng nhau khi và chỉ khi $a \mathbin{\&} b = 0$, tức hai số không chung bit nào; và hiệu $a + b - (a \oplus b)$ luôn chẵn. Một công thức cùng loại là $a + b = (a \mathbin{|} b) + (a \mathbin{\&} b)$.

Ví dụXOR Của Một Đoạn Số

Đề. Cho $0 \le A \le B \le 10^{12}$. In $A \oplus (A + 1) \oplus \dots \oplus B$.

Lời giải. Dùng tiền tố XOR: đặt $F(n) = 0 \oplus 1 \oplus \dots \oplus n$ và $F(-1) = 0$. Phần chung $F(A - 1)$ xuất hiện hai lần trong $F(B) \oplus F(A - 1)$ nên triệt tiêu, còn lại đúng đáp án. Tính $F(n)$ trong $O(1)$: bốn số $4q, 4q + 1, 4q + 2, 4q + 3$ giống nhau ở mọi bit từ bit 2 trở lên, phần chung đó xuất hiện 4 lần nên triệt tiêu, còn hai bit thấp chạy qua $00, 01, 10, 11$ có XOR bằng 0. Vậy mỗi khối bốn số có XOR 0, và $F(n)$ chỉ còn là XOR của phần dở ở khối cuối. Theo $n \bmod 4$ là $0, 1, 2, 3$, ta có $F(n) = n$, $1$, $n + 1$, $0$. Chỗ dễ sai là $A = 0$: cần $F(-1)$, mà -1 % 4 bằng $-1$ chứ không phải 3, nên trả 0 riêng cho $n < 0$. Với ví dụ, $F(9) = 1$, $F(4) = 4$, đáp án $1 \oplus 4 = 5$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll A, B;

ll F(ll n) {
    if (n < 0) return 0;
    if (n % 4 == 0) return n;
    if (n % 4 == 1) return 1;
    if (n % 4 == 2) return n + 1;
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> A >> B;
    cout << (F(B) ^ F(A - 1)) << '\n';
}

ChạyInput5 9

Output5