Sắp xếp mảng theo số bit 1 (set bits) trong C++

Sắp xếp mảng dựa trên số bit 1 (set bits) trong biểu diễn nhị phân. Phần tử có nhiều bit 1 hơn sẽ đứng trước.

Ví dụ: 12 (1100), 15 (1111), 7 (0111). Sau sắp xếp: 15, 7, 12.

Cách làm: đếm số bit 1 của mỗi số, dùng std::sort với comparator dựa trên số bit 1.

Thuật toán

demBit1(so):
    Bắt đầu
        count := 0
        trong khi so != 0, làm
            nếu so AND 1 = 1, thì tăng count
            so = dịch phải so 1 bit
        kết thúc
        trả về count
    Kết thúc

compare(num1, num2):
    Bắt đầu
        count1 = demBit1(num1)
        count2 = demBit1(num2)
        nếu count1 <= count2, trả về false, ngược lại true
    Kết thúc

Ví dụ mã C++

#include<iostream>
#include<algorithm>
using namespace std;

int demBit1(int so){
    int count = 0;
    while(so){
        if(so & 1 == 1)
            count++;
        so = so >> 1;
    }
    return count;
}

int compare(int num1, int num2){
    int count1 = demBit1(num1);
    int count2 = demBit1(num2);
    if(count1 <= count2)
        return 0;
    return 1;
}

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

Kết quả đầu ra

15 7 9 3 5 6 2 4 8