C++에서 설정된 비트 수에 따라 배열 정렬

여기서 우리는 세트 비트를 기반으로 배열을 정렬하는 흥미로운 문제를 볼 것입니다. 배열의 요소에 더 많은 수의 세트 비트가 있는 경우 해당 요소는 더 적은 수의 세트 비트를 가진 다른 요소 앞에 배치됩니다. 어떤 숫자가 12, 15, 7이라고 가정합니다. 따라서 세트 비트는 기본적으로 이진 표현에서 1의 숫자입니다. 1100(12), 1111(15), 0111(7)입니다. 그래서 정렬 후에는 다음과 같이 보일 것입니다 -

1111, 0111, 1100 (15, 7, 12)

여기서 우리는 처음에 세트 비트의 수를 찾아야 합니다. 그런 다음 C++ STL 정렬 기능을 사용하여 정렬합니다. 세트 비트 수를 기반으로 비교 논리를 만들어야 합니다.

알고리즘

getSetBitCount(number):
Begin
   count := 0
   while number is not 0, do
      if number AND 1 = 1, then
         increase count by 1
      number = right shift number by one bit
   done
   return count
End
compare(num1, num2):
Begin
   count1 = getSetBitCount(num1)
   count2 = getSetBitCount(num2)
   if count1 <= count2, then return false, otherwise return true
End

예시

#include<iostream>
#include<algorithm>
using namespace std;
int getSetBitCount(int number){
   int count = 0;
   while(number){
      if(number & 1 == 1)
      count++;
      number = number >> 1 ; //right shift the number by one bit
   }
   return count;
}
int compare(int num1, int num2){
   int count1 = getSetBitCount(num1);
   int count2 = getSetBitCount(num2);
   if(count1 <= count2)
   return 0;
   return 1;
}
main(){
   int data[] = {2, 9, 4, 3, 5, 7, 15, 6, 8};
   int n = sizeof(data)/sizeof(data[0]);
   sort(data, data + n, compare);
   for(int i = 0; i<n; i++){
      cout << data[i] << " ";
   }
}

출력

15 7 9 3 5 6 2 4 8