Count Number of Set Bits

Given a non-negative integer n, your task is to count the number of set bits (1s) in its binary representation.

For example, the number 13 has binary form 1101, which contains three set bits. The expected output is 3.

Understanding the Problem

We are given a non-negative integer n. Our goal is to count how many set bits (1s) are present in its binary representation. A set bit is simply a bit with a value of 1.

For example, the number 13 in binary is 1101. It has three set bits: the first, third, and fourth bits from the right.

So, for input n = 13, the output should be 3.

Step-by-Step Solution with Example

step 1: Understand the core idea

We'll use Brian Kernighan’s Algorithm to count the set bits efficiently. This algorithm relies on a clever bit manipulation trick: n & (n - 1) clears the rightmost set bit of n.

Each time we perform this operation, we reduce the number of set bits by one. We repeat the process and count how many times it happens before n becomes zero.

step 2: Initialize variables

We start with count = 0. This will keep track of how many set bits we have encountered so far.

step 3: Work through an example — n = 13

The binary of 13 is 1101.

• n = 13. Binary: 1101. Count = 0
• Apply n = n & (n - 1) → n = 13 & 12 → 1101 & 1100 = 1100 → n = 12. Count = 1
• Apply n = 12 & 11 → 1100 & 1011 = 1000 → n = 8. Count = 2
• Apply n = 8 & 7 → 1000 & 0111 = 0000 → n = 0. Count = 3

At this point, n becomes 0, so we stop. The final count is 3.

step 4: Return the result

Return count as the final answer. For n = 13, the output is 3.

Edge Cases

• n = 0: The binary representation is 0. No set bits. Output should be 0.
• n = 1: Binary is 1. One set bit. Output should be 1.
• Large n (e.g., 1023): Binary is 1111111111 (10 ones). Output should be 10.

We do not need to handle negative numbers, since the input is guaranteed to be non-negative.

Final Thoughts

This problem introduces a very efficient bit manipulation technique that reduces runtime significantly compared to checking every bit individually. The n & (n - 1) trick ensures that the loop runs only as many times as there are set bits.

It’s a great way for beginners to practice binary representations and understand how to manipulate bits smartly using bitwise operators.

1. Initialize a counter variable count to 0.
2. While n is not equal to 0:
• Update n as n & (n - 1). This operation removes the rightmost set bit.
• Increment count.
3. Once n becomes 0, return count.

#include <stdio.h>

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1); // remove rightmost set bit
        count++;
    }
    return count;
}

int main() {
    unsigned int number = 13;
    printf("Number of set bits in %u: %d\n", number, countSetBits(number));
    return 0;
}

#include <iostream>
using namespace std;

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1); // remove rightmost set bit
        count++;
    }
    return count;
}

int main() {
    unsigned int number = 13;
    cout << "Number of set bits in " << number << ": " << countSetBits(number) << endl;
    return 0;
}

def count_set_bits(n: int) -> int:
    count = 0
    while n:
        n = n & (n - 1)  # remove rightmost set bit
        count += 1
    return count

number = 13
print(f"Number of set bits in {number}: {count_set_bits(number)}")

public class CountSetBits {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // remove rightmost set bit
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int number = 13;
        System.out.println("Number of set bits in " + number + ": " + countSetBits(number));
    }
}

function countSetBits(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // remove rightmost set bit
    count++;
  }
  return count;
}

const number = 13;
console.log(`Number of set bits in ${number}: ${countSetBits(number)}`);

package main

import "fmt"

func countSetBits(n uint) int {
    count := 0
    for n != 0 {
        n = n & (n - 1) // remove rightmost set bit
        count++
    }
    return count
}

func main() {
    number := uint(13)
    fmt.Printf("Number of set bits in %d: %d\n", number, countSetBits(number))
}

fn count_set_bits(mut n: u32) -> u32 {
    let mut count = 0;
    while n != 0 {
        n = n & (n - 1); // remove rightmost set bit
        count += 1;
    }
    count
}

fn main() {
    let number = 13;
    println!("Number of set bits in {}: {}", number, count_set_bits(number));
}

fun countSetBits(n: Int): Int {
    var count = 0
    var num = n
    while (num != 0) {
        num = num and (num - 1) // remove rightmost set bit
        count++
    }
    return count
}

fun main() {
    val number = 13
    println("Number of set bits in $number: ${countSetBits(number)}")
}

func countSetBits(_ n: Int) -> Int {
    var count = 0
    var num = n
    while num != 0 {
        num = num & (num - 1) // remove rightmost set bit
        count += 1
    }
    return count
}

let number = 13
print("Number of set bits in \(number): \(countSetBits(number))")

function countSetBits(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // remove rightmost set bit
    count++;
  }
  return count;
}

const number = 13;
console.log(`Number of set bits in ${number}: ${countSetBits(number)}`);

Time complexity

Space complexity

O(1)

The algorithm uses only a constant amount of extra space — a counter variable and the input integer n. No additional data structures are used.