5

Qual a maneira mais performática de descobrir o número mínimo de bits necessário para representar um número natural (i.e. sem sinal), em JavaScript? Há um meio de fazer sem usar loops?

O código abaixo por exemplo funciona para todo inteiro entre 0 e 2^30 - 1 (loop infinito se ele for maior que isso):

var x = 9001;
var bits = 1;
while ( x >= (1 << bits) )
    bits++;

E esse funciona até 2^53 (o maior inteiro representável garantidamente sem perda de precisão) e um tanto além:

var x = 9001;
var bits = 1;
var limite = 2;
while ( x >= limite ) {
    bits++;
    limite *= 2;
}

Mas ambos usam loops, basicamente perguntando: cabe em 1 bit? cabe em 2 bits? cabe em 3 bits? etc. Fiquei curioso em saber se há uma maneira melhor de fazer isso.

Nota: estou interessado apenas em saber quantos bits são necessários, não em realmente fazer essa representação de fato. Mesmo porque JavaScript não usa int, long, unsigned int, etc - e sim double pra tudo... (e quando usa, não expõe para o programador)

3
  • Eu soaria ainda mais estúpido do que pareço se eu perguntasse o porquê dessa pergunta? Commented 26/07/2014 às 21:47
  • @BrunoAugusto Originalmente, eu queria armazenar uma máscara de bits e um identificador único em um único Number. Pra isso eu precisava saber se o identificador (variável) "cabe" no espaço que sobra além da máscara (fixa). Enquanto escrevia a pergunta, percebi que dizer se cabe ou não é fácil - basta eu subtrair dos 53 bits disponíveis o tamanho da máscara, e ver se o identificador está entre zero e o maior número que cabe nesse espaço. Mas continuei curioso pra saber se há um meio de determinar o menor número de bits necessário, dado um número, então submeti a pergunta assim mesmo.
    – mgibsonbr
    Commented 26/07/2014 às 23:19
  • No caso geral, calcular o logaritmo de um número - mesmo aproximado - é complicado, mas no binário fica fácil: é só contar os bits à direita do último bit setado (inclusive). Mas será que dá pra fazer isso com uma operação simples? Eu não sei, e pensei que talvez alguém conhecesse um meio...
    – mgibsonbr
    Commented 26/07/2014 às 23:21

1 Resposta 1

4

Primeiro, o aspecto matemático:

Um número positivo e inteiro n tem b bits quando 2b-1 < n < 2b-1.

Isso significa dizer que, enquanto meu inteiro não ultrapassar o valor de uma dada potência de 2, a quantidade de bits necessária para expressar esse inteiro é a base dessa potência menos um. Exemplos:

Decimal   Próxima potência de 2  Bitmap      Bits necessários
511       512  (2^10)            111111111   9
967       1024 (2^11)            1111000111  10

Logo, para calcular quantos bits b são necessários para expressar um número n, podemos usar logaritmos. Assim:

binteiro = int(log2(n)) + 1

Essa fórmula pode ser dividida em três partes:

  • log2(n) significa o logaritmo em base 2 de N, que é o expoente ao qual 2 é elevado para chegar a N. Javascript não suporta cálculos de logaritmo em base diferente de 10, então precisamos dividir Math.log(n) por Math.log(2).
  • Int(x) é a parte inteira de x. Em Javascript, a função equivalente é Math.floor().
  • +1 joga o expoente para a próxima potência de 2, para compensar pela última posição de seu número em expressão binária.

Uma maneira de expressar esta fórmula em JavaScript seria:

function numBits(numero)
{
    return Math.floor( Math.log(numero) / Math.log(2) ) + 1;
}

Eu preparei um JSFiddle onde você pode testar a performance de cada método. Assuma métodos 1 e 2 como os na sua pergunta original, e 3 como sendo o desta resposta.

Meus resultados para um ciclo de 1 a 50.000.000 foram:

Método 1: 3244 ms
Método 2: 2103 ms
Método 3:  181 ms
(Browser: Google Chrome Version 36.0.1985.125)

Método 1: 1564 ms
Método 2: 2434 ms
Método 3: 2518 ms
(Browser: Internet Explorer 11)

Fontes:

5
  • 2
    Há que notar que esta solução (sem ciclos) não é necessariamente mais performant que uma solução com ciclos: isso vai depender de como o interpretador de JS vai optimizar os ciclos e de como as funções do Math estão implementadas. Commented 26/07/2014 às 16:17
  • @MiguelVentura Pois é, também pensei nisso. Logaritmo me passou pela cabeça, mas descartei logo pensando na performance. De fato, ele é mais lento (para números relativamente pequenos, pelo menos). De todo modo, +1 pelo aspecto matemático.
    – mgibsonbr
    Commented 26/07/2014 às 16:39
  • A propósito, eu achei que a solução com ciclos seria melhor para números pequenos, e a com logaritmo melhor para números grandes, mas não é o que observei. Provavelmente, o cálculo do logaritmo não é mesmo feito em tempo constante...
    – mgibsonbr
    Commented 26/07/2014 às 16:51
  • P.S. De fato, no Chrome é mais rápido para números muito grandes! Provavelmente o algoritmo deles de log é melhor
    – mgibsonbr
    Commented 26/07/2014 às 16:56
  • Pois é - curioso, não? Fiquei com vontade de testar em outros browsers...
    – OnoSendai
    Commented 26/07/2014 às 16:58

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .