Count number of set bits in a range using bitset

0 0 4 minutes read

Given a large binary number.The task is to count the number of 1’s in a given range from L to R (1 based indexing).
Examples:

Input : s = “101101011010100000111”, L = 6, R = 15
Output : 5
s [L : R] = “1011010100”
There is only 5 set bits.
Input : s = “10110”, L = 2, R = 5
Output : 2

Approach:

Convert the string of size len to the bitset of size N.
There is no need of (N – len) + (L – 1) bits in the left side and (N – R) bits in the right side of the bitset .
Remove those bits efficiently using left and right shift bitwise operation.
Now there are all zeroes in the left side of L and right side of R, so just use count() function to get the count of 1’s in the bitset as all positions except [L, R] are ‘0’.

Below is the implementation of above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define N 32
 
// C++ function to count 
// number of 1's using bitset
int GetOne(string s, int L, int R)
{
 
    int len = s.length();
 
    // Converting the string into bitset
    bitset<N> bit(s);
 
    // Bitwise operations
    // Left shift
    bit <<= (N - len + L - 1);
 
    // Right shifts
    bit >>= (N - len + L - 1);
    bit >>= (len - R);
 
    // Now bit has only those bits
    // which are in range [L, R]
 
    // return count of one in [L, R]
    return bit.count();
}
 
// Driver code
int main()
{
 
    string s = "01010001011";
 
    int L = 2, R = 4;
 
    cout << GetOne(s, L, R);
 
    return 0;
}

Java

// Java implementation of above approach
public class Main {
    static final int N = 32;
 
    // Function to count
    // the number of 1's using a bit string
    static int getOne(String s, int L, int R) {
        int len = s.length();
 
        // Converting s to an N-bit representation
        s = "0".repeat(Math.max(0, N - len)) + s;
 
        // Extracting bits of the range [L, R]
        String bit = s.substring(N - R, N - L + 1);
 
        // Now bit has only those bits
        // which are in the range [L, R]
 
        // Return the count of '1's in [L, R]
        return (int) bit.chars().filter(c -> c == '1').count();
    }
 
    // Driver code
    public static void main(String[] args) {
        String s = "01010001011";
 
        int L = 2, R = 4;
 
        // Function Call
        System.out.println(getOne(s, L, R));
    }
}

Python3

# Python3 implementation of above approach 
 
N = 32
 
# function for converting binary
# string into integer value
def binStrToInt(binary_str):
    length = len(binary_str)
    num = 0
    for i in range(length):
        num = num + int(binary_str[i])
        num = num * 2
    return num / 2
 
 
# function to count 
# number of 1's using bitset 
def GetOne(s, L, R) : 
 
    length = len(s); 
 
    # Converting the string into bitset 
    bit = s.zfill(32-len(s));
     
    bit = int(binStrToInt(bit))
 
    # Bitwise operations 
    # Left shift 
    bit <<= (N - length + L - 1); 
 
    # Right shifts 
    bit >>= (N - length + L - 1); 
    bit >>= (length - R); 
 
    # Now bit has only those bits 
    # which are in range [L, R] 
 
    # return count of one in [L, R] 
    return bin(bit).count('1'); 
 
 
# Driver code 
if __name__ == "__main__" : 
 
    s = "01010001011"; 
 
    L = 2; R = 4; 
 
    print(GetOne(s, L, R)); 
     
# This code is contributed by AnkitRai01

C#

// C# implementation of above approach
using System;
using System.Linq;
 
class GFG {
  static int N = 32;
 
  // C# function to count
  // number of 1's using bit string
  static int GetOne(string s, int L, int R)
  {
 
    int len = s.Length;
 
    // Converting s to an N bit representation
    s = s.PadLeft(N, '0');
 
    // Extracting bits of the range [L, R]
    string bit = s.Substring(N - R, R - L + 1);
 
    // Now bit has only those bits
    // which are in range [L, R]
 
    // return count of one in [L, R]
    return bit.Count(f => (f == '1'));
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    string s = "01010001011";
 
    int L = 2, R = 4;
 
    // Function Call
    Console.WriteLine(GetOne(s, L, R));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript implementation of above approach
 
var N = 32;
 
// function for converting binary
// string into integer value
function binStrToInt(binary_str)
{
    var length = binary_str.length;
    var num = 0;
    for (var i = 0; i < length; i++) {
        num = num + parseInt(binary_str[i]);
        num = num * 2;
    }
    return num / 2;
}
 
// function to count
// number of 1's using bitset
function GetOne(s, L, R)
{
 
    var length = s.length;
 
    // Converting the string into bitset
    var bit = "0" * (32 - length) + s;
 
    bit = parseInt(binStrToInt(bit));
 
    // Bitwise operations
    // Left shift
    bit <<= (N - length + L - 1);
 
    // Right shifts
    bit >>= (N - length + L - 1);
    bit >>= (length - R);
 
    // Now bit has only those bits
    // which are in range [L, R]
 
    // return count of one in [L, R]
    return bit.toString(2).split("1").length - 1;
}
 
var s = "01010001011";
 
var L = 2;
var R = 4;
 
console.log(GetOne(s, L, R));
 
 
//This code is contributed by phasing17

Output

Time Complexity: O(len)

Auxiliary Space: O(len)

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 zambiatek!