Given a positive integer N, the task is to count the total number of set bits in binary representation of all the numbers from 1 to N.
Examples:
Input: N = 3
Output: 4
setBits(1) + setBits(2) + setBits(3) = 1 + 1 + 2 = 4Input: N = 6
Output: 9
Approach: Solution to this problem has been published in the Set 1 and the Set 2 of this article. Here, a dynamic programming based approach is discussed.
- Base case: Number of set bits in 0 is 0.
- For any number n: n and n>>1 has same no of set bits except for the rightmost bit.
Example: n = 11 (1011), n >> 1 = 5 (101)… same bits in 11 and 5 are marked bold. So assuming we already know set bit count of 5, we only need to take care for the rightmost bit of 11 which is 1. setBit(11) = setBit(5) + 1 = 2 + 1 = 3
Rightmost bit is 1 for odd and 0 for even number.
Recurrence Relation: setBit(n) = setBit(n>>1) + (n & 1) and setBit(0) = 0
We can use bottom-up dynamic programming approach to solve this.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// set bits in all the integers// from the range [1, n]int countSetBits(int n){ // To store the required count // of the set bits int cnt = 0; // To store the count of set // bits in every integer vector<int> setBits(n + 1); // 0 has no set bit setBits[0] = 0; for (int i = 1; i <= n; i++) { setBits[i] = setBits[i >> 1] + (i & 1); } // Sum all the set bits for (int i = 0; i <= n; i++) { cnt = cnt + setBits[i]; } return cnt;}// Driver codeint main(){ int n = 6; cout << countSetBits(n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to return the count of // set bits in all the integers // from the range [1, n] static int countSetBits(int n) { // To store the required count // of the set bits int cnt = 0; // To store the count of set // bits in every integer int[] setBits = new int[n + 1]; // 0 has no set bit setBits[0] = 0; // For the rest of the elements for (int i = 1; i <= n; i++) { setBits[i] = setBits[i >> 1] + (i & 1); } // Sum all the set bits for (int i = 0; i <= n; i++) { cnt = cnt + setBits[i]; } return cnt; } // Driver code public static void main(String[] args) { int n = 6; System.out.println(countSetBits(n)); }}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach# Function to return the count of# set bits in all the integers# from the range [1, n]def countSetBits(n): # To store the required count # of the set bits cnt = 0 # To store the count of set # bits in every integer setBits = [0 for x in range(n + 1)] # 0 has no set bit setBits[0] = 0 # For the rest of the elements for i in range(1, n + 1): setBits[i] = setBits[i // 2] + (i & 1) # Sum all the set bits for i in range(0, n + 1): cnt = cnt + setBits[i] return cnt# Driver coden = 6print(countSetBits(n))# This code is contributed by Sanjit Prasad |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the count of // set bits in all the integers // from the range [1, n] static int countSetBits(int n) { // To store the required count // of the set bits int cnt = 0; // To store the count of set // bits in every integer int[] setBits = new int[n + 1]; // 0 has no set bit setBits[0] = 0; // 1 has a single set bit setBits[1] = 1; // For the rest of the elements for (int i = 2; i <= n; i++) { // If current element i is even then // it has set bits equal to the count // of the set bits in i / 2 if (i % 2 == 0) { setBits[i] = setBits[i / 2]; } // Else it has set bits equal to one // more than the previous element else { setBits[i] = setBits[i - 1] + 1; } } // Sum all the set bits for (int i = 0; i <= n; i++) { cnt = cnt + setBits[i]; } return cnt; } // Driver code static public void Main() { int n = 6; Console.WriteLine(countSetBits(n)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of// set bits in all the integers// from the range [1, n]function countSetBits(n){ // To store the required count // of the set bits var cnt = 0; // To store the count of set // bits in every integer var setBits = Array.from( {length: n + 1}, (_, i) => 0); // 0 has no set bit setBits[0] = 0; // 1 has a single set bit setBits[1] = 1; // For the rest of the elements for(i = 2; i <= n; i++) { // If current element i is even then // it has set bits equal to the count // of the set bits in i / 2 if (i % 2 == 0) { setBits[i] = setBits[i / 2]; } // Else it has set bits equal to one // more than the previous element else { setBits[i] = setBits[i - 1] + 1; } } // Sum all the set bits for(i = 0; i <= n; i++) { cnt = cnt + setBits[i]; } return cnt;}// Driver codevar n = 6;document.write(countSetBits(n));// This code is contributed by 29AjayKumar </script> |
Output:
9
Time Complexity: O(N), where N is the given number.
Auxiliary Space: O(N), for creating an additional array of size N + 1.
Another simple and easy-to-understand solution:
A simple easy to implement and understand solution would be not using bits operations. The solution is to directly count set bits using __builtin_popcount(). The solution is explained in code using comments.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// set bits in all the integers// from the range [1, n]int countSetBits(int n){ // To store the required count // of the set bits int cnt = 0; // Calculate set bits in each number using // __builtin_popcount() and Sum all the set bits for (int i = 1; i <= n; i++) { cnt = cnt + __builtin_popcount(i); } return cnt;}// Driver codeint main(){ int n = 6; cout << countSetBits(n); return 0;}// This article is contributed by Abhishek |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to return the count of // set bits in all the integers // from the range [1, n] static int countSetBits(int n) { // To store the required count // of the set bits int cnt = 0; // Calculate set bits in each number using // Integer.bitCount() and Sum all the set bits for (int i = 1; i <= n; i++) { cnt = cnt + Integer.bitCount(i); } return cnt; } // Driver code public static void main(String[] args) { int n = 6; System.out.print(countSetBits(n)); }}// This code is contributed by Rajput-Ji |
Python3
# Python implementation of the approach# Function to return the count of# set bits in all the integers# from the range [1, n]def countSetBits(n): # To store the required count # of the set bits cnt = 0 # Calculate set bits in each number using # Integer.bitCount() and Sum all the set bits for i in range(1, n+1): cnt = cnt + (bin(i)[2:]).count('1') return cnt# Driver codeif __name__ == '__main__': n = 6 print(countSetBits(n))# This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approachfunction bitCount (n) { n = n - ((n >> 1) & 0x55555555) n = (n & 0x33333333) + ((n >> 2) & 0x33333333) return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24} // Function to return the count of // set bits in all the integers // from the range [1, n] function countSetBits(n) { // To store the required count // of the set bits var cnt = 0; // Calculate set bits in each number using // Integer.bitCount() and Sum all the set bits for (i = 1; i <= n; i++) { cnt = cnt + bitCount(i); } return cnt; } // Driver code var n = 6; document.write(countSetBits(n));// This code is contributed by Rajput-Ji</script> |
C#
// C# implementation of the approachusing System;using System.Linq;public class GFG { // Function to return the count of // set bits in all the integers // from the range [1, n] static int countSetBits(int n) { // To store the required count // of the set bits int cnt = 0; // Calculate set bits in each number using // int.bitCount() and Sum all the set bits for (int i = 1; i <= n; i++) { cnt = cnt + (Convert.ToString(i, 2).Count( c = > c == '1')); } return cnt; } // Driver code public static void Main(String[] args) { int n = 6; Console.Write(countSetBits(n)); }}// This code is contributed by Rajput-Ji |
Output
9
Time Complexity: O(NlogN), where N is the given number.
Auxiliary Space: O(1)
Another approach : Space optimized without use of built-in function
To optimize the space of the previous approach we can avoid using a vector to store the set bits count for every integer in the range [1, n]. Instead, we can use a single variable to store the total count of set bits.
Implementation Steps:
- Initialize a variable ‘cnt’ to 0.
- Iterate from 1 to n.
- For each i, create a variable ‘x’ and set it to i.
- While x is greater than 0, do the following:
- a. If the least significant bit of x is 1, increment ‘cnt’.
- b. Right shift x by 1 bit.
- Return cnt as the count of set bits in integers from 1 to n.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// set bits in all the integers// from the range [1, n]int countSetBits(int n){ // To store the required count // of the set bits int cnt = 0; for (int i = 1; i <= n; i++) { int x = i; while (x > 0) { cnt += (x & 1); x >>= 1; } } return cnt;}// Driver codeint main(){ int n = 6; cout << countSetBits(n); return 0;} |
Java
// Java code addition import java.util.*;public class Main { // Function to return the count of // set bits in all the integers // from the range [1, n] public static int countSetBits(int n) { // To store the required count // of the set bits int cnt = 0; for (int i = 1; i <= n; i++) { int x = i; while (x > 0) { cnt += (x & 1); x >>= 1; } } return cnt; } // Driver code public static void main(String[] args) { int n = 6; System.out.println(countSetBits(n)); }}// The code is contributed by Nidhi goel. |
Python
# Function to return the count of# set bits in all the integers# from the range [1, n]def countSetBits(n): # To store the required count # of the set bits cnt = 0 for i in range(1, n+1): x = i while x > 0: cnt += (x & 1) x >>= 1 return cnt# Driver coden = 6print(countSetBits(n)) |
Javascript
// JavaScript code to return the count of set bits in all the integers from the range [1, n]function countSetBits(n) { // To store the required count of the set bits let cnt = 0; for (let i = 1; i <= n; i++) { let x = i; while (x > 0) { cnt += (x & 1); x >>= 1; } } return cnt;}// Driver codelet n = 6;console.log(countSetBits(n)); |
C#
using System;class GFG { // Function to return the count of // set bits in all the integers // from the range [1, n] public static int CountSetBits(int n) { // To store the required count // of the set bits int cnt = 0; for (int i = 1; i <= n; i++) { int x = i; while (x > 0) { cnt += (x & 1); x >>= 1; } } return cnt; } // Driver code public static void Main(string[] args) { int n = 6; Console.WriteLine(CountSetBits(n)); }} |
Output
9
Time Complexity: O(NlogN), where N is the given number.
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
