Given two positive integers L and R, the task is to count the total number of set bits in the binary representation of all the numbers from L to R.
Examples:
Input: L = 3, R = 5
Output: 5
Explanation: (3)10 = (11)2, (4)10 = (100)2, (5)10 = (101)2
So, Total set bit in range 3 to 5 is 5Input: L = 10, R = 15
Output: 17
Method 1 – Naive Approach: The idea is to run a loop from L to R and sum the count of set bits in all numbers from L to R.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count set bits in xunsigned intcountSetBitsUtil(unsigned int x){ // Base Case if (x <= 0) return 0; // Recursive Call return ((x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2));}// Function that returns count of set bits// present in all numbers from 1 to Nunsigned int countSetBits(unsigned int L, unsigned int R){ // Initialize the result int bitCount = 0; for (int i = L; i <= R; i++) { bitCount += countSetBitsUtil(i); } // Return the setbit count return bitCount;}// Driver Codeint main(){ // Given L and R int L = 3, R = 5; // Function Call printf("Total set bit count is %d", countSetBits(L, R)); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count set bits in xstatic int countSetBitsUtil(int x){ // Base Case if (x <= 0) return 0; // Recursive Call return ((x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2));}// Function that returns count of set bits// present in all numbers from 1 to Nstatic int countSetBits(int L, int R){ // Initialize the result int bitCount = 0; for (int i = L; i <= R; i++) { bitCount += countSetBitsUtil(i); } // Return the setbit count return bitCount;}// Driver Codepublic static void main(String[] args){ // Given L and R int L = 3, R = 5; // Function Call System.out.printf("Total set bit count is %d", countSetBits(L, R));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to count set bits in xdef countSetBitsUtil(x): # Base Case if (x < 1): return 0; # Recursive Call if (x % 2 == 0): return 0; else: return 1 + (countSetBitsUtil(x / 2));# Function that returns count of set bits# present in all numbers from 1 to Ndef countSetBits(L, R): # Initialize the result bitCount = 0; for i in range(L, R + 1): bitCount += countSetBitsUtil(i); # Return the setbit count return bitCount;# Driver Codeif __name__ == '__main__': # Given L and R L = 3; R = 5; # Function Call print("Total set bit count is ", countSetBits(L, R));# This code is contributed by Princi Singh |
C#
// C# program for the above approachusing System;class GFG{// Function to count set bits in xstatic int countSetBitsUtil(int x){ // Base Case if (x <= 0) return 0; // Recursive Call return ((x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2));}// Function that returns count of set bits// present in all numbers from 1 to Nstatic int countSetBits(int L, int R){ // Initialize the result int bitCount = 0; for (int i = L; i <= R; i++) { bitCount += countSetBitsUtil(i); } // Return the setbit count return bitCount;}// Driver Codepublic static void Main(String[] args){ // Given L and R int L = 3, R = 5; // Function Call Console.Write("Total set bit count is {0}", countSetBits(L, R));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to count set bits in xfunction countSetBitsUtil(x){ // Base Case if (x <= 0) return 0; // Recursive Call return ((x % 2 == 0 ? 0 : 1) + countSetBitsUtil(parseInt(x / 2)));}// Function that returns count of set bits// present in all numbers from 1 to Nfunction countSetBits(L, R){ // Initialize the result var bitCount = 0; for (var i = L; i <= R; i++) { bitCount += countSetBitsUtil(i); } // Return the setbit count return bitCount;}// Driver Code// Given L and Rvar L = 3, R = 5;// Function Calldocument.write("Total set bit count is "+ countSetBits(L, R));// This code is contributed by noob2000.</script> |
Output:
Total set bit count is 5
Time Complexity: O(N*Log N)
Auxiliary Space: O(1)
Method 2 – Better Approach: The idea is to observe bits from the rightmost side at distance i then bits get inverted after 2i position in vertical sequence.
Example:
L = 3, R = 5 0 = 0000 1 = 0001 2 = 0010 3 = 0011 4 = 0100 5 = 0101
Observe the right most bit (i = 0) the bits get flipped after (20 = 1)
Observe the 3rd rightmost bit (i = 2) the bits get flipped after (22 = 4).
Therefore, We can count bits in vertical fashion such that at i’th right most position bits will be get flipped after 2i iteration.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that counts the set bits// from 0 to Nint countSetBit(int n){ int i = 0; // To store sum of set bits from 0 - N int ans = 0; // Until n >= to 2^i while ((1 << i) <= n) { // This k will get flipped after // 2^i iterations bool k = 0; // Change is iterator from 2^i to 1 int change = 1 << i; // This will loop from 0 to n for // every bit position for (int j = 0; j <= n; j++) { ans += k; if (change == 1) { // When change = 1 flip the bit k = !k; // Again set change to 2^i change = 1 << i; } else { change--; } } // Increment the position i++; } return ans;}// Function that counts the set bit// in the range (L, R)int countSetBits(int L, int R){ // Return the count return abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codeint main(){ // Given L and R int L = 3, R = 5; // Function Call cout << "Total set bit count is " << countSetBits(L, R) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that counts the set bits// from 0 to Nstatic int countSetBit(int n){ int i = 0; // To store sum of set bits from 0 - N int ans = 0; // Until n >= to 2^i while ((1 << i) <= n) { // This k will get flipped after // 2^i iterations boolean k = true; // Change is iterator from 2^i to 1 int change = 1 << i; // This will loop from 0 to n for // every bit position for (int j = 0; j <= n; j++) { ans += k==true?0:1; if (change == 1) { // When change = 1 flip the bit k = !k; // Again set change to 2^i change = 1 << i; } else { change--; } } // Increment the position i++; } return ans;}// Function that counts the set bit// in the range (L, R)static int countSetBits(int L, int R){ // Return the count return Math.abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codepublic static void main(String[] args){ // Given L and R int L = 3, R = 5; // Function Call System.out.print("Total set bit count is " + countSetBits(L, R) +"\n");}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach# Function that counts the set bits# from 0 to Ndef countSetBit(n): i = 0; # To store sum of set bits from 0 - N ans = 0; # Until n >= to 2^i while ((1 << i) <= n): # This k will get flipped after # 2^i iterations k = True; # Change is iterator from 2^i to 1 change = 1 << i; # This will loop from 0 to n for # every bit position for j in range(n+1): ans += 0 if k == True else 1; if (change == 1): # When change = 1 flip the bit k = False if k == True else True; # Again set change to 2^i change = 1 << i; else: change -=1; # Increment the position i += 1; return ans;# Function that counts the set bit# in the range (L, R)def countSetBits(L, R): # Return the count return abs(countSetBit(R) - countSetBit(L - 1));# Driver Codeif __name__ == '__main__': # Given L and R L = 3; R = 5; # Function Call print("Total set bit count is ", countSetBits(L, R));# This code is contributed by Rajput-Ji |
C#
// C# program for the above approachusing System;class GFG{// Function that counts the set bits// from 0 to Nstatic int countSetBit(int n){ int i = 0; // To store sum of set bits from 0 - N int ans = 0; // Until n >= to 2^i while ((1 << i) <= n) { // This k will get flipped after // 2^i iterations bool k = true; // Change is iterator from 2^i to 1 int change = 1 << i; // This will loop from 0 to n for // every bit position for (int j = 0; j <= n; j++) { ans += k==true?0:1; if (change == 1) { // When change = 1 flip the bit k = !k; // Again set change to 2^i change = 1 << i; } else { change--; } } // Increment the position i++; } return ans;}// Function that counts the set bit// in the range (L, R)static int countSetBits(int L, int R){ // Return the count return Math.Abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codepublic static void Main(String[] args){ // Given L and R int L = 3, R = 5; // Function Call Console.Write("Total set bit count is " + countSetBits(L, R) +"\n");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach// Function that counts the set bits// from 0 to Nfunction countSetBit(n){ var i = 0; // To store sum of set bits from 0 - N var ans = 0; // Until n >= to 2^i while ((1 << i) <= n) { // This k will get flipped after // 2^i iterations var k = 0; // Change is iterator from 2^i to 1 var change = 1 << i; // This will loop from 0 to n for // every bit position for (var j = 0; j <= n; j++) { ans += k; if (change == 1) { // When change = 1 flip the bit k = !k; // Again set change to 2^i change = 1 << i; } else { change--; } } // Increment the position i++; } return ans;}// Function that counts the set bit// in the range (L, R)function countSetBits(L, R){ // Return the count return Math.abs(countSetBit(R) - countSetBit(L - 1));}// Driver Code// Given L and Rvar L = 3, R = 5;// Function Calldocument.write( "Total set bit count is " + countSetBits(L, R) );</script> |
Output:
Total set bit count is 5
Time Complexity: O((L + R)*K), where K is the number of bits in L and R.
Auxiliary Space: O(1)
Method 3 – Tricky If the input number is of form 2b – 1 e.g., 1, 3, 7, 15, … etc, the number of set bits is b * 2(b-1). This is because for all the numbers 0 to 2b – 1, if you complement and flip the list you end up with the same list (half the bits are set and half bits are unset).
If the number does not have all set bits, then let m is the position of the leftmost set bit. The number of set bits in that position is n – (1 << m) + 1. The remaining set bits are in two parts:
- The bits in the (m – 1) positions down to the point where the leftmost bit becomes 0
- The 2(m – 1) numbers below that point, which is the closed form above.
For Example: N = 6
0|0 0 0|0 1 0|1 0 0|1 1 -|-- 1|0 0 1|0 1 1|1 0
From the above we have:
- The leftmost set bit is in position 2 (positions are considered starting from 0).
- If we mask that off what remains is 2 (the “1 0” in the right part of the last row), So the number of bits in the 2nd position (the lower left box) is 3 (that is, 2 + 1).
- The set bits from 0-3 (the upper right box above) is 2*2(2 – 1) = 4.
- The box in the lower right is the remaining bits we haven’t yet counted and is the number of set bits for all the numbers up to 2 (the value of the last entry in the lower right box) which can be figured recursively.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;unsigned int countSetBit(unsigned int n);// Returns position of leftmost set bit// The rightmost position is taken as 0unsigned int getLeftmostBit(int n){ int m = 0; while (n > 1) { n = n >> 1; m++; } return m;}// Function that gives the position of// previous leftmost set bit in nunsigned int getNextLeftmostBit(int n, int m){ unsigned int temp = 1 << m; while (n < temp) { temp = temp >> 1; m--; } return m;}// Function to count the set bits between// the two numbers N and Munsigned int _countSetBit(unsigned int n, int m){ // Base Case if (n == 0) return 0; // Get position of next leftmost set bit m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1 if (n == ((unsigned int)1 << (m + 1)) - 1) return (unsigned int)(m + 1) * (1 << m); // Update n for next recursive call n = n - (1 << m); return ((n + 1) + countSetBit(n) + m * (1 << (m - 1)));}// Function that returns count of set// bits present in all numbers from 1 to nunsigned int countSetBit(unsigned int n){ // Get the position of leftmost set // bit in n int m = getLeftmostBit(n); // Use the position return _countSetBit(n, m);}// Function that counts the set bits// between L and Rint countSetBits(int L, int R){ return abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codeint main(){ // Given L and R int L = 3, R = 5; // Function Call cout << "Total set bit count is " << countSetBits(L, R); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Returns position of leftmost set bit// The rightmost position is taken as 0static int getLeftmostBit(int n){ int m = 0; while (n > 1) { n = n >> 1; m++; } return m;}// Function that gives the position of// previous leftmost set bit in nstatic int getNextLeftmostBit(int n, int m){ int temp = 1 << m; while (n < temp) { temp = temp >> 1; m--; } return m;}// Function that returns count of set// bits present in all numbers from 1 to nstatic int countSetBit( int n){ // Get the position of leftmost set // bit in n int m = getLeftmostBit(n); // Use the position return _countSetBit(n, m);}// Function to count the set bits between// the two numbers N and Mstatic int _countSetBit(int n, int m){ // Base Case if (n == 0) return 0; // Get position of next leftmost set bit m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1 if (n == (( int)1 << (m + 1)) - 1) return ( int)(m + 1) * (1 << m); // Update n for next recursive call n = n - (1 << m); return ((n + 1) + countSetBit(n) + m * (1 << (m - 1)));}// Function that counts the set bits// between L and Rstatic int countSetBits(int L, int R){ return Math.abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codepublic static void main(String[] args){ // Given L and R int L = 3, R = 5; // Function Call System.out.print("Total set bit count is " + countSetBits(L, R));}}// This code is contributed by sapnasingh4991 |
Python3
# Python program for the above approach# Returns position of leftmost set bit# The rightmost position is taken as 0def getLeftmostBit(n): m = 0; while (n > 1): n = n >> 1; m += 1; return m;# Function that gives the position of# previous leftmost set bit in ndef getNextLeftmostBit(n, m): temp = 1 << m; while (n < temp): temp = temp >> 1; m -=1; return m;# Function that returns count of set# bits present in all numbers from 1 to ndef countSetBit(n): # Get the position of leftmost set # bit in n m = getLeftmostBit(n); # Use the position return _countSetBit(n, m);# Function to count the set bits between# the two numbers N and Mdef _countSetBit(n, m): # Base Case if (n == 0): return 0; # Get position of next leftmost set bit m = getNextLeftmostBit(n, m); # If n is of the form 2^x-1 if (n == int(1 << (m + 1)) - 1): return int(m + 1) * (1 << m); # Update n for next recursive call n = n - (1 << m); return ((n + 1) + countSetBit(n) + m * (1 << (m - 1)));# Function that counts the set bits# between L and Rdef countSetBits(L, R): return abs(countSetBit(R) - countSetBit(L - 1));# Driver Codeif __name__ == '__main__': # Given L and R L = 3; R = 5; # Function Call print("Total set bit count is " , countSetBits(L, R));# This code contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{// Returns position of leftmost set bit// The rightmost position is taken as 0static int getLeftmostBit(int n){ int m = 0; while (n > 1) { n = n >> 1; m++; } return m;}// Function that gives the position of// previous leftmost set bit in nstatic int getNextLeftmostBit(int n, int m){ int temp = 1 << m; while (n < temp) { temp = temp >> 1; m--; } return m;}// Function that returns count of set// bits present in all numbers from 1 to nstatic int countSetBit(int n){ // Get the position of leftmost set // bit in n int m = getLeftmostBit(n); // Use the position return _countSetBit(n, m);}// Function to count the set bits between// the two numbers N and Mstatic int _countSetBit(int n, int m){ // Base Case if (n == 0) return 0; // Get position of next leftmost set bit m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1 if (n == (( int)1 << (m + 1)) - 1) return ( int)(m + 1) * (1 << m); // Update n for next recursive call n = n - (1 << m); return ((n + 1) + countSetBit(n) + m * (1 << (m - 1)));}// Function that counts the set bits// between L and Rstatic int countSetBits(int L, int R){ return Math.Abs(countSetBit(R) - countSetBit(L - 1));}// Driver Codepublic static void Main(String[] args){ // Given L and R int L = 3, R = 5; // Function call Console.Write("Total set bit count is " + countSetBits(L, R));}}// This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach// Returns position of leftmost set bit// The rightmost position is taken as 0function getLeftmostBit(n){ var m = 0; while (n > 1) { n = n >> 1; m++; } return m;}// Function that gives the position of// previous leftmost set bit in nfunction getNextLeftmostBit(n, m){ var temp = 1 << m; while (n < temp) { temp = temp >> 1; m--; } return m;}// Function that returns count of set// bits present in all numbers from 1 to nfunction countSetBit(n){ // Get the position of leftmost set // bit in n var m = getLeftmostBit(n); // Use the position return _countSetBit(n, m);}// Function to count the set bits between// the two numbers N and Mfunction _countSetBit(n, m){ // Base Case if (n == 0) return 0; // Get position of next leftmost set bit m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1 if (n == (1 << (m + 1)) - 1) return (m + 1) * (1 << m); // Update n for next recursive call n = n - (1 << m); return ((n + 1) + countSetBit(n) + m * (1 << (m - 1)));}// Function that counts the set bits// between L and Rfunction countSetBits(L, R){ return Math.abs(countSetBit(R) - countSetBit(L - 1));}// Driver Code// Given L and Rvar L = 3, R = 5;// Function calldocument.write("Total set bit count is " + countSetBits(L, R));</script> |
Output:
Total set bit count is 5
Time Complexity: O(log N)
Auxiliary Space: O(1)
Method 4 – using setbit: In setbit method count one by one set bit of each number in range L to R using last bit, check to last bit and if it is set then increase the count and finally sum up over it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to count set bit in rangeint countSetBits(int L, int R){ // Count variable int count = 0; for (int i = L; i <= R; i++) { // Find the set bit in Nth number int n = i; while (n > 0) { // If last bit is set count += (n & 1); // Left sift by one bit n = n >> 1; } } // Return count return count;}// Driver Codeint main(){ // Given Range L and R int L = 3, R = 5; // Function Call cout << "Total set Bit count is " << countSetBits(L, R); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to count set bit in rangestatic int countSetBits(int L, int R){ // Count variable int count = 0; for (int i = L; i <= R; i++) { // Find the set bit in Nth number int n = i; while (n > 0) { // If last bit is set count += (n & 1); // Left sift by one bit n = n >> 1; } } // Return count return count;} // Driver Codepublic static void main(String[] args){ // Given Range L and R int L = 3, R = 5; // Function Call System.out.print("Total set Bit count is " + countSetBits(L, R));}}// This code is contributed by Ritik Bansal |
Python3
# Python3 program for the above approach# Function to count set bit in rangedef countSetBits(L, R): # Count variable count = 0; for i in range(L, R + 1): # Find the set bit in Nth number n = i; while (n > 0): # If last bit is set count += (n & 1); # Left sift by one bit n = n >> 1; # Return count return count;# Driver Codeif __name__ == '__main__': # Given range L and R L = 3; R = 5; # Function call print("Total set Bit count is ", countSetBits(L, R)); # This code is contributed by Amit Katiyar |
C#
// C# program for the above approachusing System;class GFG{// Function to count set bit in rangestatic int countSetBits(int L, int R){ // Count Variable int count = 0; for(int i = L; i <= R; i++) { // Find the set bit in Nth number int n = i; while (n > 0) { // If last bit is set count += (n & 1); // Left sift by one bit n = n >> 1; } } // Return count return count;}// Driver Codepublic static void Main(String[] args){ // Given Range L and R int L = 3, R = 5; // Function Call Console.Write("Total set Bit count is " + countSetBits(L, R));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach // Function to count set bit in rangefunction countSetBits(L, R){ // Count variable let count = 0; for(let i = L; i <= R; i++) { // Find the set bit in Nth number let n = i; while (n > 0) { // If last bit is set count += (n & 1); // Left sift by one bit n = n >> 1; } } // Return count return count;} // Driver Code// Given Range L and Rlet L = 3, R = 5;// Function Calldocument.write("Total set Bit count is " + countSetBits(L, R));// This code is contributed by shivanisinghss2110</script> |
Output:
Total set Bit count is 5
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Method 5 – Using STL __builtin_popcount() function: STL provides an inbuilt function for counting set a bit in an integer, so here call that function for every number in range L to R and count set bits.
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to count set bit in [L, R]int countSetBits(int L, int R){ // Variable for count set // bit in range int count = 0; // Count set bit for all // number in range for (int i = L; i <= R; i++) { // Use inbuilt function count += __builtin_popcount(i); } return count;}// Driver Codeint main(){ // Given range L and R int L = 3, R = 5; // Function Call cout << "Total set bit count is " << countSetBits(L, R); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count set bit in [L, R]static int countSetBits(int L, int R){ // Variable for count set // bit in range int count = 0; // Count set bit for all // number in range for (int i = L; i <= R; i++) { // Use inbuilt function count += Integer.bitCount(i); } return count;}// Driver Codepublic static void main(String[] args){ // Given range L and R int L = 3, R = 5; // Function Call System.out.print("Total set bit count is " + countSetBits(L, R));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to count set bit in [L, R]def countSetBits(L, R): # Variable for count set # bit in range count = 0; # Count set bit for all # number in range for i in range(L, R + 1): # Use inbuilt function count += countSetBit(i); return count;def countSetBit(n): count = 0 while (n): count += n & 1 n >>= 1 return count # Driver Codeif __name__ == '__main__': # Given range L and R L = 3; R = 5; # Function Call print("Total set bit count is " , countSetBits(L, R));# This code is contributed by sapnasingh4991 |
C#
// C# program for the above approachusing System;class GFG{// Function to count set bit in [L, R]static int countSetBits(int L, int R){ // Variable for count set // bit in range int count = 0; // Count set bit for all // number in range for (int i = L; i <= R; i++) { // Use inbuilt function count += countSetBits(i); } return count;}static int countSetBits(long x){ int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;}// Driver Codepublic static void Main(String[] args){ // Given range L and R int L = 3, R = 5; // Function Call Console.Write("Total set bit count is " + countSetBits(L, R));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to count set bit in [L, R]function countSetBits(L, R){ // Variable for count set // bit in range let count = 0; // Count set bit for all // number in range for(let i = L; i <= R; i++) { // Use inbuilt function count = Number(i.toString().split("").sort()); } return count;}// Driver Code// Given range L and Rlet L = 3, R = 5;// Function Calldocument.write("Total set bit count is " + countSetBits(L, R));// This code is contributed by shivanisinghss2110</script> |
Output:
Total set bit count is 5
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
