Chương trình tìm tổng XOR của tất cả cặp bitwise AND trong Python

Cho hai mảng arr1, arr2. XOR sum của một danh sách là XOR bitwise của tất cả phần tử. Xét danh sách chứa arr1[i] AND arr2[j] (bitwise AND) cho mọi cặp (i,j). Tìm XOR sum của danh sách đó.

Ví dụ: arr1 = [5,3,4], arr2 = [2,6] → danh sách AND = [0,4,2,2,0,4] → XOR sum = 0.

Quan sát quan trọng

XOR sum của tất cả (a_i & b_j) = (XOR của arr1) AND (XOR của arr2). Chứng minh nhờ tính chất phân phối của AND lên XOR.

Code Python

def solve(arr1, arr2):
    xor1 = 0
    xor2 = 0
    for a in arr1:
        xor1 ^= a
    for a in arr2:
        xor2 ^= a
    return xor1 & xor2

arr1 = [5, 3, 4]
arr2 = [2, 6]
print(solve(arr1, arr2))  # 0

Đầu vào / Đầu ra

Input: [5,3,4], [2,6]
Output: 0