How to Sort List by Hamming Weight in C++?

You are given a lists of non-negative integers nums. Sort the list in ascending order by the number of 1s in binary representation for each number. If there are ties in the number of 1s, then break ties by their value in ascending order.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [3, 1, 4, 7]
Output
[1, 4, 3, 7]
Explanation
1 and 4 both have one 1s but 1 comes earlier since it has lower value. 3 has two 1s. And 7 has three 1s.

C++ Custom Sort by Hamming Weight

The Hamming Weight is the number of 1’s bit. We can define that as a local function, and sort by the function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

vector<int> sortByHammingWeight(vector<int>& nums) {
    function<int(int)> hamming = [](int v) {
        int ans = 0;
        while (v > 0) {
            ans ++;
            v -= v & (-v);
        }
        return ans;
    };
    sort(begin(nums), end(nums), [&](auto &a, auto &b) {
        auto aa = hamming(a);
        auto bb = hamming(b);
        return (aa < bb) || (aa == bb) && (a < b);
    });
    return nums;
}

vector<int> sortByHammingWeight(vector<int>& nums) {
    function<int(int)> hamming = [](int v) {
        int ans = 0;
        while (v > 0) {
            ans ++;
            v -= v & (-v);
        }
        return ans;
    };
    sort(begin(nums), end(nums), [&](auto &a, auto &b) {
        auto aa = hamming(a);
        auto bb = hamming(b);
        return (aa < bb) || (aa == bb) && (a < b);
    });
    return nums;
}

Compiler intrinsics are built-in functions provided by the compiler that share a one-to-one, or many-to-one, relationship with specific instructions.

The C++ has inbuilt compiler intrinsics the __builtin_popcount to count the number of set bits in a integer.

1
2
3
4
5
6
7
8

vector<int> sortByHammingWeight(vector<int>& nums) {
    sort(begin(nums), end(nums), [&](auto &a, auto &b) {
        auto aa = __builtin_popcount(a);
        auto bb = __builtin_popcount(b);
        return (aa < bb) || (aa == bb) && (a < b);
    });
    return nums;
}

vector<int> sortByHammingWeight(vector<int>& nums) {
    sort(begin(nums), end(nums), [&](auto &a, auto &b) {
        auto aa = __builtin_popcount(a);
        auto bb = __builtin_popcount(b);
        return (aa < bb) || (aa == bb) && (a < b);
    });
    return nums;
}

Sorting has time complexity is O(NLogN).

Hamming Weight / Hamming Distance Algorithms

Here are the posts related to Hamming Distance (XOR, The number of different bits):

• A faster approach to count set bits in a 32-bit integer
• Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1’s Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

–EOF (The Ultimate Computing & Technology Blog) —