algorithm - tres - mascara de red

Encontrar el número total de bits de conjunto de 1 a n

Question

Escriba un algoritmo para encontrar F(n) el número de bits establecido en 1, en todos los números de 1 a n para cualquier valor dado de n.

La complejidad debe ser O(log n)

Por ejemplo:

1: 001
2: 010
3: 011
4: 100
5: 101
6: 110

Asi que

F(1) = 1,  
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.

Solo puedo diseñar un algoritmo O(n) .

Answer 1

¡corto y dulce!

 public static int countbits(int num){
    int count=0, n;
    while(num > 0){
        n=0;
        while(num >= 1<<(n+1))
            n++;
        num -= 1<<n;
        count += (num + 1 + (1<<(n-1))*n);
    }
    return count;
}//countbis

Answer 2

Aquí está la función java

private static int[] findx(int i) {
    //find the biggest power of two number that is smaller than i
    int c = 0;
    int pow2 = 1;
    while((pow2<< 1) <= i) {
        c++;
        pow2 = pow2 << 1;
    }
    return new int[] {c, pow2};
}

public static int TotalBits2(int number) {
    if(number == 0) {
        return 0;
    }
    int[] xAndPow = findx(number);
    int x = xAndPow[0];
    return x*(xAndPow[1] >> 1) + TotalBits2(number - xAndPow[1]) + number - xAndPow[1] + 1;
}

Answer 3

Aquí está mi solución a esto. Complejidad del tiempo: O (Log n)

public int countSetBits(int n){
    int count=0;
    while(n>0){
        int i= (int)(Math.log10(n)/Math.log10(2));
        count+= Math.pow(2, i-1)*i;
        count+= n-Math.pow(2, i)+1;
        n-= Math.pow(2, i);
    }
    return count;
}

Answer 4

Considera lo siguiente:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Si desea encontrar el número total de bits establecidos de 1 a 14 (1110) pocas observaciones:

1. 0th bit 0th (LSB) 1 bit aparece una vez cada dos bits (ver verticalmente), por lo que el número de bits establecidos = n/2 + ( 1 si n''s 0th bit is 1 más 0 )
2. 1er bit: aparecen 1s consecutivos cada cuatro bits (ver 1er bit verticalmente a lo largo de todos los números) número de bits establecidos en la posición del 1st bit = (n/4 *2) + 1 (ya que el 1st bit es un conjunto, de lo contrario 0 )
3. 2nd bit: aparecen 4 1s consecutivos cada 8 bits (este es un poco complicado) número de bits establecidos en la 2ª posición = (n/8*4 )+ 1 (ya que el 2nd bit está establecido, de lo contrario 0 ) + ((n%8)%(8/2)) El último término es para incluir el número de 1s que estaban fuera del primer grupo de bits ( (n/8) ( 14/8 =1 considera solo 1 grupo, es decir, 4 bits establecidos en 8 bits. necesitamos incluir 1s encontrados en los últimos 14-8 = 6 bits)
4. 3rd bit: aparecen 1s consecutivos cada 16 bits (similar al anterior) número de bits establecidos en la 3rd posición = (n/16*8)+1 (ya que el 3rd bit está establecido, de lo contrario 0 ) + ((n%16)%(16/2))

entonces hacemos O(1) cálculo para cada bit de un número n . un número contiene log2(n) bits. así que cuando iteramos lo anterior para todas las posiciones de n y agregamos todos los bits establecidos en cada paso, obtenemos la respuesta en pasos O(logn)

Answer 5

La forma de resolver este tipo de problemas es escribir los primeros valores y buscar un patrón.

Number binary # bits set F(n) 1 0001 1 1 2 0010 1 2 3 0011 2 4 4 0100 1 5 5 0101 2 7 6 0110 2 9 7 0111 3 12 8 1000 1 13 9 1001 2 15 10 1010 2 17 11 1011 3 20 12 1100 2 22 13 1101 3 25 14 1110 3 28 15 1111 4 32

Toma un poco de atención, pero con un poco de pensamiento te das cuenta de que las representaciones binarias de los primeros 8 y los últimos 8 números son exactamente iguales, excepto que los primeros 8 tienen un 0 en el MSB ( bit más significativo) , mientras que Los últimos 8 tienen un 1 . Así, por ejemplo, para calcular F(12) , podemos simplemente tomar F(7) y agregarle el número de bits establecidos en 8, 9, 10, 11 y 12. Pero eso es lo mismo que el número de bits establecidos en 0, 1, 2, 3 y 4 (es decir, F(4) ) , ¡más uno más por cada número!

# binary 0 0 000 1 0 001 2 0 010 3 0 011 4 0 100 5 0 101 6 0 110 7 0 111 8 1 000 <--Notice that rightmost-bits repeat themselves 9 1 001 except now we have an extra ''1'' in every number! 10 1 010 11 1 011 12 1 100

Por lo tanto, para 8 <= n <= 15 , F(n) = F(7) + F(n-8) + (n-7) . De manera similar, podemos notar que para 4 <= n <= 7 , F(n) = F(3) + F(n-4) + (n-3) ; y para 2 <= n <= 3 , F(n) = F(1) + F(n-2) + (n-1) . En general, si configuramos a = 2^(floor(log(n))) , entonces F(n) = F(a-1) + F(na) + (n-a+1)

Esto no nos da un algoritmo O(log n) ; Sin embargo, hacerlo es fácil. Si a = 2^x , anote en la tabla anterior que para a-1 , el primer bit se establece exactamente a/2 veces, el segundo bit se establece exactamente a/2 veces, el tercer bit ... hasta el final hasta el bit x. Por lo tanto, F(a-1) = x*a/2 = x*2^(x-1) . En la ecuación anterior, esto nos da

F(n) = x*2^x-1 + F(n-2^x) + (n-2^x+1)

Donde x = floor(log(n)) . Cada iteración del cálculo de F eliminará esencialmente el MSB; por lo tanto, este es un algoritmo O(log(n)) .

Answer 6

No estoy seguro si es tarde para responder, pero aquí están mis conclusiones.

Intenté resolver el problema con la siguiente aproximación, para el número N cada bitno (desde LSB a MSB, digamos que el LSB comienza con bitno 1 e incrementa con el siguiente valor de bit) el número de bits establecido se puede calcular como, (N / (2 bit topower superior) * (2 topower bitno-1) + {(N% (2 topower bitno)) - [(2 topower bitno-1) - 1]}

Han escrito una función recursiva para ello C / C ++ por favor verifique. No estoy seguro, pero creo que su complejidad es log (N). Pase los parámetros de la función 2, el número (no) para el cual queremos que se calculen los bits y el segundo conteo de inicio de LSB, valor 1.

int recursiveBitsCal(int no, int bitno){
int res = int(no/pow(2,bitno))*int(pow(2,bitno-1));
int rem1 = int(pow(2,bitno-1)) -1;
int rem = no % int(pow(2,bitno));
if (rem1 < rem) res += rem -rem1;
if ( res <= 0 )
    return 0;
else
    return res + recursiveBitsCal(no, bitno+1);
}

Answer 7

Por cierto, esta pregunta también puede hacerse mediante el método de tabla de búsqueda. Calcule previamente el número de bits establecidos de 0 a 255 y guárdelo. Publique eso, podemos calcular el número de bits establecidos en cualquier número dividiendo un número dado en dos partes de 8 bits cada una. Para cada parte, podemos buscar en la matriz de conteo formada en el primer paso. Por ejemplo, si hay un número de 16 bits como,

x = 1100110001011100 , aquí, el número de bits establecidos = número de bits establecidos en el primer byte + número de bits establecidos en el segundo byte. Por lo tanto, para obtener, primer byte,

y = (x & 0xff) z = (x >> 8) & (0xff) total set bits = count[y] + count[z]

Este método también se ejecutará en O (n).

Answer 8

Sea k el número de bits necesarios para n .

para 0,...,2^(k-1)-1 cada bit está activo exactamente para la mitad de los números, por lo que tenemos (k-1)*2^(k-1)/2 = (k-1)*2^(k-2) bits hasta ahora. Solo necesitamos verificar qué pasa con los números que son más grandes que 2^(k-1)-1
También tenemos para esos n-2^(k-1)-1 bits "up" para el MSB.

Así que podemos derivar a la función recursiva:

f(n) = (k-1)*2^(k-2) + n-(2^(k-1)-1) + f(n-(2^(k-1)))
           ^               ^            ^
         first            MSBs        recursive call for 
       2^(k-1)-1                      n-2^(k-1) highest numbers
        numbers

Donde la base es f(0) = 0 y f(2^k) = k*2^(k-1) + 1 [como hemos visto antes, sabemos exactamente cuántos bits hay para 2^(k-1)-1 , y solo necesitamos agregar 1 - para el MSB de 2^k ]

Como el valor enviado a f se reduce en al menos la mitad en cada iteración, obtenemos un total de O(logn)

Answer 9

Si n= 2^k-1, then F(n)=k*(n+1)/2

Para un n general, sea m el número más grande tal que m = 2^k-1 y m<=n . F(n) = F(m) + F(nm-1) + (nm) .

Condición de la esquina: F(0)=0 y F(-1)=0 .

Answer 10

Una búsqueda rápida de los valores de la secuencia F lleva a esta secuencia de enteros http://oeis.org/A000788

Allí vi una fórmula: a (0) = 0, a (2n) = a (n) + a (n-1) + n, a (2n + 1) = 2a (n) + n + 1 (a es igual que F ya que solo copio la fórmula de oeis)

que podría usarse para calcular un (n) en el registro (n).

Aquí está mi código C ++ de muestra:

memset(cache, -1, sizeof(cache))
cache[0] = 0

int f(int n)
    if cache[n] != -1 return cache[n];
    cache[n] = n % 2 ? (2 * f(n / 2) + n / 2 + 1) : (f(n / 2) + f(n / 2 - 1) + n / 2)

Answer 11

esto está codificado en java ...
lógica: digamos que el número es 34, el binario igual-ant es 10010, que puede escribirse como 10000 + 10. 10000 tiene 4 ceros, por lo que la cuenta de todos los 1 antes de este número es 2 ^ 4 (motivo más abajo). por lo que el conteo es 2 ^ 4 + 2 ^ 1 + 1 (numérelo). entonces la respuesta es 35
* para el número binario 10000. las combinaciones totales de llenar 4 lugares son 2 * 2 * 2 * 2x2 (uno o cero). Entonces las combinaciones totales de unos son 2 * 2 * 2 * 2.

public static int getOnesCount(int number) {
    String binary = Integer.toBinaryString(number);
    return getOnesCount(binary);
}

private static int getOnesCount(String binary) {
    int i = binary.length();

    if (i>0 && binary.charAt(0) == ''1'') {
        return gePowerof2(i) + getOnesCount(binary.substring(1));
    }else if(i==0)
        return 1;
    else
        return getOnesCount(binary.substring(1));

}
//can be replaced with any default power function
private static int gePowerof2(int i){
    int count = 1;
    while(i>1){
        count*=2;
        i--;
    }
    return count;
}