Sắp xếp một mảng theo số lượng các bit đã đặt trong C ++

Ở đây chúng ta sẽ thấy một vấn đề thú vị để sắp xếp một mảng dựa trên các bit thiết lập. Khi một phần tử trong mảng có số lượng bit tập hợp cao hơn, thì phần tử đó sẽ được đặt trước một phần tử khác có số lượng bit tập hợp thấp hơn. Giả sử một số số là 12, 15, 7. Vì vậy, các bit thiết lập về cơ bản là số 1 trong biểu diễn nhị phân của chúng. Đó là 1100 (12), 1111 (15) và 0111 (7). Vì vậy, sau khi sắp xếp nó sẽ như thế này -

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

Ở đây chúng ta phải tìm số bit set lúc đầu. Sau đó, chúng ta sẽ sử dụng hàm sắp xếp STL của C ++ để sắp xếp chúng. Chúng ta phải tạo logic so sánh dựa trên số lượng bit đã đặt

Thuật toán

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

Ví dụ

#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] << " ";
   }
}

Đầu ra

15 7 9 3 5 6 2 4 8