How to sort an array according to set bits

Question

Sort an array by number of set bits. For example,

• Input: arr = [0,1,2,3,4,5,6,7,8]
• Output: [0,1,2,4,8,3,5,6,7]

example 2

• Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
• Output: [1,2,4,8,16,32,64,128,256,512,1024]

I tried count number of set digits in a number, after that I am stuck. I am complete beginner.

arr = [1,2,3,4,5,6]
for i in range(len(arr)):
    a = arr[i]
    count1 = 0
    while(a>0):
        d = int(a/2)
        s =  a%2
        a = d
        #print(s, end=" ")
        if s == 1:
            count1+=1
    print(arr[i],count1)

Answer 1

To sort an array by the number of set bits in each element, you can use sorted function with a custom key function that counts the number of set bits in each element.

arr = [0,1,2,3,4,5,6,7,8]

def count_set_bits(num):
    count = 0
    while(num > 0):
        if num % 2 == 1:
            count += 1
        num = num // 2
    return count

sorted_arr = sorted(arr, key=count_set_bits)
print(sorted_arr)

Answer 2

Here are two versions that work if all of your given values are of type int, as in your examples:

Python 3.10 or later

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
sorted_arr = sorted(arr, key=int.bit_count)
print(sorted_arr)

With the key argument, we specify how to define a custom sort order: the given function will be applied to each element in the array, and the array elements will be sorted according to the respective results. In our case, we can directly use int.bit_count(), as it counts the set bits of integers.

Earlier Python versions

With Python versions earlier than 3.10, where int.bit_count() had not yet been introduced, we can use equivalently, as suggested by int's documentation:

sorted_arr = sorted(arr, key=lambda i: bin(i).count("1"))

In this case, we cannot directly pass an existing method or function to the key argument, so we create our own on-the-fly, using a lambda function.

Answer 3

C++ code using inbuilt function

#include <bits/stdc++.h>

bool cmp(int a, int b) { return __builtin_popcount(a) > __builtin_popcount(b); }

void sortSetBitsCount(std::vector<int> &arr, int size) {
    std::stable_sort(arr.begin(), arr.end(), cmp);
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    sortSetBitsCount(arr, n);
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << ' ';
    }
    return 0;
}

Answer 4

Your examples show ordering by increasing count of bits set, and increasing value in case of equality.
Alas, Python 3 did away with Python 2's cmp parameter, so construct a tuple of sort keys in order of descending priority - (#bitsSet, value):

def order_by_bits_set_and_value(values):
    """ Return a list containing values in order of ascending number of bits set,
        ascending value in case of same number of bits set.
    """
    return sorted(values, key=lambda binary: (int.bit_count(binary), binary))

Answer 5

Here is the one way to solve this problem,

arr = [1024,512,256,128,64,32,16,8,4,2,1]

def count_set_bits(x):
    count = 0
    while x > 0:
        count += x&1
        x >>= 1
    return count

sorted_arr = sorted(arr, key=lambda x: (count_set_bits(x), x))

Time complexity: O(n)

space complexity: O(1)