Count Set Bits Brian Kernighan Algorithm in DSA Python - Build from Scratch

Count Set Bits using Brian Kernighan Algorithm

📖 Scenario: Imagine you are working with a system that stores numbers in binary form. You want to find out how many bits are set to 1 in a given number. This is useful in many areas like error detection, cryptography, and network programming.

🎯 Goal: You will build a small program that counts the number of set bits (1s) in the binary representation of a number using the Brian Kernighan algorithm.

📋 What You'll Learn

Create a variable to hold the number to check

Create a variable to count the set bits

Use Brian Kernighan's algorithm to count set bits

Print the count of set bits

💡 Why This Matters

🌍 Real World

Counting set bits is useful in network masks, cryptography, and error detection where binary data is processed.

💼 Career

Understanding bitwise operations and efficient algorithms is important for software engineers working with low-level data processing, embedded systems, and performance optimization.

1

Create the number variable

Create a variable called number and set it to 29.

DSA Python

# Create a variable called number and set it to 29
# Your code here

Hint

Use the assignment operator = to set number to 29.

2

Create the count variable

Create a variable called count and set it to 0 to keep track of set bits.

DSA Python

number = 29
# Create a variable called count and set it to 0
# Your code here

Hint

Initialize count to zero before counting bits.

3

Implement Brian Kernighan's algorithm

Use a while loop with the condition number != 0. Inside the loop, update number to number & (number - 1) and increment count by 1.

DSA Python

number = 29
count = 0
# Use a while loop to count set bits using Brian Kernighan's algorithm
# Your code here

Hint

Brian Kernighan's algorithm repeatedly removes the rightmost set bit until the number becomes zero.

4

Print the count of set bits

Print the value of count using print(count).

DSA Python

number = 29
count = 0
while number != 0:
    number = number & (number - 1)
    count += 1
# Print the count of set bits
# Your code here

Hint

The number 29 in binary is 11101, which has 4 set bits.