Pregunta Encuentra el rango de un número decimal basado en la función F (N) = rango


Encontré esta pregunta aquí, pero esta no es la respuesta que estoy buscando. Por lo tanto, publicar de nuevo.

Una función de la forma:

F( N ) = rank

significa que dado un número N en representación decimal, su rango se da como:

Starting from 0 to N, how many numbers are there with same number of set bits in its
binary representation.

Voy a ir a través de un ejemplo para hacerlo más claro.

N = 6 ( 0110 )
Its rank is 3.
1. 3 ( 0011 )
2. 5 ( 0101 )
3. 6 ( 0110 )

Ahora, dado un número, encuentre su rango.

El enfoque obvio es comenzar desde 0 y verificar el número de bits establecidos para cada número hasta N-1.

La pregunta es:

¿Hay alguna solución logN?


7
2017-09-03 18:20


origen


Respuestas:


Sí, hay un log n solución.

Dejar n tener k bits establecidos, siendo el bit más significativo en posición p (comenzando a contar posiciones desde 0, entonces 2^p <= n < 2^(p+1)) Luego están pCk (coeficiente binomial, también choose(p,k)) formas de colocar k bits en las posiciones 0, ..., p-1, todos estos dan números con exactamente k establecer bits que son más pequeños que n. Si k == 1, eso es, de lo contrario, quedan los números con k establecer bits y p-th bit set que son más pequeños que n considerar. Esos pueden ser contados al determinar el rango de n - 2^p.

Código (no es óptimo, realiza un recálculo innecesario y no hace todo lo posible para evitar el desbordamiento):

unsigned long long binom(unsigned n, unsigned k) {
    if (k == 0 || n == k) return 1;
    if (n < k) return 0;
    if (k > (n >> 1)) k = n-k;
    unsigned long long res = n, j;
    // We're not doing all we can to avoid overflow, as this is a proof of concept,
    // not production code.
    for(j = 2; j <= k; ++j) {
        res *= (n+1-j);
        res /= j;
    }
    return res;
}

unsigned popcount(unsigned long long n) {
    unsigned k = 0;
    while(n) {
        ++k;
        n &= (n-1);
    }
    return k;
}

unsigned long long rank(unsigned long long n) {
    if (n == 0) return 1;
    unsigned p = 0, k = popcount(n);
    unsigned long long mask = 1,h = n >> 1;
    while(h > 0) {
        ++p;
        h >>= 1;
    }
    mask <<= p;
    unsigned long long r = binom(p,k);
    r += rank(n-mask);
    return r;
}

Probado en un ciclo para 0 <= n < 10^8 para verificar si hay errores sin encontrar ningún desajuste

Verificar salida aquí.


7
2017-09-03 18:34



Aquí hay una implementación O (logN) bastante eficiente que realiza múltiples adiciones en paralelo por paso:

unsigned int countBits( unsigned int bits )
{
    bits = ( bits & 0x55555555 ) + ( ( bits >> 1 ) & 0x55555555 );
    bits = ( bits & 0x33333333 ) + ( ( bits >> 2 ) & 0x33333333 );
    bits = ( bits + ( bits >>  4 ) ) & 0x0f0f0f0f;
    bits += bits >>  8;
    return ( bits + ( bits >> 16 ) ) & 63;
}

Comienza con 16 adiciones de 2 bits, luego realiza 8 adiciones de 4 bits y así sucesivamente. Se puede ampliar para trabajar con enteros de 64 bits mediante el uso de máscaras más largas y un paso adicional:

unsigned int countBits( unsigned long long bits )
{
    bits = ( bits & 0x5555555555555555L ) + ( ( bits >> 1 ) & 0x5555555555555555LL );
    bits = ( bits & 0x3333333333333333L ) + ( ( bits >> 2 ) & 0x3333333333333333LL );
    bits = ( bits + ( bits >>  4 ) ) & 0x0f0f0f0f0f0f0f0fLL;
    bits += bits >>  8;
    bits += bits >> 16;
    return (unsigned int) ( bits + ( bits >> 32 ) ) & 127;
}

0
2017-09-03 19:39



Se puede resolver mediante técnicas de combinación y permutación.

F (N) = rango

Primero encuentre el número de bits que se requieren para representar N. En la representación binaria, el número se puede construir de la siguiente manera:

N = cn 2^n + .... + c3 2^2 + c2 2^1 + c1 2^0

Ahora, para encontrar n (o números de bits en representación binaria de un número) en la ecuación anterior, podemos suponer que será floor(log2(N)) + 1. Por ejemplo, considere cualquier número, digamos 118 luego se puede representar por piso (log2 (118)) + 1 = 7 bits.

n = floor(log2(118)) + 1;

La fórmula anterior es solo O(1). Ahora, necesitamos encontrar cuántos 1s hay en la representación binaria de un número. Teniendo en cuenta un pseudo-código para hacer este trabajo:

function count1(int N) {
    int c = 0;
    int N' = N;

    while(N' > 0) {
       N' -= 2^(floor(log2(N')));
       c++;
    }
}

Por encima del pseudo-código es O(logN). Escribí un pequeño script en MATLAB para probar mi pseudocódigo anterior y aquí están los resultados.

count1(6)   = 2
count1(3)   = 2
count1(118) = 5

Perfecto, ahora tenemos número de bits y número de 1 en esos bits. Ahora, se puede aplicar una combinación simple y permutación para encontrar el rango de número. primero supongamos, n es la cantidad de bits necesarios para representar un número y c es el número de 1s en la representación de bits de un número. Por lo tanto, el rango estaría dado por:

r = n ! / c ! * (n - c) ! 

EDITAR: Como lo sugirió DSM, he corregido la lógica para encontrar el RANGO correcto. Idea es eliminar todos los números no deseados de la permutación. Así que agregué este código:

for i = N + 1 : 2^n - 1
    if count(i) == c
       r = r - 1;
    end
end

He escrito una secuencia de comandos MATLAb para encontrar el rango de un número usando el método anterior:

function r = rankN(N)

n = floor(log2(N)) + 1;
c = count(N);
r = factorial(n) / (factorial(c) * factorial(n - c));
% rejecting all the numbers may have included in the permutations 
% but are unnecessary.
for i = N + 1 : 2^n - 1
    if count(i) == c
       r = r - 1;
    end
end

function c = count(n)

c = 0;
N = n;
while N > 0
    N = N - 2^(floor(log2(N)));
    c = c + 1;
end

Y encima de alogrithm es O(1) + O(logN) + O(1) = O(logN). El resultado es:

>> rankN(3)

ans =

     1

>> rankN(4)

ans =

     3

>> rankN(7)

ans =

     1

>> rankN(118)

ans =

    18

>> rankN(6)

ans =

     3

Nota: Rango de 0 es siempre 1 porque el método anterior fracasará 0 como log2(0) es indefinido.


0
2017-09-03 19:12