XOR các phần tử của mảng có số bit thiết lập bằng K trong C++

Trong bài toán này, chúng ta được cung cấp một mảng n phần tử và một giá trị nguyên k. Nhiệm vụ là tìm XOR của tất cả các phần tử trong mảng có số bit thiết lập (set bits) bằng k.

Ví dụ minh họa

mảng = {2, 12, 44, 103, 17} , K = 3

Kết quả

44

Để giải quyết bài toán này, chúng ta sẽ đếm số bit thiết lập của từng phần tử trong mảng và so sánh với k. Nếu số bit thiết lập bằng k, chúng ta sẽ đưa phần tử đó vào một vector và tính XOR của tất cả các phần tử trong vector đó.

Để đếm số bit thiết lập, chúng ta sử dụng hàm __builtin_popcount() – một hàm tích hợp sẵn trong C++.

Chương trình minh họa

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

int XorKSetBits(int arr[], int n, int k) { 
    vector<int> kBitElements; 
    for (int i = 0; i < n; i++) { 
        if (__builtin_popcount(arr[i]) == k) { 
            kBitElements.push_back(arr[i]); 
        } 
    } 
    int result = kBitElements[0]; 
    for (int i = 1; i < kBitElements.size(); i++) 
        result ^= kBitElements[i]; 
    return result; 
} 

int main() { 
    int arr[] = { 2, 12, 44, 103, 17 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 3; 
    cout << "XOR của các phần tử mảng với " << k << " bit thiết lập là: " << XorKSetBits(arr, n, k); 
    return 0; 
}

Kết quả chạy chương trình

XOR của các phần tử mảng với 3 bit thiết lập là: 44