根据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