Dados dos enteros positivos L y R , la tarea es contar el número total de bits establecidos en la representación binaria de todos los números de L a R .
Ejemplos:
Entrada: L = 3, R = 5
Salida: 5
Explicación: (3) 10 = (11) 2, (4) 10 = (100) 2, (5) 10 = (101) 2
Por lo tanto, el conjunto total de bits está en el rango 3 a 5 es 5Entrada: L = 10, R = 15
Salida: 17
Método 1: enfoque ingenuo: la idea es ejecutar un bucle de L a R y sumar el recuento de bits establecidos en todos los números de L a R.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count set bits in x
unsigned int
countSetBitsUtil(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 N
unsigned 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 Code
int 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 approach
class GFG{
// Function to count set bits in x
static 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 N
static 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 Code
public 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 x
def 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 N
def 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 Code
if __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 approach
using System;
class GFG{
// Function to count set bits in x
static 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 N
static 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 Code
public 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 x
function 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 N
function 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 R
var L = 3, R = 5;
// Function Call
document.write("Total set bit count is "+
countSetBits(L, R));
// This code is contributed by noob2000.
</script>
Producción:
Total set bit count is 5
Complejidad de tiempo: O(N*Log N)
Espacio auxiliar: O(1)
Método 2: mejor enfoque: la idea es observar los bits desde el extremo derecho a la distancia i , luego los bits se invierten después de la posición 2 i en secuencia vertical.
Ejemplo:
L = 3, R = 5 0 = 0000 1 = 0001 2 = 0010 3 = 0011 4 = 0100 5 = 0101
Observe el bit más a la derecha (i = 0) los bits se invierten después de ( 2 0 = 1)
Observe el tercer bit más a la derecha (i = 2) los bits se invierten después de ( 2 2 = 4).
Por lo tanto, podemos contar los bits de forma vertical, de modo que en la i-ésima posición a la derecha, los bits se voltearán después de 2 i iteraciones .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the set bits
// from 0 to N
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 = 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 Code
int 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 approach
import java.util.*;
class GFG{
// Function that counts the set bits
// from 0 to N
static 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 Code
public 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 N
def 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 Code
if __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 approach
using System;
class GFG{
// Function that counts the set bits
// from 0 to N
static 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 Code
public 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 N
function 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 R
var L = 3, R = 5;
// Function Call
document.write( "Total set bit count is "
+ countSetBits(L, R) );
</script>
Producción:
Total set bit count is 5
Complejidad de tiempo: O((L + R)*K), donde K es el número de bits en L y R.
Espacio auxiliar: O(1)
Método 3: engañoso Si el número de entrada tiene la forma 2 b – 1 , por ejemplo, 1, 3, 7, 15, etc., el número de bits establecidos es b * 2 (b-1) . Esto se debe a que para todos los números del 0 al 2 b – 1 , si complementa y voltea la lista, termina con la misma lista (la mitad de los bits están establecidos y la mitad de los bits no están establecidos).
Si el número no tiene todos los bits establecidos, entonces sea m la posición del bit establecido más a la izquierda. El número de bits establecidos en esa posición es n – (1 << m) + 1 . Los bits establecidos restantes se dividen en dos partes:
- Los bits en las posiciones (m – 1) hasta el punto donde el bit más a la izquierda se convierte en 0
- Los 2 (m – 1) números debajo de ese punto, que es la forma cerrada arriba.
Por ejemplo: N = 6
0|0 0 0|0 1 0|1 0 0|1 1 -|-- 1|0 0 1|0 1 1|1 0
De lo anterior tenemos:
- El bit establecido más a la izquierda está en la posición 2 (las posiciones se consideran a partir de 0).
- Si enmascaramos eso, lo que queda es 2 (el «1 0» en la parte derecha de la última fila), entonces el número de bits en la segunda posición (el cuadro inferior izquierdo) es 3 (es decir, 2 + 1) .
- Los bits establecidos de 0-3 (el cuadro superior derecho arriba) es 2*2 (2 – 1) = 4.
- El cuadro en la parte inferior derecha son los bits restantes que aún no hemos contado y es el número de bits establecidos para todos los números hasta 2 (el valor de la última entrada en el cuadro inferior derecho) que se puede calcular recursivamente.
A continuación se muestra la implementación del enfoque anterior:
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 0
unsigned 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 n
unsigned 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 M
unsigned 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 n
unsigned 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 R
int countSetBits(int L, int R)
{
return abs(countSetBit(R)
- countSetBit(L - 1));
}
// Driver Code
int 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 approach
import java.util.*;
class GFG{
// Returns position of leftmost set bit
// The rightmost position is taken as 0
static 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 n
static 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 n
static 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 M
static 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 R
static int countSetBits(int L, int R)
{
return Math.abs(countSetBit(R) -
countSetBit(L - 1));
}
// Driver Code
public 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 0
def 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 n
def 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 n
def 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 M
def _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 R
def countSetBits(L, R):
return abs(countSetBit(R) - countSetBit(L - 1));
# Driver Code
if __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 approach
using System;
class GFG{
// Returns position of leftmost set bit
// The rightmost position is taken as 0
static 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 n
static 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 n
static 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 M
static 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 R
static int countSetBits(int L, int R)
{
return Math.Abs(countSetBit(R) -
countSetBit(L - 1));
}
// Driver Code
public 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 0
function 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 n
function 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 n
function 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 M
function _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 R
function countSetBits(L, R)
{
return Math.abs(countSetBit(R) -
countSetBit(L - 1));
}
// Driver Code
// Given L and R
var L = 3, R = 5;
// Function call
document.write("Total set bit count is " +
countSetBits(L, R));
</script>
Producción:
Total set bit count is 5
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Método 4 – usando setbit: en el método setbit, cuente uno por uno los bits establecidos de cada número en el rango L a R usando el último bit, verifique hasta el último bit y, si está configurado, aumente el conteo y finalmente sume.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to count set bit in range
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 Code
int 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 approach
class GFG{
// Function to count set bit in range
static 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 Code
public 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 range
def 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 Code
if __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 approach
using System;
class GFG{
// Function to count set bit in range
static 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 Code
public 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 range
function 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 R
let L = 3, R = 5;
// Function Call
document.write("Total set Bit count is " +
countSetBits(L, R));
// This code is contributed by shivanisinghss2110
</script>
Producción:
Total set Bit count is 5
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)
Método 5: uso de la función STL __builtin_popcount() : STL proporciona una función incorporada para contar un bit en un número entero, así que llame a esa función para cada número en el rango L a R y cuente los bits establecidos.
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 Code
int 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 approach
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 += Integer.bitCount(i);
}
return count;
}
// Driver Code
public 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 Code
if __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 approach
using 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 Code
public 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 R
let L = 3, R = 5;
// Function Call
document.write("Total set bit count is " +
countSetBits(L, R));
// This code is contributed by shivanisinghss2110
</script>
Producción:
Total set bit count is 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por thakurabhaysingh445 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA