Dado un entero positivo n, cuente el número total de bits establecidos en representación binaria de todos los números del 1 al n.
Ejemplos:
Input: n = 3 Output: 4 Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13
Fuente: pregunta de la entrevista de Amazon
Método 1 (Simple)
Una solución simple es ejecutar un bucle de 1 a n y sumar el recuento de bits establecidos en todos los números de 1 a n.
C++
// A simple program to count set bits
// in all numbers from 1 to n.
#include <iostream>
using namespace std;
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x);
// Returns count of set bits present in all
// numbers from 1 to n
unsigned int countSetBits(unsigned int n)
{
int bitCount = 0; // initialize the result
for (int i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);
}
// Driver program to test above functions
int main()
{
int n = 4;
cout <<"Total set bit count is " <<countSetBits(n);
return 0;
}
// This code is contributed by shivanisinghss2110.
C
// A simple program to count set bits
// in all numbers from 1 to n.
#include <stdio.h>
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x);
// Returns count of set bits present in all
// numbers from 1 to n
unsigned int countSetBits(unsigned int n)
{
int bitCount = 0; // initialize the result
for (int i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
// A utility function to count set bits
// in a number x
unsigned int countSetBitsUtil(unsigned int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);
}
// Driver program to test above functions
int main()
{
int n = 4;
printf("Total set bit count is %d", countSetBits(n));
return 0;
}
Java
// A simple program to count set bits
// in all numbers from 1 to n.
class GFG{
// Returns count of set bits present
// in all numbers from 1 to n
static int countSetBits( int n)
{
// initialize the result
int bitCount = 0;
for (int i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
// A utility function to count set bits
// in a number x
static int countSetBitsUtil( int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) +
countSetBitsUtil(x / 2);
}
// Driver program
public static void main(String[] args)
{
int n = 4;
System.out.print("Total set bit count is ");
System.out.print(countSetBits(n));
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
# A simple program to count set bits
# in all numbers from 1 to n.
# Returns count of set bits present in all
# numbers from 1 to n
def countSetBits(n):
# initialize the result
bitCount = 0
for i in range(1, n + 1):
bitCount += countSetBitsUtil(i)
return bitCount
# A utility function to count set bits
# in a number x
def countSetBitsUtil(x):
if (x <= 0):
return 0
return (0 if int(x % 2) == 0 else 1) + countSetBitsUtil(int(x / 2))
# Driver program
if __name__=='__main__':
n = 4
print("Total set bit count is", countSetBits(n))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// A simple C# program to count set bits
// in all numbers from 1 to n.
using System;
class GFG
{
// Returns count of set bits present
// in all numbers from 1 to n
static int countSetBits( int n)
{
// initialize the result
int bitCount = 0;
for (int i = 1; i <= n; i++)
bitCount += countSetBitsUtil(i);
return bitCount;
}
// A utility function to count set bits
// in a number x
static int countSetBitsUtil( int x)
{
if (x <= 0)
return 0;
return (x % 2 == 0 ? 0 : 1) +
countSetBitsUtil(x / 2);
}
// Driver program
public static void Main()
{
int n = 4;
Console.Write("Total set bit count is ");
Console.Write(countSetBits(n));
}
}
// This code is contributed by Sam007
PHP
<?php
// A simple program to count set bits
// in all numbers from 1 to n.
// Returns count of set bits present
// in all numbers from 1 to n
function countSetBits($n)
{
$bitCount = 0; // initialize the result
for ($i = 1; $i <= $n; $i++)
$bitCount += countSetBitsUtil($i);
return $bitCount;
}
// A utility function to count
// set bits in a number x
function countSetBitsUtil($x)
{
if ($x <= 0)
return 0;
return ($x % 2 == 0 ? 0 : 1) +
countSetBitsUtil($x / 2);
}
// Driver Code
$n = 4;
echo "Total set bit count is " .
countSetBits($n);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// A simple program to count set bits
// in all numbers from 1 to n.
// Returns count of set bits present
// in all numbers from 1 to n
function countSetBits(n)
{
// initialize the result
let bitCount = 0;
for (let i = 1; i <= n; i++)
{
bitCount += countSetBitsUtil(i);
}
return bitCount;
}
// A utility function to count set bits
// in a number x
function countSetBitsUtil(x)
{
if (x <= 0)
{
return 0;
}
return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(Math.floor(x/2));
}
// Driver program
let n = 4;
document.write("Total set bit count is ");
document.write(countSetBits(n));
// This code is contributed by rag2127
</script>
Producción
Total set bit count is 5
Complejidad de tiempo: O (nLogn)
Método 2 (Simple y eficiente que el Método 1)
Si observamos los bits desde el lado derecho a la distancia i, los bits se invierten después de la posición 2^i en secuencia vertical.
por ejemplo n = 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 (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 inviertan después de 2^i iteración;
C++
#include <bits/stdc++.h>
using namespace std;
// Function which counts set bits from 0 to n
int countSetBits(int n)
{
int i = 0;
// ans store sum of set bits from 0 to n
int ans = 0;
// while n greater than equal 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) {
k = !k; // When change = 1 flip the bit
change = 1 << i; // again set change to 2^i
}
else {
change--;
}
}
// increment the position
i++;
}
return ans;
}
// Main Function
int main()
{
int n = 17;
cout << countSetBits(n) << endl;
return 0;
}
Java
public class GFG {
// Function which counts set bits from 0 to n
static int countSetBits(int n)
{
int i = 0;
// ans store sum of set bits from 0 to n
int ans = 0;
// while n greater than equal to 2^i
while ((1 << i) <= n) {
// This k will get flipped after
// 2^i iterations
boolean k = false;
// 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++) {
if (k == true)
ans += 1;
else
ans += 0;
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;
}
// Driver program
public static void main(String[] args)
{
int n = 17;
System.out.println(countSetBits(n));
}
}
// This code is contributed by Sam007.
Python3
# Function which counts set bits from 0 to n def countSetBits(n) : i = 0 # ans store sum of set bits from 0 to n ans = 0 # while n greater than equal to 2^i while ((1 << i) <= n) : # This k will get flipped after # 2^i iterations k = 0 # 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(0, n+1) : ans += k if change == 1 : # When change = 1 flip the bit k = not k # again set change to 2^i change = 1 << i else : change -= 1 # increment the position i += 1 return ans # Driver code if __name__ == "__main__" : n = 17 print(countSetBits(n)) # This code is contributed by ANKITRAI1
C#
using System;
class GFG
{
static int countSetBits(int n)
{
int i = 0;
// ans store sum of set bits from 0 to n
int ans = 0;
// while n greater than equal to 2^i
while ((1 << i) <= n) {
// This k will get flipped after
// 2^i iterations
bool k = false;
// 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++) {
if (k == true)
ans += 1;
else
ans += 0;
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;
}
// Driver program
static void Main()
{
int n = 17;
Console.Write(countSetBits(n));
}
}
// This code is contributed by Sam007
PHP
<?php
// Function which counts
// set bits from 0 to n
function countSetBits($n)
{
$i = 0;
// ans store sum of set
// bits from 0 to n
$ans = 0;
// while n greater than
// equal to 2^i
while ((1 << $i) <= $n)
{
// This k will get flipped
// after 2^i iterations
$k = 0;
// change is iterator
// from 2^i to 1
$change = 1 << $i;
// This will loop from 0 to n
// for every bit position
for ($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;
}
// Driver code
$n = 17;
echo(countSetBits($n));
// This code is contributed by Smitha
?>
Javascript
<script>
// Javascript program for the above approach
// Function which counts set bits from 0 to n
function countSetBits(n)
{
let i = 0;
// ans store sum of set bits from 0 to n
let ans = 0;
// while n greater than equal to 2^i
while ((1 << i) <= n) {
// This k will get flipped after
// 2^i iterations
let k = 0;
// change is iterator from 2^i to 1
let change = 1 << i;
// This will loop from 0 to n for
// every bit position
for (let 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;
}
// Driver Code
let n = 17;
document.write(countSetBits(n));
</script>
Producción
35
Complejidad de tiempo: O(k*n)
donde k = número de bits para representar el número n
k <= 64
Método 3 (complicado)
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 encendidos, la otra mitad apagados).
Si el número no tiene todos los bits establecidos, entonces alguna posición m es 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:
1) Los bits en las posiciones (m-1) hasta el punto donde el bit más a la izquierda se convierte en 0 y
2) Los 2^(m-1) números debajo de ese punto, que es la forma cerrada arriba.
Una manera fácil de verlo es considerar el número 6:
0|0 0 0|0 1 0|1 0 0|1 1 -|-- 1|0 0 1|0 1 1|1 0
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. bits para todos los números hasta 2 (el valor de la última entrada en el cuadro inferior derecho) que se pueden calcular recursivamente.
C++
#include <bits/stdc++.h>
// A O(Logn) complexity program to count
// set bits in all numbers from 1 to n
using namespace std;
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
unsigned int getLeftmostBit(int n)
{
int m = 0;
while (n > 1)
{
n = n >> 1;
m++;
}
return m;
}
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of 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;
}
// The main recursive function used by countSetBits()
unsigned int _countSetBits(unsigned int n, int m);
// Returns count of set bits present in
// all numbers from 1 to n
unsigned int countSetBits(unsigned int n)
{
// Get the position of leftmost set
// bit in n. This will be used as an
// upper bound for next set bit function
int m = getLeftmostBit(n);
// Use the position
return _countSetBits(n, m);
}
unsigned int _countSetBits(unsigned int n, int m)
{
// Base Case: if n is 0, then set bit
// count is 0
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, i.e., if n
// is like 1, 3, 7, 15, 31, .. etc,
// then we are done.
// Since positions are considered starting
// from 0, 1 is added to m
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) + countSetBits(n) + m * (1 << (m - 1));
}
// Driver code
int main()
{
int n = 17;
cout<<"Total set bit count is "<< countSetBits(n);
return 0;
}
// This code is contributed by rathbhupendra
C
// A O(Logn) complexity program to count
// set bits in all numbers from 1 to n
#include <stdio.h>
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
unsigned int getLeftmostBit(int n)
{
int m = 0;
while (n > 1) {
n = n >> 1;
m++;
}
return m;
}
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of 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;
}
// The main recursive function used by countSetBits()
unsigned int _countSetBits(unsigned int n, int m);
// Returns count of set bits present in
// all numbers from 1 to n
unsigned int countSetBits(unsigned int n)
{
// Get the position of leftmost set
// bit in n. This will be used as an
// upper bound for next set bit function
int m = getLeftmostBit(n);
// Use the position
return _countSetBits(n, m);
}
unsigned int _countSetBits(unsigned int n, int m)
{
// Base Case: if n is 0, then set bit
// count is 0
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, i.e., if n
// is like 1, 3, 7, 15, 31, .. etc,
// then we are done.
// Since positions are considered starting
// from 0, 1 is added to m
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) + countSetBits(n) + m * (1 << (m - 1));
}
// Driver program to test above functions
int main()
{
int n = 17;
printf("Total set bit count is %d", countSetBits(n));
return 0;
}
Java
// Java A O(Logn) complexity program to count
// set bits in all numbers from 1 to n
import java.io.*;
class GFG
{
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
static int getLeftmostBit(int n)
{
int m = 0;
while (n > 1)
{
n = n >> 1;
m++;
}
return m;
}
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of 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;
}
// The main recursive function used by countSetBits()
// Returns count of set bits present in
// all numbers from 1 to n
static int countSetBits(int n)
{
// Get the position of leftmost set
// bit in n. This will be used as an
// upper bound for next set bit function
int m = getLeftmostBit(n);
// Use the position
return countSetBits(n, m);
}
static int countSetBits( int n, int m)
{
// Base Case: if n is 0, then set bit
// count is 0
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, i.e., if n
// is like 1, 3, 7, 15, 31, .. etc,
// then we are done.
// Since positions are considered starting
// from 0, 1 is added to m
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) + countSetBits(n) + m * (1 << (m - 1));
}
// Driver code
public static void main (String[] args)
{
int n = 17;
System.out.println ("Total set bit count is " + countSetBits(n));
}
}
// This code is contributed by ajit..
Python3
# A O(Logn) complexity program to count
# set bits in all numbers from 1 to n
"""
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
"""
def getLeftmostBit(n):
m = 0
while (n > 1) :
n = n >> 1
m += 1
return m
"""
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of leftmost set bit in n */
"""
def getNextLeftmostBit(n, m) :
temp = 1 << m
while (n < temp) :
temp = temp >> 1
m -= 1
return m
# The main recursive function used by countSetBits()
# def _countSetBits(n, m)
# Returns count of set bits present in
# all numbers from 1 to n
def countSetBits(n) :
# Get the position of leftmost set
# bit in n. This will be used as an
# upper bound for next set bit function
m = getLeftmostBit(n)
# Use the position
return _countSetBits(n, m)
def _countSetBits(n, m) :
# Base Case: if n is 0, then set bit
# count is 0
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, i.e., if n
# is like 1, 3, 7, 15, 31, .. etc,
# then we are done.
# Since positions are considered starting
# from 0, 1 is added to m
if (n == (1 << (m + 1)) - 1) :
return ((m + 1) * (1 << m))
# update n for next recursive call
n = n - (1 << m)
return (n + 1) + countSetBits(n) + m * (1 << (m - 1))
# Driver code
n = 17
print("Total set bit count is", countSetBits(n))
# This code is contributed by rathbhupendra
C#
// C# A O(Logn) complexity program to count
// set bits in all numbers from 1 to n
using System;
class GFG
{
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
static int getLeftmostBit(int n)
{
int m = 0;
while (n > 1)
{
n = n >> 1;
m++;
}
return m;
}
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of 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;
}
// The main recursive function used by countSetBits()
// Returns count of set bits present in
// all numbers from 1 to n
static int countSetBits(int n)
{
// Get the position of leftmost set
// bit in n. This will be used as an
// upper bound for next set bit function
int m = getLeftmostBit(n);
// Use the position
return countSetBits(n, m);
}
static int countSetBits( int n, int m)
{
// Base Case: if n is 0,
// then set bit count is 0
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, i.e., if n
// is like 1, 3, 7, 15, 31, .. etc,
// then we are done.
// Since positions are considered starting
// from 0, 1 is added to m
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) + countSetBits(n) +
m * (1 << (m - 1));
}
// Driver code
static public void Main ()
{
int n = 17;
Console.Write("Total set bit count is " +
countSetBits(n));
}
}
// This code is contributed by Tushil.
Javascript
<script>
// JavaScript A O(Logn) complexity program to count
// set bits in all numbers from 1 to n
/* Returns position of leftmost set bit.
The rightmost position is considered
as 0 */
function getLeftmostBit(n)
{
let m = 0;
while (n > 1)
{
n = n >> 1;
m++;
}
return m;
}
/* Given the position of previous leftmost
set bit in n (or an upper bound on
leftmost position) returns the new
position of leftmost set bit in n */
function getNextLeftmostBit(n,m)
{
let temp = 1 << m;
while (n < temp)
{
temp = temp >> 1;
m--;
}
return m;
}
// The main recursive function used by countSetBits()
// Returns count of set bits present in
// all numbers from 1 to n
function countSetBits(n)
{
// Get the position of leftmost set
// bit in n. This will be used as an
// upper bound for next set bit function
let m = getLeftmostBit(n);
// Use the position
return _countSetBits(n, m);
}
function _countSetBits(n,m)
{
// Base Case: if n is 0, then set bit
// count is 0
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, i.e., if n
// is like 1, 3, 7, 15, 31, .. etc,
// then we are done.
// Since positions are considered starting
// from 0, 1 is added to m
if (n == (1 << (m + 1)) - 1)
return (m + 1) * (1 << m);
// update n for next recursive call
n = n - (1 << m);
return (n + 1) + countSetBits(n) + m * (1 << (m - 1));
}
// Driver code
let n = 17;
document.write("Total set bit count is " + countSetBits(n));
// This code is contributed by ab2127
</script>
Producción
Total set bit count is 35
Complejidad de Tiempo: O(Log). Desde el primer vistazo a la implementación, la complejidad del tiempo se ve más. Pero si echamos un vistazo más de cerca, las declaraciones dentro del bucle while de getNextLeftmostBit() se ejecutan para todos los 0 bits en n. Y el número de veces que se ejecuta la recursividad es menor o igual que establecer bits en n. En otras palabras, si el control entra en el ciclo while de getNextLeftmostBit(), entonces omite esos muchos bits en la recursividad.
Gracias a agatsu e IC por sugerir esta solución.
Aquí hay otra solución sugerida por Piyush Kapoor .
Una solución simple, usando el hecho de que para el i-ésimo bit menos significativo, la respuesta será
(N/2^i)*2^(i-1)+ X
dónde
X = N%(2^i)-(2^(i-1)-1)
si y si
N%(2^i)>=(2^(i-1)-1)
C++
int getSetBitsFromOneToN(int N){
int two = 2,ans = 0;
int n = N;
while(n){
ans += (N/two)*(two>>1);
if((N&(two-1)) > (two>>1)-1) ans += (N&(two-1)) - (two>>1)+1;
two <<= 1;
n >>= 1;
}
return ans;
}
Java
static int getSetBitsFromOneToN(int N){
int two = 2,ans = 0;
int n = N;
while(n != 0)
{
ans += (N / two)*(two >> 1);
if((N&(two - 1)) > (two >> 1) - 1)
ans += (N&(two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// This code is contributed by divyeshrabadiya07.
Python3
def getSetBitsFromOneToN(N):
two = 2
ans = 0
n = N
while(n != 0)
{
ans += int(N / two) * (two >> 1)
if((N & (two - 1)) > (two >> 1) - 1):
ans += (N&(two - 1)) - (two >> 1) + 1
two <<= 1;
n >>= 1;
}
return ans
# This code is contributed by avanitrachhadiya2155
C#
static int getSetBitsFromOneToN(int N){
int two = 2,ans = 0;
int n = N;
while(n != 0)
{
ans += (N / two)*(two >> 1);
if((N&(two - 1)) > (two >> 1) - 1)
ans += (N&(two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// This code is contributed by divyesh072019.
Javascript
<script>
function getSetBitsFromOneToN(N)
{
var two = 2
var ans = 0
var n = N
while(n != 0)
{
ans += Math.floor(N / two) * (two >> 1)
if ((N & (two - 1)) > (two >> 1) - 1)
ans += (N&(two - 1)) - (two >> 1) + 1
two <<= 1;
n >>= 1;
}
return ans
}
// This code is contributed by AnkThon
</script>
Método 4 (recursivo)
Acercarse:
Para cada número ‘n’, habrá un número a, donde a<=n y a es la potencia perfecta de dos, como 1,2,4,8…..
Sea n = 11, ahora podemos ver que
Numbers till n, are: 0 -> 0000000 1 -> 0000001 2 -> 0000010 3 -> 0000011 4 -> 0000100 5 -> 0000101 6 -> 0000110 7 -> 0000111 8 -> 0001000 9 -> 0001001 10 -> 0001010 11 -> 0001011 Now we can see that, from 0 to pow(2,1)-1 = 1, we can pair elements top-most with bottom-most, and count of set bit in a pair is 1 Similarly for pow(2,2)-1 = 4, pairs are: 00 and 11 01 and 10 here count of set bit in a pair is 2, so in both pairs is 4 Similarly we can see for 7, 15, ans soon..... so we can generalise that, count(x) = (x*pow(2,(x-1))), here x is position of set bit of the largest power of 2 till n for n = 8, x = 3 for n = 4, x = 2 for n = 5, x = 2 so now for n = 11, we have added set bits count from 0 to 7 using count(x) = (x*pow(2,(x-1))) for rest numbers 8 to 11, all will have a set bit at 3rd index, so we can add count of rest numbers to our ans, which can be calculated using 11 - 8 + 1 = (n-pow(2,x) + 1) Now if notice that, after removing front bits from rest numbers, we get again number from 0 to some m so we can recursively call our same function for next set of numbers, by calling countSetBits(n - pow(2,x)) 8 -> 1000 -> 000 -> 0 9 -> 1001 -> 001 -> 1 10 -> 1010 -> 010 -> 2 11 -> 1011 -> 011 -> 3
Código:
C++
#include <bits/stdc++.h>
using namespace std;
int findLargestPower(int n)
{
int x = 0;
while ((1 << x) <= n)
x++;
return x - 1;
}
int countSetBits(int n)
{
if (n <= 1)
return n;
int x = findLargestPower(n);
return (x * pow(2, (x - 1))) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x));
}
int main()
{
int N = 17;
cout << countSetBits(N) << endl;
return 0;
}
Java
import java.io.*;
class GFG
{
static int findLargestPower(int n)
{
int x = 0;
while ((1 << x) <= n)
x++;
return x - 1;
}
static int countSetBits(int n)
{
if (n <= 1)
return n;
int x = findLargestPower(n);
return (x * (int)Math.pow(2, (x - 1))) + (n - (int)Math.pow(2, x) + 1)
+ countSetBits(n - (int)Math.pow(2, x));
}
public static void main(String[] args)
{
int N = 17;
System.out.print(countSetBits(N));
}
}
// This code is contributed by shivanisinghss2110
Python3
def findLargestPower(n): x = 0 while ((1 << x) <= n): x += 1 return x - 1 def countSetBits(n): if (n <= 1): return n x = findLargestPower(n) return (x * pow(2, (x - 1))) + (n - pow(2, x) + 1) + countSetBits(n - pow(2, x)) N = 17 print(countSetBits(N)) # This code is contributed by shivanisinghss2110
C#
using System;
class GFG
{
static int findLargestPower(int n)
{
int x = 0;
while ((1 << x) <= n)
x++;
return x - 1;
}
static int countSetBits(int n)
{
if (n <= 1)
return n;
int x = findLargestPower(n);
return (x * (int)Math.Pow(2, (x - 1))) + (n - (int)Math.Pow(2, x) + 1)
+ countSetBits(n - (int)Math.Pow(2, x));
}
public static void Main(string[] args)
{
int N = 17;
Console.Write(countSetBits(N));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function findLargestPower(n)
{
var x = 0;
while ((1 << x) <= n)
x++;
return x - 1;
}
function countSetBits(n)
{
if (n <= 1)
return n;
var x = findLargestPower(n);
return (x * Math.pow(2, (x - 1))) + (n - Math.pow(2, x) + 1) + countSetBits(n - Math.pow(2, x));
}
var N = 17;
document.write(countSetBits(N));
// this code is contributed by shivanisinghss2110
</script>
Producción
35
Complejidad de tiempo: O (LogN)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 5 (Iterativo)
Ejemplo:
0 -> 0000000 8 -> 001000 16 -> 010000 24 -> 011000
1 -> 0000001 9 -> 001001 17 -> 010001 25 -> 011001
2 -> 0000010 10 -> 001010 18 -> 010010 26 -> 011010
3 -> 0000011 11 -> 001011 19 -> 010010 27 -> 011011
4 -> 0000100 12 -> 001100 20 -> 010100 28 -> 011100
5 -> 0000101 13 -> 001101 21 -> 010101 29 -> 011101
6 -> 0000110 14 -> 001110 22 -> 010110 30 -> 011110
7 -> 0000111 15 -> 001111 23 -> 010111 31 -> 011111
Entrada: N = 4
Salida: 5
Entrada: N = 17
Salida: 35
Enfoque: Reconocimiento de patrones
Sea ‘N’ cualquier número arbitrario y considere la indexación de derecha a izquierda (siendo el más a la derecha 1); entonces el Pow más cercano = pow(2,i).
Ahora, cuando escriba todos los números del 1 al N, observará el patrón que se menciona a continuación:
Para cada índice i, hay exactamente elementos continuos de NearestPow/2 que no están configurados, seguidos de elementos de NearestPow/2 que están configurados.
A lo largo de la solución, voy a utilizar este concepto.
Puede observar claramente el concepto anterior en la tabla anterior.
La fórmula general que se me ocurrió:
una. addRemaining = mod – (pos más cercano/2) + 1 si mod >= Pow más cercano/2;
b. totalSetBitCount = totalRep*(mainestPow/2) + addRemaining
donde totalRep -> número total de veces que el patrón se repite en el índice i
addRemaining -> número total de bits establecidos que quedan por agregar después de que se agote el patrón
Por ejemplo: sea N = 17
leftMostSetIndex = 5 (índice de bits más a la izquierda, considerando la indexación basada en 1)
i = 1 => pos más cercana = pow(2,1) = 2; totalRep = (17+1)/2 = 9 (suma 1 solo para i=1)
mod = 17%2 = 1
addRemaining = 0 (solo para el caso base)
totalSetBitCount = totalRep*(pos más cercano/2) + addRemaining = 9*(2/2) + 0 = 9*1 + 0 = 9
i = 2 => pos más cercana = pow(2, 2)=4; RepTotal = 17/4 = 4
mod = 17%4 = 1
mod(1) < (4/2) => 1 < 2 => añadirRestos = 0
TotalSetBitCount = 9 + 4*(2) + 0 = 9 + 8 = 17
i = 3 => Pow más cercano = pow(2,3) = 8; RepTotal = 17/8 = 2
mod = 17%8 = 1
mod < 4 => addRemaining = 0
TotalSetBitCount = 17 + 2*(4) + 0 = 17 + 8 + 0 = 25
i = 4 => Pow más cercano = pow(2, 4) = 16; RepTotal = 17/16 = 1
mod = 17%16 = 1
mod < 8 => addRemaining = 0
TotalSetBitCount = 25 + 1*(8) + 0 = 25 + 8 + 0 = 33
No podemos simplemente operar en la próxima potencia (32) como 32>17. Además, como los primeros medios bits serán solo 0, necesitamos encontrar la distancia del número dado (17) desde la última potencia para obtener directamente el número de 1 que se agregará
i = 5 => Pow más cercano = (2, 5) = 32 (caso base 2)
lastPow = pow(2, 4) = 16
mod = 17%16 = 1
totalSetBit = 33 + (mod+1) = 33 + 1 + 1 = 35
Por lo tanto, el número total de bits establecidos de 1 a 17 es 35
Intente iterar con N = 30, para una mejor comprensión de la solución.
Solución
C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int GetLeftMostSetBit(int n){
int pos = 0;
while(n>0){
pos++;
n>>=1;
}
return pos;
}
int TotalSetBitsFrom1ToN(int n){
int leftMostSetBitInd = GetLeftMostSetBit(n);
int totalRep, mod;
int nearestPow;
int totalSetBitCount = 0;
int addRemaining=0;
int curr=0; // denotes the number of set bits at index i
//cout<<"leftMostSetBitInd: "<<leftMostSetBitInd<<endl;
for(int i=1; i<=leftMostSetBitInd; ++i){
nearestPow = pow(2, i);
if(nearestPow>n){
int lastPow = pow(2, i-1);
mod = n%lastPow;
totalSetBitCount += mod+1;
}
else{
if(i==1 && n%2==1){
totalRep = (n+1)/nearestPow;
mod = nearestPow%2;
addRemaining = 0;
}
else{
totalRep = n/nearestPow;
mod = n%nearestPow;
if(mod >= (nearestPow/2)){
addRemaining = mod - (nearestPow/2) + 1;
}else{
addRemaining = 0;
}
}
curr = totalRep*(nearestPow/2) + addRemaining;
totalSetBitCount += curr;
}
// debug output at each iteration
//cout<<i<<" "<<nearestPow<<" "<<totalRep<<" "<<mod<<" "<<totalSetBitCount<<" "<<curr<<endl;
}
return totalSetBitCount;
}
int main(){
std::cout<<TotalSetBitsFrom1ToN(4)<<endl;
std::cout<<TotalSetBitsFrom1ToN(17)<<endl;
std::cout<<TotalSetBitsFrom1ToN(30)<<endl;
return 0;
}
//This code is contributed by rjkrsngh
Java
import java.io.*;
import java.util.*;
class GFG{
static int GetLeftMostSetBit(int n){
int pos = 0;
while(n>0){
pos++;
n>>=1;
}
return pos;
}
static int TotalSetBitsFrom1ToN(int n){
int leftMostSetBitInd = GetLeftMostSetBit(n);
int totalRep, mod;
int nearestPow;
int totalSetBitCount = 0;
int addRemaining = 0;
int curr = 0; // denotes the number of set bits at index i
for(int i=1; i<=leftMostSetBitInd; ++i){
nearestPow = (int)Math.pow(2, i);
if(nearestPow>n){
int lastPow = (int)Math.pow(2, i-1);
mod = n%lastPow;
totalSetBitCount += mod+1;
}
else{
if(i == 1 && n % 2 == 1){
totalRep = (n + 1) / nearestPow;
mod = nearestPow % 2;
addRemaining = 0;
}
else{
totalRep = n/nearestPow;
mod = n%nearestPow;
if(mod >= (nearestPow/2))
{
addRemaining = mod - (nearestPow/2) + 1;
}
else{
addRemaining = 0;
}
}
curr = totalRep*(nearestPow/2) + addRemaining;
totalSetBitCount += curr;
}
}
return totalSetBitCount;
}
public static void main(String[] args){
System.out.println(TotalSetBitsFrom1ToN(4));
System.out.println(TotalSetBitsFrom1ToN(17));
System.out.println(TotalSetBitsFrom1ToN(30));
}
}
// This code is contributed by vikaschhonkar1
// By: Vikas Chhonkar
Python3
def get_left_most_set_bit(n): left_most_set_bit_indx = 0 while n > 0: left_most_set_bit_indx += 1 n >>= 1 return left_most_set_bit_indx def total_set_bits_from_1_to_n(n): left_most_set_bit_indx = get_left_most_set_bit(n) total_rep = 0 mod = 0 nearest_pow = 0 total_set_bit_count = 0 add_remaining = 0 curr=0 # denotes the number of set bits at index i for i in range(1, left_most_set_bit_indx + 1): nearest_pow = pow(2, i) if nearest_pow > n: last_pow = pow(2, i-1) mod = n % last_pow total_set_bit_count += mod + 1 else: if i == 1 and n % 2 == 1: total_rep = (n + 1) / nearest_pow mod = nearest_pow % 2 add_remaining = 0 else: total_rep = int(n / nearest_pow) mod = n % nearest_pow add_remaining = int(mod - (nearest_pow / 2) + 1) if mod >= nearest_pow / 2 else 0 curr = int(total_rep * (nearest_pow / 2) + add_remaining) total_set_bit_count += curr return total_set_bit_count # Driver code if __name__ == "__main__": print(total_set_bits_from_1_to_n(4)) print(total_set_bits_from_1_to_n(17)) print(total_set_bits_from_1_to_n(30)) # This code is contributed by tssovi.
C#
// C# program for the above approach
using System;
public class GFG {
static int GetLeftMostSetBit(int n){
int pos = 0;
while(n>0){
pos++;
n>>=1;
}
return pos;
}
static int TotalSetBitsFrom1ToN(int n){
int leftMostSetBitInd = GetLeftMostSetBit(n);
int totalRep, mod;
int nearestPow;
int totalSetBitCount = 0;
int addRemaining = 0;
int curr = 0; // denotes the number of set bits at index i
for(int i=1; i<=leftMostSetBitInd; ++i){
nearestPow = (int)Math.Pow(2, i);
if(nearestPow>n){
int lastPow = (int)Math.Pow(2, i-1);
mod = n%lastPow;
totalSetBitCount += mod+1;
}
else{
if(i == 1 && n % 2 == 1){
totalRep = (n + 1) / nearestPow;
mod = nearestPow % 2;
addRemaining = 0;
}
else{
totalRep = n/nearestPow;
mod = n%nearestPow;
if(mod >= (nearestPow/2))
{
addRemaining = mod - (nearestPow/2) + 1;
}
else{
addRemaining = 0;
}
}
curr = totalRep*(nearestPow/2) + addRemaining;
totalSetBitCount += curr;
}
}
return totalSetBitCount;
}
// Driver Code
public static void Main(String[] args) {
Console.WriteLine(TotalSetBitsFrom1ToN(4));
Console.WriteLine(TotalSetBitsFrom1ToN(17));
Console.WriteLine(TotalSetBitsFrom1ToN(30));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
function GetLeftMostSetBit(n) {
var pos = 0;
while (n > 0) {
pos++;
n >>= 1;
}
return pos;
}
function TotalSetBitsFrom1ToN(n) {
var leftMostSetBitInd = GetLeftMostSetBit(n);
var totalRep, mod;
var nearestPow;
var totalSetBitCount = 0;
var addRemaining = 0;
var curr = 0; // denotes the number of set bits at index i
for (var i = 1; i <= leftMostSetBitInd; ++i) {
nearestPow = parseInt( Math.pow(2, i));
if (nearestPow > n) {
var lastPow = parseInt( Math.pow(2, i - 1));
mod = n % lastPow;
totalSetBitCount += mod + 1;
} else {
if (i == 1 && n % 2 == 1) {
totalRep = parseInt((n + 1) / nearestPow);
mod = nearestPow % 2;
addRemaining = 0;
} else {
totalRep =parseInt( n / nearestPow);
mod = n % nearestPow;
if (mod >= parseInt(nearestPow / 2)) {
addRemaining = mod - parseInt(nearestPow / 2) + 1;
} else {
addRemaining = 0;
}
}
curr = totalRep * (parseInt(nearestPow / 2)) + addRemaining;
totalSetBitCount += curr;
}
}
return totalSetBitCount;
}
document.write(TotalSetBitsFrom1ToN(4));
document.write("<br/>"+TotalSetBitsFrom1ToN(17));
document.write("<br/>"+TotalSetBitsFrom1ToN(30));
// This code is contributed by Rajput-Ji
</script>
Producción :
5
35
75
Complejidad de tiempo: O(log(n))
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA