Mapeando dois números inteiros para um, de maneira única e determinística

235

Imagine dois números inteiros positivos A e B. Eu quero combinar esses dois em um único número C.

Não pode haver outros números inteiros D e E combinados com C. Portanto, combiná-los com o operador de adição não funciona. Por exemplo, 30 + 10 = 40 = 40 + 0 = 39 + 1 Nem a concatinação funciona. Por exemplo, "31" + "2" = 312 = "3" + "12"

Essa operação de combinação também deve ser determinística (sempre produz o mesmo resultado com as mesmas entradas) e sempre deve gerar um número inteiro no lado positivo ou negativo dos números inteiros.

prejuízo
fonte
10
Você deve esclarecer se quer dizer números inteiros em software ou números inteiros em matemática. No software, você escolhe qualquer tipo de número inteiro e ele terá um tamanho, assim você terá um número finito deles, para que não haja solução (a menos que, é claro, seus dados de entrada estejam dentro de um intervalo e a saída possa ser qualquer número inteiro). Em matemática, veja a solução da ASk.
Daniel Daranas
Estou falando de números inteiros limitados em um intervalo baixo e positivo. Diga 0 a 10.000
dano
27
@harm: Então, que tal 10,001*A + B?
BlueRaja - Danny Pflughoeft
2
Eu encontrei estas funções PHP: gist.github.com/hannesl/8031402
cakan
Se a ordem não importa por exemplo: (3,12) e (12,3) dão o mesmo resultado, eu uso "A + B" + "A * B"
Sodj

Respostas:

233

Você está procurando um NxN -> Nmapeamento bijetivo . Estes são utilizados para, por exemplo, encaixe . Consulte este PDF para obter uma introdução às chamadas funções de emparelhamento . A Wikipedia introduz uma função de emparelhamento específica, a saber, a função de emparelhamento Cantor :

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

Três observações:

  • Como outros deixaram claro, se você planeja implementar uma função de emparelhamento, em breve poderá achar que você precisa de números inteiros arbitrariamente grandes (bignums).
  • Se você não quiser fazer uma distinção entre os pares (a, b) e (b, a), classifique aeb antes de aplicar a função de emparelhamento.
  • Na verdade eu menti. Você está procurando um ZxZ -> Nmapeamento bijetivo . A função do Cantor funciona apenas em números não negativos. No entanto, isso não é um problema, porque é fácil definir uma bijeção f : Z -> N, assim:
    • f (n) = n * 2 se n> = 0
    • f (n) = -n * 2-1 se n <0
Stephan202
fonte
13
+1 Acho que esta é a resposta correta para números inteiros ilimitados.
Desconhecido
4
Como posso obter novamente o valor de k1, k2?
MinuMaster 22/04/12
3
@MinuMaster: descrito no mesmo artigo da Wikipedia, em Invertendo a função de emparelhamento Cantor .
precisa saber é o seguinte
4
Veja também a função de Szudzik, explicada por newfal abaixo.
OliJG
1
Embora isso esteja correto para números inteiros ilimitados, não é melhor para números inteiros limitados. Acho que o comentário de @ blue-raja faz mais sentido de longe.
Kardasis
226

A função de emparelhamento Cantor é realmente uma das melhores por aí, considerando sua simplicidade, rapidez e eficiência de espaço, mas há algo ainda melhor publicado na Wolfram por Matthew Szudzik, aqui . A limitação da função de emparelhamento do Cantor (relativamente) é que o intervalo de resultados codificados nem sempre fica dentro dos limites de um 2Nnúmero inteiro de bits se as entradas forem Nnúmeros inteiros de dois bits. Ou seja, se minhas entradas são 16números inteiros de dois bits que variam de 0 to 2^16 -1, então existem 2^16 * (2^16 -1)combinações de entradas possíveis; portanto, pelo óbvio Princípio Pigeonhole , precisamos de uma saída de tamanho, pelo menos 2^16 * (2^16 -1), igual a 2^32 - 2^16, ou seja, um mapa de32números de bits devem ser viáveis ​​idealmente. Isso pode não ter pouca importância prática no mundo da programação.

Função de emparelhamento Cantor :

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

O mapeamento para dois números inteiros máximos de 16 bits (65535, 65535) será 8589803520 que, como você vê, não pode caber em 32 bits.

Entre na função de Szudzik :

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

O mapeamento para (65535, 65535) agora será 4294967295 que, como você vê, é um número inteiro de 32 bits (0 a 2 ^ 32 -1). É aqui que esta solução é ideal, ela simplesmente utiliza todos os pontos desse espaço, para que nada possa ser mais eficiente em termos de espaço.


Agora, considerando o fato de que normalmente lidamos com implementações assinadas de números de vários tamanhos em idiomas / estruturas, vamos considerar signed 16números inteiros de bits que variam de -(2^15) to 2^15 -1(mais tarde veremos como estender até a saída para abranger o intervalo assinado). Desde ae btem que ser positivo eles variam de 0 to 2^15 - 1.

Função de emparelhamento Cantor :

O mapeamento para dois números inteiros máximos assinados com mais de 16 bits (32767, 32767) será 2147418112, que está um pouco abaixo do valor máximo para o número inteiro assinado de 32 bits.

Agora a função de Szudzik :

(32767, 32767) => 1073741823, muito menor ..

Vamos considerar números inteiros negativos. Isso está além da pergunta original que eu conheço, mas apenas elaborando para ajudar futuros visitantes.

Função de emparelhamento 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 é Int64. A saída de 64 bits para entradas de 16 bits pode ser tão imperdoável!

Função 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 é de 32 bits para o intervalo não assinado ou de 64 bits para o intervalo assinado, mas ainda melhor.

Agora, tudo isso enquanto a saída sempre foi positiva. No mundo assinado, economizará ainda mais espaço se pudermos transferir metade da saída para o eixo negativo . Você poderia fazer isso para o 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

O que eu faço: Depois de aplicar um peso de 2às entradas e passar pela função, divido a saída por duas e levo algumas delas para o eixo negativo multiplicando por -1.

Veja os resultados, para qualquer entrada no intervalo de um 16número de bit assinado , a saída está dentro dos limites de um 32número inteiro de bits assinado, o que é legal. Não sei como proceder da mesma maneira para a função de emparelhamento Cantor, mas não tentei tanto quanto não é tão eficiente. Além disso, mais cálculos envolvidos na função de emparelhamento Cantor também são mais lentos .

Aqui está uma implementação em 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 os cálculos intermediários podem exceder os limites do 2Nnúmero inteiro assinado, usei o 4Ntipo inteiro (a última divisão por 2traz de volta o resultado para 2N).

O link que forneci em uma solução alternativa mostra um gráfico da função utilizando cada ponto no espaço. É incrível ver que você pode codificar exclusivamente um par de coordenadas para um único número reversível! Mundo mágico dos números !!

nawfal
fonte
5
Qual seria a função unhash modificada para números inteiros assinados?
Arets Paeglis
7
Essa resposta me confunde. Se você deseja mapear (0,0)até (65535,65535)um único número, a<<16 + bé basicamente melhor em todos os sentidos (mais rápido, mais simples, mais fácil de entender, mais óbvio) . Se você quiser (-32768,-32768)para (327687,327687)em vez disso, apenas sujeita 32768 em primeiro lugar.
BlueRaja - Danny Pflughoeft
2
@ BlueRaja-DannyPflughoeft você está certo. Minha resposta seria válida se o intervalo não for limitado ou desconhecido. Vou atualizá-lo. Eu o escrevi antes que o limite me importasse. A edição desta resposta está há muito tempo em minha mente. Vou encontrar tempo em breve.
Nawfal 15/05
A função de Szudzik funciona para combinações ou permutações. Parece ser permutações, certo? Se eu quiser usar o Combination, posso simplesmente eliminar as partes IF e Else do algoritmo?
Jamie Marshall
Aqui está uma implementação em Python da função de Szudzik generalizada para tuplas de qualquer tamanho: gitlab.com/snippets/32559
Doutor J
47

Se A e B puderem ser expressos com 2 bytes, você poderá combiná-los em 4 bytes. Coloque A na metade mais significativa e B na metade menos significativa.

Na linguagem C, isso fornece (assumindo sizeof (short) = 2 e 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
fonte
3
combine()deve return (unsigned short)(A<<16) | (unsigned short)(B); Assim que os números negativos podem ser embalados adequadamente.
Andy
2
@ Andy A<<16ficará fora dos limites. Deveria serreturn (unsigned int)(A<<16) | (unsigned short)(B);
DanSkeel 31/03
15

Isso é possível?
Você está combinando dois números inteiros. Ambos têm o intervalo de -2.147.483.648 a 2.147.483.647, mas você só aceita os positivos. Isso faz 2147483647 ^ 2 = 4,61169E + 18 combinações. Como cada combinação deve ser única E resultar em um número inteiro, você precisará de algum tipo de número inteiro mágico que possa conter essa quantidade de números.

Ou minha lógica é falha?

Boris Callens
fonte
+1 É o que eu penso também (embora eu tenha feito o cálculo dizendo que a ordem de A e B não importa)
lc.
4
Sim, sua lógica está correta pelo princípio do buraco de pombo. Infelizmente, o autor da pergunta não especificou se o número inteiro é limitado ou não.
Desconhecido
Sim, eu também tive essa ideia, mas achei que a mensagem é essencialmente a mesma, então não me incomodei em recalcular.
Boris Callens 28/05/09
Também acabei de perceber que deveria pegar meus livros didáticos de cálculo de chances (tradução literal do holandês) novamente.
Boris Callens 28/05/09
2
@ Boris: Kansrekening é "teoria das probabilidades".
2020 Stephan202
8

A maneira matemática padrão para números inteiros positivos é usar a singularidade da fatoração primária.

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

A desvantagem é que a imagem tende a abranger uma gama bastante grande de números inteiros; portanto, quando se trata de expressar o mapeamento em um algoritmo de computador, você pode ter problemas com a escolha de um tipo apropriado para o resultado.

Você pode modificar isso para lidar com negativos xe ycodificar um sinalizador com poderes de 5 e 7 termos.

por exemplo

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
CB Bailey
fonte
A matemática está bem. Mas, como Boris diz, se você deseja executar isso como um programa de computador, deve levar em consideração a finura da máquina. O algoritmo funcionará corretamente para um subconjunto de números inteiros representáveis ​​na máquina relevante.
Yuval F
2
Afirmei isso no meu segundo parágrafo. As tags na pergunta indicam 'algoritmo', 'matemático' e 'determinístico', não uma linguagem específica. O intervalo de entrada pode não ser limitado e o ambiente pode ter um tipo inteiro ilimitado 'bigint'.
CB Bailey
8

Seja o número ao primeiro, bo segundo. Seja po a+1-ésimo número primo, qseja o b+1-ésimo número primo

Então, o resultado é pq, se a<b,ou 2pqse a>b. Se a=b, deixe estar p^2.

ASk
fonte
4
Duvido que você queira uma solução NP.
User44242
1
Isso não produz o mesmo resultado para a = 5, b = 14 e a = 6, b = 15?
Lieven Keersmaekers
3
Dois produtos de dois primos diferentes não podem ter o mesmo resultado (decomposição exclusiva do fator primo) a = 5, b = 14 -> resultado é 13 * 47 = 611 a = 6, b = 15 -> resultado é 17 * 53 = 901
Pergunte
4

Não é tão difícil construir um mapeamento:

   1 2 3 4 5 use esse mapeamento se (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 esse mapeamento se (a, b) == (b, a) (espelho)
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-o se precisar de 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

Descobrir como obter o valor de um a, b arbitrário é um pouco mais difícil.

Golfinho
fonte
4

f(a, b) = s(a+b) + a, Onde s(n) = n*(n+1)/2

  • Esta é uma função - é determinística.
  • Também é injetivo - f mapeia valores diferentes para pares diferentes (a, b). Você pode provar isso usando o fato: s(a+b+1)-s(a+b) = a+b+1 < a.
  • Ele retorna valores muito pequenos - bom se você for usá-lo para indexação de array, pois o array não precisa ser grande.
  • É compatível com o cache - se dois pares (a, b) estão próximos, f mapeia números para eles que estão próximos um do outro (em comparação com outros métodos).

Não entendi o que você quer dizer com:

deve sempre produzir um número inteiro no lado positivo ou negativo dos números inteiros

Como posso escrever (maior que), (menor que) caracteres neste fórum?

libeako
fonte
2
Caracteres maiores que e menores que devem funcionar bem por dentro backtick escapes.
TRiG
Isso é equivalente à função de emparelhamento do Cantor e, como tal, não funciona com números inteiros negativos.
Davor Josipovic
4

Embora a resposta de Stephan202 seja a única verdadeiramente geral, para números inteiros em um intervalo limitado, você pode fazer melhor. Por exemplo, se seu intervalo for 0..10.000, você poderá:

#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));
}

Os resultados podem caber em um único inteiro para um intervalo até a raiz quadrada da cardinalidade do tipo inteiro. Isso é um pouco mais eficiente que o método mais geral do Stephan202. Também é consideravelmente mais simples de decodificar; sem raízes quadradas, para iniciantes :)

bdonlan
fonte
Por acaso isso é possível para carros alegóricos?
Lukas
3

Verifique isto: http://en.wikipedia.org/wiki/Pigeonhole_principle . Se A, B e C são do mesmo tipo, isso não pode ser feito. Se A e B são inteiros de 16 bits e C é de 32 bits, você pode simplesmente usar o deslocamento.

A própria natureza dos algoritmos de hash é que eles não podem fornecer um hash exclusivo para cada entrada diferente.

Groo
fonte
2

Aqui está uma extensão do código de @DoctorJ para números inteiros ilimitados com base no método fornecido por @nawfal. Pode codificar e decodificar. Funciona com matrizes normais e matrizes 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
fonte
2

Que tal algo muito mais simples: dados dois números, A e B permitem que str seja a concatenação: 'A' + ';' + 'B'. Então deixe a saída ser hash (str). Eu sei que essa não é uma resposta matemática, mas um script python simples (que possui uma função de hash integrada) deve fazer o trabalho.

Madhav Nakar
fonte
2
mas (8,11) e (81,1) são mapeados para o mesmo número 811
Leevi L
Essa é uma boa opinião. Você pode corrigir esse problema, apenas adicionando um símbolo no meio. Portanto, para (8, 11) o hash da cadeia "8-11" e para (81, 1) o hash da cadeia "81-1". Então, em geral, para (A, B) o hash "AB" é o hash. (Eu sei que parece hacky, mas deve funcionar).
Madhav Nakar
sua também errado, porque essa tarefa é mapear dois inteiros para um novo inteiro, não uma string com um símbolo
Leevi L
Estou vindo de uma perspectiva de CS em vez de matemática (para soluções matemáticas, observe as respostas acima). Estou pegando dois números inteiros, transformando-os em uma string, quando então é transformado em um número inteiro. Basicamente, sim, estou mapeando dois números inteiros para um novo.
Madhav Nakar
1

O que você sugere é impossível. Você sempre terá colisões.

Para mapear dois objetos para outro conjunto único, o conjunto mapeado deve ter um tamanho mínimo do número de combinações esperado:

Supondo um número inteiro de 32 bits, você tem 2147483647 números inteiros positivos. A escolha de duas delas em que a ordem não importa e com a repetição produz 2305843008139952128 combinações. Isso não se encaixa muito bem no conjunto de números inteiros de 32 bits.

No entanto, você pode ajustar esse mapeamento em 61 bits. Usar um número inteiro de 64 bits é provavelmente mais fácil. Defina a palavra alta para o número inteiro menor e a palavra baixa para o número maior.

lc.
fonte
1

Digamos que você tenha um número inteiro de 32 bits, por que não mover A para o primeiro meio de 16 bits e B para o outro?

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


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

Além de ser o mais eficiente possível em termos de espaço e barato de calcular, um efeito colateral muito interessante é que você pode fazer cálculos vetoriais no número compactado.

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
fonte
0

vamos ter dois números B e C, codificando-os em um único número A

A = B + C * N

Onde

B = A% N = B

C = A / N = C

Ankur Chauhan
fonte
2
Como você escolhe N para tornar essa representação única? Se você resolver esse problema, como essa resposta é diferente das respostas acima?
ameixa
Você deve acrescentar que N deve ser maior do que ambos B e C.
Radoslav Stoyanov
0

Dados inteiros positivos A e B, seja D = número de dígitos A e E = número de dígitos B tem O resultado pode ser uma concatenação de D, 0, E, 0, A e B.

Exemplo: A = 300, B = 12. D = 3, E = 2 resultado = 302030012. Isso aproveita o fato de que o único número que começa com 0 é 0,

Pro: fácil de codificar, fácil de decodificar, legível por humanos, dígitos significativos podem ser comparados primeiro, potencial para comparação sem cálculo, simples verificação de erro.

Contras: O tamanho dos resultados é um problema. Mas tudo bem, por que estamos armazenando números inteiros ilimitados em um computador?

Ban Piao
fonte
0

Se você deseja mais controle, como alocar bits X para o primeiro número e bits Y para o segundo número, você pode 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);
    }
};

Eu uso 32 bits no total. A idéia aqui é que, se você quiser, por exemplo, que o primeiro número tenha até 10 bits e o segundo número tenha até 12 bits, faça o seguinte:

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

Agora você pode armazenar no num_anúmero máximo que é 2^10 - 1 = 1023e no num_bvalor máximo de 2^12 - 1 = 4095.

Para definir o valor para os números A e B:

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

Agora bnumsão todos os bits (total de 32 bits. Você pode modificar o código para usar 64 bits) Para obter o num a:

int a = nums_mapper.GetNumA(bnum);

Para obter o número b:

int b = nums_mapper.GetNumB(bnum);

EDIT: bnumpode ser armazenado dentro da classe. Não fiz isso porque compartilhei o código com minhas próprias necessidades e espero que seja útil.

Obrigado pela fonte: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ pela função de extrair bits e obrigado também por mouvicielresponder neste post. Usando essas fontes, pude descobrir uma solução mais avançada

gil123
fonte