De quantos bits eu preciso?

Neste post, vamos criar um algoritmo que nos diz o número de bits que são necessários para representar um dado valor inteiro. Por exemplo, na linguagem C++ o tipo de dado long int permite armazenar valores com até 31 bits além do bit de sinal. Ou seja a declaração abaixo nos permite armazenar inteiros que vão de −2147483648 a 2147483647.

long int a = 2174483647;

O algoritmo que vamos criar é semelhante a função sizeof(var) que retorna o tamanho de uma variável em bytes, no entanto nosso código retornará o tamanho mínimo em bits que é necessário para representar um valor.

A abordagem é mais uma vez "indutiva". O esquema que criaremos é semelhante ao apresentado no post que discutimos a conversão de um valor decimal para binário.

Projeto indutivo:

• Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido, ou seja, precisamos de apenas 1 bit.
• Hipótese de indução: Nós podemos assumir que já sabemos quantos são os n - 1 bits que são necessários para a nossa representação binária. Essa é a etapa mais interessante e criativa no processo indutivo =D.
• Caso geral: Agora basta estender a solução adicionando 1 a resposta que a hipótese de indução nos deu. E assim obteremos a quantidade total de bits que são necessários para representar o valor desejado.

Agora é só escrever o código, a linguagem de programação que será utilizada é o que menos interessa. No entanto, saber "o que" deve ser feito é um pré-requisito básico para irmos a etapa seguinte, ou seja, a etapa do "como fazer". A linguagem Haskell é ótima para esse tipo de demostração, pois é puramente funcional/indutiva, e aproxima o "o que fazer" do "como fazer".

• Implementação em Haskell

numberBits :: Int -> Int
numberBits 0 = 1
numberBits 1 = 1
numberBits n = 1 + numberBits(n `div` 2)