C++에서 세트 비트가 K와 동일한 배열의 모든 요소에 대한 XOR

이 문제에서는 n개의 요소와 정수 값 k의 배열이 제공됩니다. 우리의 임무는 k와 동일한 비트를 설정한 배열의 모든 요소에 대한 XOR을 찾는 것입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

array = {2, 12, 44, 103, 17} , K =3

출력

44

이 문제를 해결하기 위해 배열의 모든 요소의 세트 비트를 세고 k와 비교합니다. 설정된 비트 수가 k와 같으면 벡터로 푸시하고 벡터의 모든 요소에 대한 XOR을 찾습니다.

설정된 비트 수를 찾기 위해 __builtin_popcount()를 사용합니다. C++의 내장 함수입니다.

솔루션 구현을 보여주는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;
int XorKSetBits(int arr[], int n, int k){
   vector<int> kBitElments;
   for (int i = 0; i < n; i++) {
      if (__builtin_popcount(arr[i]) == k) {
         kBitElments.push_back(arr[i]);
      }
   }
   int result = kBitElments[0];
   for (int i = 1; i < kBitElments.size(); i++)
      result ^= kBitElments[i];
   return result;
}
int main(){
   int arr[] = { 2, 12, 44, 103, 17 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   cout<<"XOR of all element of the array with "<<k<<" set bits is : "<<XorKSetBits(arr, n, k);
   return 0;
}

출력

XOR of all element of the array with 3 set bits is : 44