सी ++ में सेट बिट्स की गिनती के अनुसार एक सरणी को क्रमबद्ध करें

यहां हम सेट-बिट्स के आधार पर एक सरणी को सॉर्ट करने के लिए एक दिलचस्प समस्या देखेंगे। जब सरणी में एक तत्व में सेट-बिट्स की संख्या अधिक होती है, तो उसे दूसरे तत्व से पहले रखा जाएगा जिसमें सेट बिट्स की संख्या कम होती है। मान लीजिए कुछ संख्याएं 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