A resposta do Lucas Virgili explica bem o raciocínio por trás da pergunta (que certamente é mesmo sobre representação binária), mas gostaria de dar uma resposta um pouco mais geral:
Quando se pega um número qualquer, no abstrato, e se representa esse número em uma base, se está justamente decompondo-o em uma série de números menores. Por exemplo:
44 = 10*4 + 1*4 (base 10: 44)
= 16*2 + 1*12 (base 16: 2C)
= 32*1 + 16*0 + 8*1 + 4*1 + 2*0 + 1*0 (base 2: 101100)
E assim por diante. No caso dos números em binário, há apenas duas possibilidades: ou o componente está presente ou não está:
1, 2, 4, 8, 16, 32,...
No caso dos números em decimal, por exemplo, cada componente pode ocorrer de 0
a 9
vezes:
1,1,1,1,1,1,1,1,1, 10,10,10,10,10,10,10,10,10, 100,100,100,100,100,100,100,100,100, 1000...
E assim por diante. Para se "montar" o número 44
, pega-se 4 unidades (i.e. dentre os 9 valores 1
disponíveis pega-se 4) e 4 dezenas (dentre os 9 valores 10
disponíveis pega-se 4). Nenhuma centena, milhar, etc.
Esse raciocínio vale mesmo para bases "loucas", como por exemplo: "representar uma quantia em Reais usando o menor número possível de notas/moedas":
1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$20, R$50, R$100...
R$44 = R$20 + R$10 + R$10 + R$2 + R$2
Método reverso
A forma mais eficiente de se resolver esse problema (representar um número dado um conjunto de componentes) é se começar pelo "maior deles" (ou, se a sequência for infinita, o maior dentre eles que for menor ou igual ao número) e percorrer a lista até o início - subtraindo-se os valores encontrados até o número chegar a zero:
entrada = 44
lista = [1,2,4,8,16,32,64,128]
maior = x in lista if x <= entrada
for y from maior to 0:
if y <= entrada:
incluir y na saída
entrada -= y
Exceto pelo caso binário (onde o teste por bits é mais simples e eficiente - já que o computador te "ajuda" na tarefa com operadores binários próprios pra isso), essa seria a melhor forma de fazer, para uma entrada arbitrária [ordenada em ordem crescente, é claro].
Método direto
Lembra do primário, quando você aprendeu a fazer somas usando o QVL? O mesmo princípio pode ser utilizado, mas usando-se uma base arbitrária em vez do 10:
- Enquanto o valor a ser atingido for maior que zero:
- Pegue o menor valor da lista (unidade), e acrescente-o à saída - decrementando a entrada
- Se o menor valor da lista não estiver disponível (i.e. todas as unidades foram usadas), retire N valores da saída e troque-os por um valor de grandeza maior (dezena) - de modo que N unidades + 1 unidade seja igual a 1 dezena.
- Repita recursivamente para grandezas maiores (dezena/centena, centena/milhar, etc).
Citei esse método por curiosidade apenas, pois desnecessário dizer ele é por demais ineficiente (você estaria "contando" de 1 a 44 - complexidade O(n)
), deixo a implementação em código como exercício para o leitor... :P