Cuente el número de bits establecidos en un rango usando el conjunto de bits

Dado un número binario grande. La tarea es contar el número de 1 en un rango dado de L a R (indexación basada en 1).
Ejemplos:
 

Entrada: s = “101101011010100000111”, L = 6, R = 15 
Salida: 5 
s [L : R] = “1011010100” 
Solo hay 5 bits establecidos.
Entrada: s = “10110”, L = 2, R = 5 
Salida: 2 
 

Acercarse: 
 

• Convierta la string de tamaño len al conjunto de bits de tamaño N .
• No hay necesidad de (N – len) + (L – 1) bits en el lado izquierdo y (N – R) bits en el lado derecho del conjunto de bits.
• Elimine esos bits de manera eficiente utilizando la operación bit a bit de desplazamiento a la izquierda y a la derecha.
• Ahora hay todos ceros en el lado izquierdo de L y en el lado derecho de R, así que solo use la función count() para obtener el conteo de 1 en el conjunto de bits, ya que todas las posiciones excepto [L, R] son ​​’0′.

A continuación se muestra la implementación del enfoque anterior: 
 

// 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;
}

# 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# 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 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

2

Complejidad de tiempo: O (len)

Espacio Auxiliar: O(len)