C++ Count set bits in an integer














































C++ Count set bits in an integer



Count Set Bits

Write an efficient program to count number of 1s in binary representation of an integer.

Examples :

Input : n = 64
Output : 1
Binary representation of 64 is 1000000 and has 1 set bit

Input : n = 13
Output : 3
Binary representation of 13 is 1101 and has 3 set bits



Set bits in a binary number is represented by 1. So, the digit 1 is known as set bit in the terms of the computer.

Unset bits in a binary number is represented by 0. So, the digit 0 is known as unset bit in the terms of the computer.


In this below C++ Program, we are reading the unsigned integer using 'n' variable. Using while loop count the number of bits set to one using bitwise operations.

If condition statement is used to check the value which copies a bit to the result if it exists in both operands using Binary AND operator is not equal to 0. If the condition is true, then execute the statement and increment the number of bits set to 1 using count variable.

Using Binary Right Shift Operator, the left operand's value is moved right by the number of bits specified by the right operands and assign the value to 'n' variable. Hence we are displaying the output of the program. Print the count of the number of bits set to one using bitwise operations.


CODE

//C++ program for finding the number of set bits
#include<iostream>
using namespace std;
/*Funtion for counting the Set Bits*/
int countSetBits(int n)
{
//initially the count is Zero(0)
int count=0;
while(n!=0)
{
//main condition to check whether the particular bit is Set or Not
if((n&1)!=0)
count++;
n=n>>
1; //right shift on bit
}
return count;
}
/*Driver Code*/
int main()
{
int n;
cin>>n;

cout<<"Number of Set bits in "<<n<<" is "<<countSetBits(n);
return 0;
}

OUTPUT
CASE #1
Number of Set bits in 64 is 1
CASE #2
Number of Set bits in 15 is 4
Time Complexity of this Approach is O(n)
Space Complexity of this Approach is O(1)



More Articles of Shaik Ismail:

Name Views Likes
C++ Shutdown Using C++ Code 384 1
C++ Majority Element (LeetCode) 328 0
C++ Missing Number(LeetCode) 155 0
C++ Count set bits in an integer 551 0
C++ Power of Two Leetcode BitManipulation 446 0
C++ Single Number LeetCode Bit Manipulation 214 0
C++ Radix Sort 186 0
C++ Wave Sort 161 0
C++ Counting Sort 155 0
C++ DNF Algorithm for Sorting 0,1,2 320 0
C++ Merge Sort 157 0
C++ Quick Sort 232 0
C++ Insertion Sort 153 0
C++ Selection Sort 167 0
C++ Bubble Sort 204 0
C++ DFS for a Graph 182 0
C++ BFS in Graph 197 0
C++ Graph Representation (Adjacency list) 160 0
C++ Graph Representation 181 0
C++ Basics of Graph Data Structure 162 0
C++ Diameter of a Binary Tree 193 0
C++ Check if a binary tree is a BST or not 493 0
C++ Heap Sort 364 0
C++ Deletion in Heaps 380 0
C++ Insertion of Elements in Heap 157 0
C++ Basics of Heap Data Structure 152 0
C++ Deletion in AVL Trees 138 0
C++ AVL Rotations 238 0
C++ AVL Tree 144 0
C++ Deletion of Nodes in BST 494 0
C++ Kth Largest Element in BST 149 0
C++ Kth Smallest Element in BST 175 0
C++ Searching in BST 137 0
C++ Insertion of Nodes in BST 138 0
C++ Basics of BST Part - 1 337 0
C++ Binary Tree is a SumTree or Not 122 0
C++ Sum of all leaf nodes 126 0
C++ Identical Binary Trees 132 0
C++ Mirror Binary Tree 190 0
CPP Project or program to get six subjects marks of a student and then calculate its total, average and percentage and display them on the screen 145 0
C++ Lowest Common Ancestor 143 0
C++ Bottom View of a Binary Tree 183 0
C++ Top View of a Binary Tree 131 0
C++ Vertical Order Traversal of a Binary Tree 198 0
C++ Level Order Traversal of a Binary Tree 172 0
C++ Height of the Binary Tree (Code) 131 0
C++ Binary Tree Representation and Traversals (Code) 169 1
C++ Binary Tree 135 0
C++ Basics of Tree Data Structure PART - 2 147 0
Tree 133 1
Basics of Tree Data Structure PART - 1 98 0

Comments