เรียงอาร์เรย์ตามจำนวน Set Bits ใน C++

นี่คือโจทย์น่าสนใจในการเรียงอาร์เรย์ตาม set-bits เมื่อองค์ประกอบในอาร์เรย์มี set-bits มากกว่า จะวางไว้หน้าองค์ประกอบที่มี set-bits น้อยกว่า สมมติเลขคือ 12, 15, 7 set bits คือจำนวน 1 ใน binary คือ 1100 (12), 1111 (15), 0111 (7) หลังเรียงจะได้ −

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

เราต้องหาจำนวน set-bits ก่อน แล้วใช้ sort ของ C++ STL พร้อม logic การเปรียบเทียบจาก set-bit counts

อัลกอริทึม

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