Count Total Set Bits in 1..N 🎯

Welcome to our deep dive into the fascinating world of Data Structures and Algorithms! Today, we're going to explore a fun problem that will help you understand one of the essential concepts in algorithms: Bitwise Operations. Specifically, we'll learn how to count the total set bits in the numbers from 1 to N. Let's get started!

What are Set Bits and Why are They Important? 💡

A set bit in a binary number is a 1 that appears in the binary representation of the number. For example, in the binary representation of the number 11 (1011 in base 2), we have three set bits (1s).

Counting set bits is an essential skill for programmers, as it often appears in various algorithms and data structures, such as Bloom Filters, Hamming Distance, and more.

Understanding the Problem: Counting Set Bits in 1..N 📝

In this lesson, we'll learn how to write a function that counts the total number of set bits in all numbers from 1 to N, where N is a given positive integer.

Let's break down the problem into smaller, more manageable pieces.

Step 1: Counting Set Bits for a Single Number 🎯

First, we'll learn how to count the set bits for a single number. This will lay the groundwork for counting set bits for a range of numbers.

python

def count_set_bits(n):
    # Initialize counter
    count = 0

    # Iterate through the binary representation of the number
    while n > 0:
        # If the least significant bit is 1, increment the counter
        if n & 1 == 1:
            count += 1

        # Shift the number right by one bit
        n = n >> 1

    return count

💡 Pro Tip: In the line n = n >> 1, we are right-shifting the number by one bit. This is equivalent to dividing the number by 2.

Step 2: Counting Set Bits for a Range of Numbers 🎯

Now that we can count set bits for a single number, we can extend this concept to a range of numbers. To count set bits for all numbers from 1 to N, we'll simply call the count_set_bits function for each number in the range and sum the results.

python

def count_set_bits_in_range(n):
    total = 0

    # Iterate through the numbers from 1 to N
    for i in range(1, n + 1):
        total += count_set_bits(i)

    return total

📝 Note: The count_set_bits_in_range function assumes that the input n is a positive integer, as we are interested in counting set bits for numbers from 1 to N.

Step 3: Testing Our Solution 🎯

Finally, let's test our implementation to make sure it works as expected.

python

print(count_set_bits_in_range(5))  # Output: 15
print(count_set_bits_in_range(10)) # Output: 45

Challenge: Extend the Solution 🎯

Now that you've mastered the basics, can you extend the solution to count the number of set bits in a list of numbers?