# C/C++ Program to Count the Number of Bits Set to 1 in an Integer

Write a program to count the number of bits set to 1 in an integer in C/C++.

For example,

```Input
10
Output
2

Input
15
Output
4

Explaination
The binary string of 10 is : 1010
Number of 1's in 1010 = 2

The binary string of 15 is : 1111
Number of 1's in 1111 = 4```

The problem can be solved in multiple ways. We will discuss some of them.

## Method 1

In this method, we use the fact that if a binary number is odd then its rightmost bit is 1 whereas if the number is even, then the rightmost bit is 0. We first check if the input number is divisible by 2 or not. If the number of divisible by 2, we do nothing. Whereas if the number is not divisible by 2, we increment the counter. After that, we right-shift the number and repeat the steps until the input number becomes 0.

Steps

1. Let N be the input number.
2. Set counter = 0.
3. Repeat the following steps while N > 0.
• Set r = N % 2. If N is divisible by 2, r will store 0. If N is not divisible by 2, then r will store 1.
• counter = counter + r.
• N = N / 2. Dividing N by 2 is equivalent to right-shift N by 1.
4. The number of 1’s in N is stored in counter.
``````#include <stdio.h>

int count_ones(int n) {

int counter = 0, r;

while (n > 0) {

r = n % 2;
counter = counter + r;	// r is 1 only if the right-most bit in n is 1
// if the right-most bit is 0, then r is also 0
// thus, the counter will not be affected

n = n / 2;	// right-shift n

}

return counter;

}

int main() {

int n;
printf("Enter a Number: ");
scanf("%d", &n);

printf("Number of 1's in %d = %d", n, count_ones(n));

}``````

Output

```Enter a Number: 15
Number of 1's in 15 = 4```

## Method 2

In this method, we convert the input decimal number to binary string using itoa(). After converting the input integer to a binary string, we iterate each character of the string and check for 1s.

Syntax of itoa()

``void itoa( int value, char* str, int base )``
• value: It is the decimal value we want to convert.
• str: It is the array that stores the resulting string.
• base: It is the base of the resulting string. In this question, we need to convert an integer to binary. Therefore, we will set the base to 2.
``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int count_ones(int n) {

char buffer;
int counter = 0, i;
itoa(n, buffer, 2);

for (i = 0; i < strlen(buffer); ++i) {
if (buffer[i] == '1')
++counter;
}

return counter;

}

int main() {

int n;
printf("Enter a Number: ");
scanf("%d", &n);

printf("Number of 1's in %d = %d", n, count_ones(n));

}``````

Output

``````Enter a Number: 16
Number of 1's in 16 = 1``````

## Method 3

This method is similar to method 1 but instead of loop, we use recursion to find number of 1s.

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int count_ones(int n) {

if (n == 0)
return 0;

if (n % 2 == 1)
return 1 + count_ones(n / 2);
else
return count_ones(n / 2);

}

int main() {

int n;
printf("Enter a Number: ");
scanf("%d", &n);

printf("Number of 1's in %d = %d", n, count_ones(n));

}``````

Output

``````Enter a Number: 31
Number of 1's in 31 = 5``````

Read