How do you count the number of set bits in a number?

In one line

The rule

The number of set bits in a number is the count of 1s in its binary representation.

There is no single formula, but the common method is:

• Keep dividing the number by 2 and count how many times the remainder is 1.

Let's understand it simply

Imagine you have a number, like 13. In binary, 13 is 1101. Each digit is either a 1 (set bit) or a 0 (unset bit).

Think of each 1 as a light bulb that is ON. You just need to count how many bulbs are glowing. For 1101, three bulbs are ON, so there are 3 set bits.

How it works

1. Start with your number (let's say 13).
2. Check the last digit (rightmost bit) by dividing by 2 and looking at the remainder.
3. If the remainder is 1, add 1 to your count.
4. Divide the number by 2 (ignore the remainder).
5. Repeat steps 2–4 until the number becomes 0.

The story behind it

Counting set bits is important in computer science. It is used in many areas like error checking, cryptography, and digital electronics. The method is simple but powerful. Programmers often use it to check how many features are ON in a device, or how many permissions a user has.

Where you see it in real life

• Digital clocks: Each segment is ON or OFF (1 or 0). Counting ON segments uses set bits.
• Permissions in computers: Read, write, execute permissions are stored as bits. Counting set bits tells how many permissions are given.
• Cricket scoreboards: Electronic boards use bits to show numbers. Counting set bits helps in checking errors.
• Traffic lights: Each light (red, yellow, green) can be ON or OFF, stored as bits.
• Mobile phone settings: Features like WiFi, Bluetooth, GPS are ON/OFF, stored as bits.

Why it matters

• Used in error detection and correction in computers.
• Helps in optimizing programs (faster calculations).
• Needed in competitive programming and coding interviews.
• Used in hardware design (like microcontrollers and chips).

Worked example

Let's count set bits in the number 13:

Given: number = 13
Step 1: 13 divided by 2 = 6, remainder = 1 (count = 1)
Step 2: 6 divided by 2 = 3, remainder = 0 (count = 1)
Step 3: 3 divided by 2 = 1, remainder = 1 (count = 2)
Step 4: 1 divided by 2 = 0, remainder = 1 (count = 3)
Step 5: Number is now 0, stop.
Final answer: 13 has 3 set bits.

Common mistakes

• Forgetting to check the remainder each time (must check if it's 1).
• Stopping before the number becomes 0 (must continue till 0).
• Confusing set bits (1s) with unset bits (0s).

Remember it

Count the 1s in the binary form — each 1 is a set bit.