Tính tổng a[i] XOR a[j]

#1

Mình đã đọc đi đọc lại code nhưng vẫn không hiểu, mong mọi người có thể giải thích giúp mình. Cảm ơn nhiều.

untitled.jpg976×531 54.2 KB 

#include <bits/stdc++.h>
using namespace std;
long n, a[1000005], b[1000005];
long long s = 0;
int main()
{
    cin >> n;
    for (long i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 20; i >= 0; i--){
        for (long u = 1; u <= n; u++)
            if ( (a[u] >> i) % 2 == 0) 
                b[i]++; // dem so bit 0
    }
    for (long i = 0; i <= n; i++)
        s += b[i] * (n - b[i]) * (1ll << i);
    cout << s;
}
#2

Format lại code bằng cách thêm 3 dấu ` vào đầu và cuối code, như thế này:
```
// code của bạn
```

Bạn format code xong thì mình mới đọc được code của bạn.

#3

OK bạn, mình đã edit rồi đó.

1 Like
#4

Code khá tường minh đó. Khổ nỗi bị sai :smile:.

Bạn để ý rằng, trong 1 dãy xor, cứ có chẵn bit 1 thì kết quả của dãy bằng 0, nếu không thì bằng 1.

1 ^ 1 ^ 1 = 1
1 ^ 1 ^ 1 ^ 1 = 0

Cái gì xor 0 cũng bằng chính nó.

x ^ 0 = x

Ta sẽ sử dụng 2 tính chất trên vào bài này.

Lưu ý thêm, a[i] ^ ... ^ a[j] = 1 số ghép bởi các bit, với mỗi bit k là kết quả của phép xor bit thứ k của các số a[i],... a[j], hay

res là 1 số có nhiều bit, với mọi bit k thì
res[k] = a[i][k] ^ ... ^ a[j][k]

Dòng trên không đúng về mặt lập trình, tuy nhiên mình sử dụng để bạn có thể mường tượng dễ hơn.

Limit bài này là 10^6 nên ta xét 20 bit. Với 20 bit, ta kiểm tra với mỗi bit i có bao nhiêu số a[u] có giá trị của bit i bằng 1. Các bit được đánh số từ phải sang trái. Bit 0 là bit tận cùng bên phải. Ví dụ:

a[1] = 10 = 0..001010 (2) // bit 1 và bit 3 bằng 1
a[2] = 8  = 0..001000 (2) // bit 3 bằng 1
a[3] = 7  = 0..000111 (2) // bit 0, 1, 2 bằng 1
a[4] = 18 = 0..010010 (2) // bit 1 và bit 4 bằng 1 
a[5] = 3  = 0..000011 (2) // bit 0 và bit 1 bằng 1
--------------------------
XOR       = 0..010100 (2) // thử xor cả dãy

author’s note: đến đây mình phát hiện ra code này không đẹp lắm, hơn nữa lại rất dễ gây hiểu nhầm, mình sẽ giải thích theo cách của mình.

Ta định nghĩa

b[i] = số lượng các số a[u] có bit i bằng 1

Cách kiểm tra xem số a[u] có bit i bằng 1 hay không:

// nhớ khởi tạo mảng b !!!!!!!!!

for (int i = 0; i <= 20; i++) // chạy từ 0 -> 20 không sao cả
    for (int u = 0; u < n; u++)
        if (a[u] & (1 << i) > 0) b[i]++;  // toán tử bitwise AND

1 << i là pow(2, i), nó biểu diễn dưới dạng nhị phân là 100..00 (i chữ số 0). Xem ví dụ để hiểu dòng code trên hơn:

x = 10 (1010 trong hệ nhị phân) -> lấy bit 3
         x = 1010
& (1 << 3) = 1000
-------------------
             1000
// 1 & 1 = 1, các trường hợp khác cho kết quả = 0 hết.

Khi kết quả x & (1 << 3) lớn hơn 0, ta kết luận x có bit 3 bằng 1.

Ta đã xong mảng b. Trích xuất kết quả:

s = 0;  // khởi tạo biến kết quả !!!!!!
for (int i = 0; i <= 20; i++) // lấy 20 bit
    if (b[i] % 2 == 0) // ở vị trí bit i có chẵn bit 1 -> bit i của kết quả sẽ bằng 0
        s += 0; // mình rảnh thôi, bạn có thể bỏ dòng này đi
    else // ở vị trí bit i có lẻ bit 1 -> bit i của kết quả sẽ bằng 1
        s += (1 << i)

Bạn nên đọc 1 tài liệu về bitwise để hiểu thêm.

3 Likes
#5

Cảm ơn bạn vì sự chi tiết :D.

1 Like
#6

Cám ơn anh vì sự nhiệt tình :D.

2 Likes
#7

Do xor tính trên từng bit nên ta xét bit thứ k của cả N số. Ta quan tâm đến số các bit 0 và số các bit 1 để tính số các bit 1 còn lại. Mà 1 xor 0 = 0 xor 1 = 1 nên kết quả tính là số bit 1 * số bit 0.

Vậy bài này quay trong O(N).

1 Like
#8

N <= 10^6, xấu nhất là có N / 2 bit 1 và N / 2 bit 0, có sợ nhân vào sẽ bị to quá không ạ?

#9

Mình cũng tự hỏi là số 12 đó thớt tính ntn :slight_smile: chứ sum này phải có int64, tối đa khoảng 10^12.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?