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

For example,

Input10Output2Input15Output4ExplainationThe 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**

- Let N be the input number.
- Set counter = 0.
- 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.

- 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[40];
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**

- Program to find the sum of even digits of an integer
- Left-Shift array elements by 1 in C/C++
- Program to swap the first half and second half of the array