Menu
Coddy logo textTech
START LEARNING
flag En iconEnglishdown icon

Number of set-bits

Lesson 11 of 17 in Coddy's Bit Manipulation course.

First up, what are set-bits?

The digit '1' in binary numbers is known as set bit in the terms of the computer.

Here in this lesson we want to calculate,

The number of set bits present in the binary form of the given number.

For example, let's say we have a number (20)10 in binary (10100)2 , the number of set-bits present in (20)10 are 2.

Try to think of an approach. You might probably think about converting the number into it's binary form and count the number of one's, okay ,but what about large numbers? You will not be able to store them within integer datatype, how will we be able to know number of set bits in large numbers? The answer obviously bits manipulation!

  • Firstly we take a position variable let's call it pos for knowing which bit is present at a particular position in the binary number.
  • Then we do left shift pos times on '1'.
  • Then we simply do an AND operation with the given number.

How is it useful? Let's understand this with the number (20)10 -

  • For first position, pos=0. 20 & 1<<pos , 1<<pos=1 and doing AND operation on (10100)2 and (00001)2 gives us zero.
  • For second position, pos=1. 20 & 1<<pos, 1<<pos=(10)2 and doing AND operation on (10100)2 and (00010)2 gives us zero.
  • For third position, pos=2. 20 & 1<<pos, 1<<pos=(100)2 and doing AND operation on (10100)2 and (00100)2 gives us one, that is our first set bit.
  • For fourth position, pos=2. 20 & 1<<pos, 1<<pos=(1000)2 and doing AND operation on (10100)2 and (01000)2 gives us zero.
  • For third position, pos=2. 20 & 1<<pos, 1<<pos=(10000)2 and doing AND operation on (10100)2 and (10000)2 gives us one, that is second set bit.

To count the number of set bits we can keep a counter variable to count the set bits. But I hope this example makes the algorithm clear to you.

And this way we can easily calculate number of set-bits present in the binary form of a number without having to worry to go out of range of int datatype in C++.

challenge icon

Challenge

Medium

Complete the function SetBits to return number of set-bits in the given number using the above approach.

Try it yourself

#include <cmath>

int SetBits(int num) {
    // Write code here
}

All lessons in Bit Manipulation

1Introduction and basics

What is bit manipulation?Why we need bit manipulation?Binary and decimal numbersNOT & OR operatorsAND operatorXOR operatorRight and left shift operatorsBitwise Operators Summary

2Bit Algorithms

Power of 2Number occurring odd times Number of set-bits Rotate bits of a number IRotate bits of a number II

3Practice challenges

Tina and her bits assignmentXORtyFind KFind Minimum Sum