Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Output
3.3.
Implementation in Java
3.3.1.
Output
3.4.
Time complexity
3.5.
Space complexity
4.
Optimized Approach
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Output
4.3.
Implementation in Java
4.3.1.
Output
4.4.
Time Complexity
4.5.
Space Complexity
5.
Using Built-in Functions
5.1.
Implementation in C++
5.1.1.
Output
5.2.
Implementation in Java
5.2.1.
Output
5.3.
Time Complexity
5.4.
Space Complexity
6.
Frequently Asked Questions
6.1.
What do C++'s bitwise operators do?
6.2.
What is the bitwise operator's time and space complexity?
6.3.
Can we use the left shift and right shift for negative numbers?
6.4.
How can we quickly check if a number is even or odd?
6.5.
What is Bitwise XOR?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Total Set Bits in an Array

Author Sahil Setia
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

It sometimes becomes necessary to consider data at the bit level. We must work with each data bit separately. We may also need to turn on/off specific data bits to make our task more manageable; we use binary operators. Bitwise operations can be considered an essential topic of Data Structures and Algorithms. 

title image

In this blog, we will discuss a fundamental and common problem of binary numbers: counting the total number of set bits in an array in the binary representation of each integer. Before diving into the solution, let’s look at the problem statement again. 

Problem Statement

The main task is to count the total number of 1’s in the Array's binary representation of each integer. Simply put, the mission is to find the total number of 1’s(set bits) of each array integer. 

Input

Total number of elements in the array = 5

Given array = [15, 11, 6, 4, 9]

Output

12

Explanation

The total number of set bits in 15 is equal to 4.

Explanation image 1

The total number of set bits in 11 is equal to 3.

Explanation image 2

The total number of set bits in 6 is equal to 2.

Explanation image 3

The total number of set bits in 4 is equal to 1.

Explanation image 4

The total number of set bits in 9 is equal to 2.

Explanation image 5

Therefore, the total number of set bits in the array equals = 4 + 3 + 2 + 1 + 2 = 12, which is displayed as the output.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Brute Force Approach

There are numerous approaches to solving this problem, and there are infinite ways of implementing this problem. This problem is the basic building block of the bitwise algorithms, and we will see some common yet effective ways to solve this problem.

For each number in the array, the naive approach uses a simple loop and a right shift operator and considers every integer bit. A counter is maintained subsequently to keep track of the number of set bits.

This means we go through all the bits of the number and check whether it is set by performing AND operation(with 1). There will be two possibilities which are as follows:

  • 1 AND 1 (Right-most bit) = 1
  • 1 AND 0 (Right-most bit) = 0
     

The solution is simple. Here, we traverse the array once, count the set bits in each number and add it to the answer.

For counting the number of set bits in a number, check if the last bit of the number is 1 or not, and keep shifting the number towards the right each time until the number becomes 0.

Algorithm

  1. Call the ‘solve()’ function to find the array's total number of set bits.
     
  2. Traverse the array, and for each number in the array, call the ‘count_bits()’ function for the corresponding number ‘N’, where ‘N’ is the input of which the total set bits must be counted.
     
  3. Initialize a ‘total’ variable to store the count of the total set bits in the integer.
     
  4. Use a while loop with the condition till ‘N’ is greater than zero and do the following:
    1. Take AND of the number ‘N’ with 1 to check if the rightmost bit is set and increment the ‘total’ if the bit is set.
       
    2. Shift the number to the right using the right shift operator.
       
  5. Finally, return the ‘total’ from the ‘count_bits()’ function and add it to the variable ‘ans’, which stores the total number of set bits in the array.
     
  6. After traversing through the array, return the ‘ans’ from the ‘solve()’ function and display it as the output.

Implementation in C++

/* 
    C++ program to count the number of set bits 
    in the given array.
*/

#include <iostream>
#include <vector>
using namespace std;

// Function which calculates the set bits of integer
int count_bits(int n){
    
    // Initialising a variable to count the total.
    int total = 0;
    
    while (n){
        
        // If the last bit is 1, increment the total
        if((n&1)>0){
            ++total;
        }

        // Right shift the value of n
        n >>= 1;
    }
    return total;
}

// Function which calculates the set bits in array
int solve(vector <int>&arr, int n){
    
    // For storing total bits in the array
    int ans = 0;
    
    // Traversing through the array
    for(int i=0;i<n;i++){
        
        ans += count_bits(arr[i]);
    }
    
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 15;
    arr[1] = 11;
    arr[2] = 6;
    arr[3] = 4;
    arr[4] = 9;
    
    // Calling the function
    cout << solve(arr,N);
    return 0;
}


Output

Output image

Implementation in Java

public class MyClass {
    
    // Function which calculates the set bits
    static int count_bits(int n){
        
        // Initialising a variable to count the total.
        int total = 0;
        
        while (n>0){
            
            // If the last bit is 1, increment the total
            if((n&1)>0){
                ++total;
            }
    
            // Right shift the value of n
            n >>= 1;
        }
        return total;
    }
    
    // Function which calculates the set bits in array
    static int solve(int arr[], int n){
        
        // For storing total bits in the array
        int ans = 0;
        
        // Traversing through the array
        for(int i=0;i<n;i++){
            
            ans += count_bits(arr[i]);
        }
        
        return ans;
    }
 
    // Driver program
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int [N];
        arr[0] = 15;
        arr[1] = 11;
        arr[2] = 6;
        arr[3] = 4;
        arr[4] = 9;
        
        // Calling the function
        System.out.println(solve(arr, N));
    }
}


Output

Output image

Time complexity

O(N * log(max(Ai))), where ‘N’ is equal to the number of elements in the array and max(Ai) means the maximum of all elements of the array.

Explanation: Here, we're traversing the array elements once. For calculating the number of set bits, since there are log(Ai) bits in a number and we are going through all the bits one by one, the time complexity of this approach is O(N * log(max(Ai))).

Space complexity

O(1)

Explanation Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Optimized Approach

The state of every bit in the number is examined to see if it is set or not. As the number is examined, all the bits of the number are iterated and Bitwise AND of the number with a power of 2’s is taken and if the result is not equal to zero, the particular bit in the position is known to be set.

The working of the AND operator is shown below in table-

AND table

Algorithm

  1. Call the ‘solve()’ function to find the total number of set bits in the array.
     
  2. Traverse the array, and for each number in the array, call the ‘count_bits()’ function for the corresponding number ‘N’ where ‘N’ is the input of which the total set bits must be counted.
     
  3. Initialize a ‘total’ variable to store the count of the total set bits in the integer.
     
  4. Use a while loop with the condition till N is greater than zero and do the following:
    1. Take AND of the number ‘N’ with 2i  where ‘i’ is the current bit to check, and if the AND is greater than zero, that means the current bit is set and increment the ‘total’ on each iteration.
       
  5. Finally, return the ‘total’ from the ‘count_bits()’ function and add it to the variable ‘ans’, which stores the total number of set bits in the array.
     
  6. After traversing through the array, return the ‘ans’ from the ‘solve()’ function and display it as the output.

Implementation in C++

/* 
    C++ program to count the number of set bits 
    in the given array.
*/

#include <iostream>
#include <vector>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
    
    // Initialising a variable count to 0.
    int total = 0;
    
    // Iterating over all the bits
    for(int i = 0 ; i < 32 ; i++){
        
        // (1<<i) corresponds to 2 raised to i
        if(n & (1<<i)){
            ++total;
        }
    }
    return total;
}

// Function which calculates the set bits in array
int solve(vector <int>&arr, int n){
    
    // For storing total bits in the array
    int ans = 0;
    
    // Traversing through the array
    for(int i=0;i<n;i++){
        
        ans += count_bits(arr[i]);
    }
    
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 15;
    arr[1] = 11;
    arr[2] = 6;
    arr[3] = 4;
    arr[4] = 9;
    
    // Calling the function
    cout << solve(arr,N);
    return 0;
}


Output

Output image

Implementation in Java

public class MyClass {
    
    // Function which calculates the set bits
    static int count_bits(int n){
        
        // Initialising a variable count to 0.
        int total = 0;
        
        // Iterating over all the bits
        for(int i = 0 ; i < 32 ; i++){
            
            // (1<<i) corresponds to 2 raised to i
            if((n & (1<<i)) > 0){
                ++total;
            }
        }
        return total;
    }
    
    // Function which calculates the set bits in the array
    static int solve(int arr[], int n){
        
        // For storing total bits in the array
        int ans = 0;
        
        // Traversing through the array
        for(int i=0;i<n;i++){
            
            ans += count_bits(arr[i]);
        }
        
        return ans;
    }
 
    // Driver program
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int [N];
        arr[0] = 15;
        arr[1] = 11;
        arr[2] = 6;
        arr[3] = 4;
        arr[4] = 9;
        
        // Calling the function
        System.out.println(solve(arr, N));
    }
}


Output

Output image

Time Complexity

O(N * 32) = O(N) 

Explanation: Since the traversal of the array takes up to O(N) time and Iterating over all the bits takes in a total of 32 iterations, i.e., constant iterations take place hence, the time complexity of the above code is O(N). 

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Using Built-in Functions

GCC provides a built-in function __builtin_popcount(N) to count the number of set bits in a positive integer, N.

Implementation in C++

/* 
    C++ program to count the number of set bits 
    in the given array.
*/

#include <iostream>
#include <vector>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
    
    // Calling the builtin pop count method
    int total = __builtin_popcount(n);
    return total;
}

// Function which calcultes the set bits in array
int solve(vector <int>&arr, int n){
    
    // For storing total bits in the array
    int ans = 0;
    
    // Traversing through the array
    for(int i=0;i<n;i++){
        
        ans += count_bits(arr[i]);
    }
    
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 15;
    arr[1] = 11;
    arr[2] = 6;
    arr[3] = 4;
    arr[4] = 9;
    
    // Calling the function
    cout << solve(arr,N);
    return 0;
}

Output

Output image

Implementation in Java

public class MyClass {
    
    // Function which calculates the set bits
    static int count_bits(int n){
        
        // Calling the builtin pop count method
        int total = Integer.bitCount(n);
        return total;
    }
    
    // Function which calculates the set bits in the array
    static int solve(int arr[], int n){
        
        // For storing total bits in the array
        int ans = 0;
        
        // Traversing through the array
        for(int i=0;i<n;i++){
            
            ans += count_bits(arr[i]);
        }
        
        return ans;
    }
 
    // Driver program
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int [N];
        arr[0] = 15;
        arr[1] = 11;
        arr[2] = 6;
        arr[3] = 4;
        arr[4] = 9;
        
        // Calling the function
        System.out.println(solve(arr, N));
    }
}


Output

Output image

Time Complexity

O(N* (Total set bits in the integer))

Explanation: Since the array, traversal takes O(N) time, and the total number of iterations will be the total number of set bits in the integer. In the worst case, all the bits will be set, and the number can have a maximum of logN bits, and the worst case complexity will be O(N* logN).

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Frequently Asked Questions

What do C++'s bitwise operators do?

Bitwise operators are the operations that change a number's bits. Bitwise operators are operations that can be used to add, subtract, or shift bits in binary quantities.

What is the bitwise operator's time and space complexity?

Bitwise operations generally operate in the time and space complexity of O(1).

Can we use the left shift and right shift for negative numbers?

Negative numbers should not be handled using the left and right shift operators. In C and C++, the result is undefined behavior if the second operand is a negative number.

How can we quickly check if a number is even or odd?

We can use & operator to check if a number is odd or even quick. For a number n, if (n & 1) yields 0, the number is even; else number is odd.

What is Bitwise XOR?

It is also called Exclusive OR. It takes two numbers as input operands and does Bitwise XOR on every corresponding bit of two numbers. If both bits are different, the bitwise OR operator returns 1. Otherwise, it produces a value of 0.

Conclusion

In this blog, we discussed a problem based on counting the number of set bits in the given array and saw the various approaches we can use to solve the problem. We saw the algorithm for the methods and implemented the solution in two different languages, C++, and Java.

Recommended Reading:

Do check out the Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Count Set Bits in Index Range [L, R] in Given Array for Q Queries
Next article
Form a Number Using Bit Rotations of N having the Same Frequency of each Digit
Live masterclass