cyberangles blog

Print first n numbers with exactly two set bits

In the realm of bit manipulation in computer programming, a common and interesting problem is to find and print the first n numbers that have exactly two set bits. A set bit refers to a bit position in the binary representation of a number that has a value of 1. This problem not only tests your understanding of binary numbers but also your ability to use bitwise operations effectively.

In this blog post, we will explore different approaches to solve this problem, understand the underlying concepts, and provide code examples in Python.

2026-07

Table of Contents#

  1. What are set bits?
  2. Understanding the problem
  3. Naive Approach
  4. Optimized Approach
  5. Python Code Implementation
  6. Complexity Analysis
  7. Example Usage
  8. Best Practices
  9. Conclusion
  10. References

What are set bits?#

In binary representation, a bit can either be 0 or 1. When a bit has a value of 1, it is called a set bit. For example, the number 5 in binary is 101, which has two set bits. We will be interested in finding numbers that have exactly two such set bits in their binary representation.

Understanding the problem#

The problem requires us to find the first n positive integers that have exactly two set bits in their binary representation. To solve this problem, we need to have a way to count the number of set bits in a number and then iterate through positive integers until we find n numbers that meet the criteria.

Naive Approach#

The naive approach to solve this problem involves iterating through positive integers starting from 1. For each number, we count the number of set bits in its binary representation. If the count is equal to 2, we add the number to our result list. We continue this process until we have found n such numbers.

Here is the general algorithm:

  1. Initialize an empty result list.
  2. Start iterating from 1.
  3. For each number, count the number of set bits using a loop or a pre - defined function.
  4. If the number of set bits is 2, add the number to the result list.
  5. Stop when the result list has n elements.

Optimized Approach#

An optimized approach leverages the fact that a number with exactly two set bits can be written in the form (1 << i) | (1 << j), where i < j. We can generate all possible pairs (i, j) and calculate the corresponding numbers.

Here is the general algorithm:

  1. Initialize an empty result list.
  2. Use two nested loops to generate all pairs (i, j) where i ranges from 0 to a sufficient value and j ranges from i + 1 to a sufficient value.
  3. For each pair (i, j), calculate the number num = (1 << i) | (1 << j).
  4. Add the number to the result list.
  5. Stop when the result list has n elements.

Python Code Implementation#

def naive_print_two_set_bits(n):
    result = []
    num = 1
    while len(result) < n:
        set_bit_count = bin(num).count('1')
        if set_bit_count == 2:
            result.append(num)
        num += 1
    return result
 
def optimized_print_two_set_bits(n):
    result = []
    i = 0
    while len(result) < n:
        for j in range(i + 1, 32):  # 32 - bit integer range
            num = (1 << i) | (1 << j)
            result.append(num)
            if len(result) == n:
                break
        i += 1
    return result

Complexity Analysis#

Naive Approach#

  • Time Complexity: The time complexity of the naive approach is $O(k log k)$, where $k$ is the $n$-th number with exactly two set bits. In the worst case, we may need to check a large number of integers to find n numbers with exactly two set bits.
  • Space Complexity: The space complexity is $O(n)$ because we need to store n numbers in the result list.

Optimized Approach#

  • Time Complexity: The time complexity of the optimized approach is $O(n)$ because we directly generate the numbers with exactly two set bits without checking unnecessary numbers.
  • Space Complexity: The space complexity is $O(n)$ because we need to store n numbers in the result list.

Example Usage#

n = 5
print("Naive Approach:", naive_print_two_set_bits(n))
print("Optimized Approach:", optimized_print_two_set_bits(n))

Best Practices#

  • Use Bitwise Operations: Bitwise operations are generally faster than converting a number to its binary string representation and then counting the set bits. The optimized approach uses bitwise operations to directly generate the numbers.
  • Understand the Problem Constraints: If the problem has constraints on the range of numbers, use them to optimize your solution. In our case, we used a 32 - bit integer range in the optimized approach.

Conclusion#

In this blog post, we learned how to find and print the first n numbers with exactly two set bits. We explored a naive approach and an optimized approach, implemented them in Python, and analyzed their time and space complexities. By using bitwise operations, we were able to come up with an efficient solution to the problem.

References#