Mapear dos enteros a uno, de una manera única y determinista

235

Imagine dos enteros positivos A y B. Quiero combinar estos dos en un solo entero C.

No puede haber otros enteros D y E que se combinen con C. Por lo tanto, combinarlos con el operador de suma no funciona. Por ejemplo, 30 + 10 = 40 = 40 + 0 = 39 + 1 Tampoco funciona la concatenación. Por ejemplo, "31" + "2" = 312 = "3" + "12"

Esta operación de combinación también debe ser determinista (siempre produce el mismo resultado con las mismas entradas) y siempre debe producir un número entero en el lado positivo o negativo de los enteros.

daño
fuente
10
Debe aclarar si se refiere a enteros en software o enteros en matemáticas. En el software, eliges cualquier tipo de entero y tendrá un tamaño, por lo que tienes un número finito de ellos, por lo que no hay solución (a menos, por supuesto, que tus datos de entrada estén dentro de cierto rango y tu salida pueda ser cualquier número entero). En matemáticas, vea la solución de ASk.
Daniel Daranas
Estoy hablando de enteros limitados en un rango bajo y positivo. Decir 0 a 10,000
daño
27
@harm: Entonces, ¿qué tal solo 10,001*A + B?
BlueRaja - Danny Pflughoeft
2
He encontrado estas funciones PHP: gist.github.com/hannesl/8031402
cakan
Si el orden no importa, por ejemplo: (3,12) y (12,3) dan el mismo resultado, uso "A + B" + "A * B"
Sodj

Respuestas:

233

Estás buscando un NxN -> Nmapeo biyectivo . Éstos se utilizan, por ejemplo, para hacer cola de milano . Eche un vistazo a este PDF para obtener una introducción a las llamadas funciones de emparejamiento . Wikipedia presenta una función de emparejamiento específica, a saber, la función de emparejamiento de Cantor :

pi (k1, k2) = 1/2 (k1 + k2) (k1 + k2 + 1) + k2

Tres observaciones:

  • Como otros han dejado en claro, si planea implementar una función de emparejamiento, pronto encontrará que necesita enteros arbitrariamente grandes (bignums).
  • Si no desea hacer una distinción entre los pares (a, b) y (b, a), clasifique ayb antes de aplicar la función de emparejamiento.
  • En realidad mentí. Estás buscando un ZxZ -> Nmapeo biyectivo . La función de Cantor solo funciona en números no negativos. Sin embargo, esto no es un problema, porque es fácil definir una biyección f : Z -> N, así:
    • f (n) = n * 2 si n> = 0
    • f (n) = -n * 2 - 1 si n <0
Stephan202
fuente
13
+1 Creo que esta es la respuesta correcta para enteros ilimitados.
Desconocido
44
¿Cómo puedo obtener nuevamente el valor de k1, k2?
MinuMaster
3
@MinuMaster: eso se describe en el mismo artículo de Wikipedia, en Invertir la función de emparejamiento de Cantor .
Stephan202
44
Ver también la función de Szudzik, explicada por newfal a continuación.
OliJG
1
Si bien esto es correcto para enteros ilimitados, no es mejor para enteros acotados. Creo que el comentario de @ blue-raja tiene mucho sentido.
Kardasis
226

La función de emparejamiento de Cantor es realmente una de las mejores, considerando que es simple, rápida y eficiente en cuanto al espacio, pero hay algo aún mejor publicado en Wolfram por Matthew Szudzik, aquí . La limitación de la función de emparejamiento de Cantor (relativamente) es que el rango de resultados codificados no siempre se mantiene dentro de los límites de un 2Nnúmero entero de bits si las entradas son Nnúmeros enteros de dos bits. Es decir, si mis entradas son 16enteros de dos bits que van desde 0 to 2^16 -1, entonces hay 2^16 * (2^16 -1)combinaciones de entradas posibles, por lo que, según el Principio de Pigeonhole obvio , necesitamos una salida de tamaño al menos 2^16 * (2^16 -1), que sea igual 2^32 - 2^16o, en otras palabras, un mapa de32los números de bits deberían ser factibles idealmente. Esto puede no ser de poca importancia práctica en el mundo de la programación.

Función de emparejamiento de Cantor :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

La asignación para dos enteros máximos de 16 bits (65535, 65535) será 8589803520 que, como puede ver, no puede caber en 32 bits.

Ingrese la función de Szudzik :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

La asignación para (65535, 65535) ahora será 4294967295 que, como puede ver, es un entero de 32 bits (0 a 2 ^ 32 -1). Aquí es donde esta solución es ideal, simplemente utiliza cada punto en ese espacio, por lo que nada puede ser más eficiente.


Ahora, considerando el hecho de que generalmente tratamos con implementaciones firmadas de números de varios tamaños en lenguajes / marcos, consideremos signed 16los enteros de bits que van desde -(2^15) to 2^15 -1(más adelante veremos cómo extender incluso la salida para que se extienda sobre el rango firmado). Desde ay btienen que ser positivos van desde 0 to 2^15 - 1.

Función de emparejamiento de Cantor :

La asignación para dos números enteros máximos con signo de 16 bits (32767, 32767) será 2147418112, que es justo por debajo del valor máximo para el número entero con signo de 32 bits.

Ahora la función de Szudzik :

(32767, 32767) => 1073741823, mucho más pequeño ...

Consideremos los enteros negativos. Eso está más allá de la pregunta original que conozco, pero solo se elabora para ayudar a los futuros visitantes.

Función de emparejamiento de Cantor :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520 que es Int64. ¡La salida de 64 bits para entradas de 16 bits puede ser tan imperdonable!

La función de Szudzik :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295, que es 32 bits para rango sin signo o 64 bits para rango con signo, pero aún mejor.

Ahora todo esto mientras que la salida siempre ha sido positiva. En el mundo firmado, se ahorrará aún más espacio si pudiéramos transferir la mitad de la salida al eje negativo . Podrías hacerlo así para Szudzik's:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

Lo que hago: después de aplicar un peso de 2a las entradas y pasar por la función, divido la salida por dos y llevo algunas de ellas al eje negativo multiplicando por -1.

Vea los resultados, para cualquier entrada en el rango de un 16número de bit con signo , la salida se encuentra dentro de los límites de un 32entero de bit con signo que es genial. No estoy seguro de cómo hacer lo mismo para la función de emparejamiento de Cantor, pero no intenté tanto como no es tan eficiente. Además, más cálculos involucrados en la función de emparejamiento de Cantor significa que también es más lento .

Aquí hay una implementación de C #.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Como los cálculos intermedios pueden exceder los límites del 2Nentero con signo, he usado el 4Ntipo entero (la última división 2devuelve el resultado 2N).

El enlace que he proporcionado en una solución alternativa muestra muy bien un gráfico de la función que utiliza cada punto en el espacio. ¡Es sorprendente ver que puedes codificar de forma única un par de coordenadas en un solo número de forma reversible! ¡Mundo mágico de números!

nawfal
fuente
55
¿Cuál sería la función unhash modificada para enteros con signo?
Arets Paeglis
77
Esta respuesta me confunde. Si desea asignar (0,0)a través (65535,65535)de un único número, entonces a<<16 + bes mejor en todos los sentidos, básicamente (más rápido, más simple, más fácil de entender, más evidente) . Si quieres (-32768,-32768)a (327687,327687)cambio, simplemente sujeta 32768 primero.
BlueRaja - Danny Pflughoeft
2
@ BlueRaja-DannyPflughoeft tienes razón. Mi respuesta sería válida si el rango no es limitado o desconocido. Lo actualizaré. Lo había escrito antes de que el límite me importara. Editar esta respuesta ha estado en mi mente por mucho tiempo. Encontraré tiempo pronto.
nawfal
¿Funciona la función de Szudzik para combinaciones o permutaciones? Parece ser permutaciones ¿verdad? Si quiero usar para la combinación, ¿puedo eliminar las partes IF y Else del algoritmo?
Jamie Marshall
Aquí hay una implementación de Python de la función de Szudzik generalizada a tuplas de cualquier longitud: gitlab.com/snippets/32559
Doctor J
47

Si A y B pueden expresarse con 2 bytes, puede combinarlos en 4 bytes. Ponga A en la mitad más significativa y B en la mitad menos significativa.

En lenguaje C esto da (suponiendo sizeof (short) = 2 y sizeof (int) = 4):

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}
Mouviciel
fuente
3
combine()debería return (unsigned short)(A<<16) | (unsigned short)(B); Para que los números negativos se puedan empaquetar correctamente.
Andy
2
@Andy A<<16saldrá de los límites. Debería serreturn (unsigned int)(A<<16) | (unsigned short)(B);
DanSkeel
15

¿Es esto posible?
Estás combinando dos enteros. Ambos tienen el rango de -2,147,483,648 a 2,147,483,647 pero solo tomará los positivos. Eso hace 2147483647 ^ 2 = 4,61169E + 18 combinaciones. Como cada combinación tiene que ser única Y dar como resultado un número entero, necesitará algún tipo de número entero mágico que pueda contener esta cantidad de números.

¿O es mi lógica defectuosa?

Boris Callens
fuente
+1 Eso es lo que pienso también (aunque hice el cálculo diciendo que el orden de A y B no importa)
lc.
44
Sí, su lógica es correcta según el principio del casillero. Desafortunadamente, el autor de la pregunta no especificó si el número entero está acotado o no.
Desconocido
Sí, tuve esa idea de último momento también, pero pensé que el mensaje es esencialmente el mismo, así que no me molesté en recordarlo.
Boris Callens
También me di cuenta de que debería retomar mis libros de texto de cálculo de posibilidades (traducción literal del holandés) nuevamente.
Boris Callens
2
@ Boris: Kansrekening es "teoría de la probabilidad".
Stephan202
8

La forma matemática estándar para los enteros positivos es utilizar la singularidad de la factorización prima.

f( x, y ) -> 2^x * 3^y

La desventaja es que la imagen tiende a abarcar una amplia gama de enteros, por lo que cuando se trata de expresar el mapeo en un algoritmo informático, puede tener problemas para elegir un tipo apropiado para el resultado.

Puede modificar esto para tratar con negativo xy ycodificando banderas con potencias de 5 y 7 términos.

p.ej

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
CB Bailey
fuente
Las matemáticas están bien. Pero, como dice Boris, si desea ejecutar esto como un programa de computadora, debe tener en cuenta la finitud de la máquina. El algoritmo funcionará correctamente para un subconjunto de los enteros representables en la máquina relevante.
Yuval F
2
Lo dije en mi segundo párrafo. Las etiquetas en la pregunta indican 'algoritmo', 'matemático' y 'determinista', no un lenguaje en particular. El rango de entrada puede no estar limitado y el entorno puede tener un tipo entero ilimitado 'bigint'.
CB Bailey
8

Deje que el número asea ​​el primero, bel segundo. Sea pel a+1enésimo número primo, qsea ​​el b+1enésimo número primo

Entonces, el resultado es pq, si a<b,o 2pqsi a>b. Si a=b, que así sea p^2.

Pedir
fuente
44
Dudo que quieras una solución NP.
user44242
1
¿No produce esto el mismo resultado para a = 5, b = 14 y a = 6, b = 15?
Lieven Keersmaekers
3
Dos productos de dos primos diferentes no pueden tener el mismo resultado (descomposición única del factor primo) a = 5, b = 14 -> el resultado es 13 * 47 = 611 a = 6, b = 15 -> el resultado es 17 * 53 = 901
PREGUNTE
4

No es tan difícil construir un mapeo:

   1 2 3 4 5 use esta asignación si (a, b)! = (B, a)
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40

   1 2 3 4 5 use esta asignación si (a, b) == (b, a) (espejo)
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24


    0 1 -1 2 -2 use esto si necesita negativo / positivo
 0 0 1 2 4 6
 1 1 3 5 7 10
-1 2 5 8 11 14
 2 4 8 11 15 19
-2 6 10 14 19 24

Descubrir cómo obtener el valor para un arbitrario a, b es un poco más difícil.

Delfín
fuente
4

f(a, b) = s(a+b) + a, dónde s(n) = n*(n+1)/2

  • Esta es una función, es determinista.
  • También es inyectivo: f asigna diferentes valores para diferentes pares (a, b). Puede probar esto con el hecho de: s(a+b+1)-s(a+b) = a+b+1 < a.
  • Devuelve valores bastante pequeños, bueno si lo va a usar para indexar la matriz, ya que la matriz no tiene que ser grande.
  • Es compatible con el caché: si dos (a, b) pares están cerca uno del otro, entonces f asigna números que están cerca el uno del otro (en comparación con otros métodos).

No entendí lo que quieres decir con:

siempre debe producir un número entero en el lado positivo o negativo de los enteros

¿Cómo puedo escribir (mayor que), (menor que) caracteres en este foro?

libeako
fuente
2
Los caracteres mayores y menores que deberían funcionar bien en el interior backtick escapes.
TRiG
Esto es equivalente a la función de emparejamiento de Cantor, y como tal no funciona con enteros negativos.
Davor Josipovic
4

Aunque la respuesta de Stephan202 es la única realmente general, para los enteros en un rango acotado puede hacerlo mejor. Por ejemplo, si su rango es 0..10,000, entonces puede hacer:

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

Los resultados pueden caber en un solo entero para un rango hasta la raíz cuadrada de la cardinalidad del tipo entero. Esto empaca un poco más eficientemente que el método más general de Stephan202. También es considerablemente más sencillo de decodificar; que no requieren raíces cuadradas, para empezar :)

bdonlan
fuente
¿Es esto posible por casualidad para flotadores?
Lukas
3

Revisa esto: http://en.wikipedia.org/wiki/Pigeonhole_principle . Si A, B y C son del mismo tipo, no se puede hacer. Si A y B son enteros de 16 bits, y C es de 32 bits, entonces simplemente puede usar el desplazamiento.

La naturaleza misma de los algoritmos de hash es que no pueden proporcionar un hash único para cada entrada diferente.

Groo
fuente
2

Aquí hay una extensión del código de @DoctorJ a enteros ilimitados basado en el método proporcionado por @nawfal. Puede codificar y decodificar. Funciona con matrices normales y matrices numpy.

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn't work with np
        raise ValueError('Cannot encode empty tuple')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError('Can only encode integers')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError('Can only encode integers (got {})'.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError('Tuple is the wrong size ({})'.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton's method, via http://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
NStarman
fuente
2

¿Qué tal algo mucho más simple? Dados dos números, A y B dejan que str sea la concatenación: 'A' + ';' + 'B'. Luego, deje que la salida sea hash (str). Sé que esta no es una respuesta matemática, pero un simple script de Python (que tiene una función hash incorporada) debería hacer el trabajo.

Madhav Nakar
fuente
2
pero (8,11) y (81,1) se asignan al mismo número 811
Leevi L
Ese es un buen punto. Puede solucionar ese problema simplemente agregando un símbolo en el medio. Entonces, para (8, 11) hash la cadena "8-11" y para (81, 1) hash la cadena "81-1". Entonces, en general, para (A, B) hash la cadena "AB". (Sé que suena raro, pero debería funcionar).
Madhav Nakar
también está mal porque esa tarea es asignar dos enteros a un nuevo entero, no una cadena con un símbolo
Leevi L
Vengo desde una perspectiva CS en lugar de una matemática (para soluciones matemáticas, mire las respuestas anteriores). Estoy tomando dos enteros, convirtiéndolos en una cadena, cuando luego se convierte en un entero. Esencialmente, sí, estoy mapeando dos enteros a uno nuevo.
Madhav Nakar
1

Lo que sugieres es imposible. Siempre tendrás colisiones.

Para asignar dos objetos a otro conjunto único, el conjunto asignado debe tener un tamaño mínimo del número de combinaciones esperadas:

Suponiendo un entero de 32 bits, tiene 2147483647 enteros positivos. Elegir dos de estos en los que el orden no importa y con la repetición produce 2305843008139952128 combinaciones. Esto no encaja bien en el conjunto de enteros de 32 bits.

Sin embargo, puede ajustar esta asignación en 61 bits. Usar un número entero de 64 bits es probablemente lo más fácil. Establezca la palabra alta en el entero más pequeño y la palabra baja en la más grande.

lc.
fuente
1

Digamos que tiene un número entero de 32 bits, ¿por qué no simplemente mueve A a la primera mitad de 16 bits y B a la otra?

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

Además de ser tan eficiente en espacio como sea posible y barato de calcular, un efecto secundario realmente genial es que puedes hacer cálculos vectoriales en el número empaquetado.

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication
Stuffe
fuente
0

tengamos dos números B y C, codificándolos en un solo número A

A = B + C * N

dónde

B = A% N = B

C = A / N = C

Ankur Chauhan
fuente
2
¿Cómo eliges N para hacer que esta representación sea única? Si resuelve ese problema, ¿en qué se diferencia esta respuesta de las anteriores?
Pode el
Debe agregar que N debe ser mayor que B y C.
Radoslav Stoyanov
0

Dados los enteros positivos A y B, supongamos que D = número de dígitos A tiene, y E = número de dígitos B tiene El resultado puede ser una concatenación de D, 0, E, 0, A y B.

Ejemplo: A = 300, B = 12. D = 3, E = 2 resultado = 302030012. Esto aprovecha el hecho de que el único número que comienza con 0, es 0,

Pro: fácil de codificar, fácil de decodificar, legible por humanos, se pueden comparar primero dígitos significativos, potencial de comparación sin cálculo, simple verificación de errores.

Contras: el tamaño de los resultados es un problema. Pero está bien, ¿por qué estamos almacenando enteros ilimitados en una computadora?

Ban Piao
fuente
0

Si desea más control, como asignar bits X para el primer número e bits Y para el segundo número, puede usar este código:

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

Yo uso 32 bits en total. La idea aquí es que si desea, por ejemplo, que el primer número tenga hasta 10 bits y el segundo número tenga hasta 12 bits, puede hacer esto:

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

Ahora puede almacenar en num_ael número máximo que es 2^10 - 1 = 1023y en el num_bvalor máximo de 2^12 - 1 = 4095.

Para establecer el valor para num A y num B:

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

Ahora bnumes todos los bits (32 bits en total. Puede modificar el código para usar 64 bits) Para obtener num a:

int a = nums_mapper.GetNumA(bnum);

Para obtener num b:

int b = nums_mapper.GetNumB(bnum);

EDITAR: bnumse puede almacenar dentro de la clase. No lo hice porque mis propias necesidades compartí el código y espero que sea útil.

Gracias por la fuente: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ por la función para extraer bits y gracias también por mouvicielresponder en esta publicación. Usando estos para las fuentes podría encontrar una solución más avanzada

gil123
fuente