Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Bit Manipulation

Count Set Bits

Easy · Bit Manipulation · Asked at Amazon, Microsoft, Cisco, TCS, Infosys

Print the number of 1 bits in the binary representation of n.

Input

One integer n.

Output

The number of set bits.

Constraints

n & (n − 1) removes the lowest set bit.

Example 1

Input

11

Output

3

Example 2

Input

128

Output

1

Hints

  1. Checking all 64 bits works. Can you loop only as many times as there are 1 bits?
  2. n & (n − 1) clears the lowest set bit. Count how many times you can do that before n becomes 0.

Approach

Brian Kernighan's trick: subtracting 1 flips the lowest set bit and every 0 below it, so n & (n − 1) removes exactly that lowest 1. Repeat until n is 0 and count the steps. That's one iteration per set bit. Built-ins exist too: __builtin_popcountll, Long.bitCount, bin(n).count("1").

Complexity: O(number of set bits) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    int count = 0;
    while (n) {
        n &= n - 1;  // clear the lowest set bit
        count++;
    }
    cout << count << "\n";
    return 0;
}

Python solution

n = int(input())
count = 0
while n:
    n &= n - 1  # clear the lowest set bit
    count += 1
print(count)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int count = 0;
        while (n != 0) {
            n &= n - 1;  // clear the lowest set bit
            count++;
        }
        System.out.println(count);
    }
}

Solve Count Set Bits online · All practice problems