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[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

Leave a Comment