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