Sort Integers by The Number of 1 Bits

Sort Integers by The Number of 1 Bits

What is this problem about?

This problem is a classic bit manipulation and sorting challenge. You are given an array of integers, and you need to sort them in ascending order based on the number of "1" bits (set bits) in their binary representation.

If two or more integers have the same number of set bits, they should be sorted in ascending order of their numerical value. For example, the number 7 in binary is 111 (three 1s), while 8 is 1000 (one 1). In the sorted output, 8 would come before 7.

Why is this asked in interviews?

Tech companies like Google, Amazon, and J.P. Morgan ask this to test two fundamental skills: bit manipulation and custom sorting. It requires you to know how to count bits efficiently (e.g., using Brian Kernighan’s algorithm or built-in functions) and how to apply those counts within a sort function. It’s a great "Medium-Easy" question that checks if a candidate knows their "bits and bytes."

Algorithmic pattern used

The algorithmic pattern used is Bit Manipulation combined with a Custom Sort Key.

1. Counting Bits: You can count set bits by repeatedly using n & (n - 1), which removes the lowest set bit, or by using language-specific functions like bin(n).count('1') or Integer.bitCount(n).
2. Sorting: Sort the array using a key that produces a tuple or a custom comparison: (bit_count, original_value). This naturally handles the tie-breaking rule.

Example explanation

Input: [0, 1, 2, 3, 4, 5, 6, 7, 8]

• 0: bits=0. -> [0]
• 1: bits=1.
• 2: bits=1.
• 4: bits=1.
• 8: bits=1. -> [1, 2, 4, 8] (sorted numerically)
• 3: bits=2.
• 5: bits=2.
• 6: bits=2. -> [3, 5, 6] (sorted numerically)
• 7: bits=3. -> [7] Final Result: [0, 1, 2, 4, 8, 3, 5, 6, 7].

Common mistakes candidates make

A common mistake is incorrectly counting the bits, perhaps by using a loop that checks every bit up to 32, which is slower than necessary. Another error is not implementing the numerical tie-breaker correctly, leading to incorrect ordering for numbers with the same bit count. Some candidates also forget that the original numbers must be preserved in the output, not replaced by their bit counts.

Interview preparation tip

Mastering the "Sort Integers by The Number of 1 Bits coding problem" involves knowing your language's bit manipulation toolkit. Practice Brian Kernighan’s algorithm (count += 1; n &= (n-1)) as it is a common follow-up question in interviews. Also, be prepared to discuss the time complexity of your sorting algorithm, which remains $O(N \log N)$ even with the bit counting overhead.