Algoritmos – Conversão Binária – Parte 01

Introdução

Existem casos em APIs e integrações onde é necessária por exemplo converter um número para uma string em formato binário, apenas com os caracteres “0” (zero) e “1” (um). Vamos ver uma forma de fazer isso na velocidade da luz?

Funções nToBit8() , nToBit16() e nToBitS()

A função nToBit8() recebe um número entre 0 e 255, e retorna a string binária com tamanho de 8 caracteres, já a nToBit16() converte um número entre 0 e 65535 retornando uma string de 16 caracteres. Já a função nToBitS() é capaz de converter um número inteiro decimal de até 14 dígitos para binário, realizando duas operações aritméticas para cada bloco de 8 bits.

Normalmente uma conversão de um número em base 10 (decimal) para base 2 (binária) exige cálculos matemáticos — divisões, módulo — e comparações. Porém, a alternativa mais rápida neste caso é gastar um pouco de memória, para fazer um cache da conversão de um byte ( 256 valores diferentes ) para a string binária, colocar em um array STATIC — carregado apenas uma vez — e depois recuperar o resultado diretamente de um elemento do array, sem comparação ou aritmética nenhuma. Para retornar um binário de 16 bits, fazemos apenas duas operações aritméticas e montamos o resultado concatenando dois elementos do cache.  Vamos ao código de exemplo e da implementação:

USER Function tstbits()
Local nI,nJ
Local cTmp
Local nTimer

// Conversao de 0 a 1023 em string de 16 caracteres
For nI := 0 to 1023
	conout(ntobit16(nI))
Next

// Teste de desempenho 
nTimer := seconds()
For nI := 1 to 10000
	For nJ := 0 to 255
               cTmp := ntobit8(nJ)	              
	Next
Next
Conout("Tempo ..... "+str(seconds()-nTimer,12,3)+" s.")
Return


// Carga automatica do cache 
STATIC _Bits := LoadBits()


// NTOBIT8
// Funcao de Conversao de um numero entre 0 e 255 
// para uma string de 8 bytes contendo os caracteres "0" e "1"
// Tempo O(1) 

STATIC Function NTOBIT8(nI)
Return _Bits[nI+1]

// NTOBIT16
// Converte um numero entre 0 e 65535 
// para uma string de 16 bytes contendo os caracteres "0" e "1"
// Tempo O(1) 
STATIC Function NTOBIT16(nI)
Local n1,n2
If nI > 255
	n2 := ( nI%256 )
	n1 := ( nI - n2 ) / 256 
Else
	n1 := 0 
	n2 := nI
Endif  
Return _Bits[n1+1]+_Bits[n2+1]

// Funcao NTOBITS()
// Converte qualquer numero decimal de até 14 dígitos inteiros 
// do AdvPL para formato binário em blocos de 8 bits 
STATIC Function NTOBITS(nI)
Local nTmp
Local cBitsRet  := ''
While nI > 256  
	nTmp := nI % 256
	cBitsRet := _Bits[nTmp+1] + cBitsRet
	nI := ( nI - nTmp ) / 256
Enddo
cBitsRet := _Bits[nI+1] + cBitsRet
Return cBitsRet
// Carga do cache de conversão numérica para binário 
STATIC Function LoadBits()
     
If _Bits = NIL 
      
_Bits := {}

AADD(_Bits,'00000000')
AADD(_Bits,'00000001')
AADD(_Bits,'00000010')
AADD(_Bits,'00000011')
AADD(_Bits,'00000100')
AADD(_Bits,'00000101')
AADD(_Bits,'00000110')
AADD(_Bits,'00000111')
AADD(_Bits,'00001000')
AADD(_Bits,'00001001')
AADD(_Bits,'00001010')
AADD(_Bits,'00001011')
AADD(_Bits,'00001100')
AADD(_Bits,'00001101')
AADD(_Bits,'00001110')
AADD(_Bits,'00001111')
AADD(_Bits,'00010000')
AADD(_Bits,'00010001')
AADD(_Bits,'00010010')
AADD(_Bits,'00010011')
AADD(_Bits,'00010100')
AADD(_Bits,'00010101')
AADD(_Bits,'00010110')
AADD(_Bits,'00010111')
AADD(_Bits,'00011000')
AADD(_Bits,'00011001')
AADD(_Bits,'00011010')
AADD(_Bits,'00011011')
AADD(_Bits,'00011100')
AADD(_Bits,'00011101')
AADD(_Bits,'00011110')
AADD(_Bits,'00011111')
AADD(_Bits,'00100000')
AADD(_Bits,'00100001')
AADD(_Bits,'00100010')
AADD(_Bits,'00100011')
AADD(_Bits,'00100100')
AADD(_Bits,'00100101')
AADD(_Bits,'00100110')
AADD(_Bits,'00100111')
AADD(_Bits,'00101000')
AADD(_Bits,'00101001')
AADD(_Bits,'00101010')
AADD(_Bits,'00101011')
AADD(_Bits,'00101100')
AADD(_Bits,'00101101')
AADD(_Bits,'00101110')
AADD(_Bits,'00101111')
AADD(_Bits,'00110000')
AADD(_Bits,'00110001')
AADD(_Bits,'00110010')
AADD(_Bits,'00110011')
AADD(_Bits,'00110100')
AADD(_Bits,'00110101')
AADD(_Bits,'00110110')
AADD(_Bits,'00110111')
AADD(_Bits,'00111000')
AADD(_Bits,'00111001')
AADD(_Bits,'00111010')
AADD(_Bits,'00111011')
AADD(_Bits,'00111100')
AADD(_Bits,'00111101')
AADD(_Bits,'00111110')
AADD(_Bits,'00111111')
AADD(_Bits,'01000000')
AADD(_Bits,'01000001')
AADD(_Bits,'01000010')
AADD(_Bits,'01000011')
AADD(_Bits,'01000100')
AADD(_Bits,'01000101')
AADD(_Bits,'01000110')
AADD(_Bits,'01000111')
AADD(_Bits,'01001000')
AADD(_Bits,'01001001')
AADD(_Bits,'01001010')
AADD(_Bits,'01001011')
AADD(_Bits,'01001100')
AADD(_Bits,'01001101')
AADD(_Bits,'01001110')
AADD(_Bits,'01001111')
AADD(_Bits,'01010000')
AADD(_Bits,'01010001')
AADD(_Bits,'01010010')
AADD(_Bits,'01010011')
AADD(_Bits,'01010100')
AADD(_Bits,'01010101')
AADD(_Bits,'01010110')
AADD(_Bits,'01010111')
AADD(_Bits,'01011000')
AADD(_Bits,'01011001')
AADD(_Bits,'01011010')
AADD(_Bits,'01011011')
AADD(_Bits,'01011100')
AADD(_Bits,'01011101')
AADD(_Bits,'01011110')
AADD(_Bits,'01011111')
AADD(_Bits,'01100000')
AADD(_Bits,'01100001')
AADD(_Bits,'01100010')
AADD(_Bits,'01100011')
AADD(_Bits,'01100100')
AADD(_Bits,'01100101')
AADD(_Bits,'01100110')
AADD(_Bits,'01100111')
AADD(_Bits,'01101000')
AADD(_Bits,'01101001')
AADD(_Bits,'01101010')
AADD(_Bits,'01101011')
AADD(_Bits,'01101100')
AADD(_Bits,'01101101')
AADD(_Bits,'01101110')
AADD(_Bits,'01101111')
AADD(_Bits,'01110000')
AADD(_Bits,'01110001')
AADD(_Bits,'01110010')
AADD(_Bits,'01110011')
AADD(_Bits,'01110100')
AADD(_Bits,'01110101')
AADD(_Bits,'01110110')
AADD(_Bits,'01110111')
AADD(_Bits,'01111000')
AADD(_Bits,'01111001')
AADD(_Bits,'01111010')
AADD(_Bits,'01111011')
AADD(_Bits,'01111100')
AADD(_Bits,'01111101')
AADD(_Bits,'01111110')
AADD(_Bits,'01111111')
AADD(_Bits,'10000000')
AADD(_Bits,'10000001')
AADD(_Bits,'10000010')
AADD(_Bits,'10000011')
AADD(_Bits,'10000100')
AADD(_Bits,'10000101')
AADD(_Bits,'10000110')
AADD(_Bits,'10000111')
AADD(_Bits,'10001000')
AADD(_Bits,'10001001')
AADD(_Bits,'10001010')
AADD(_Bits,'10001011')
AADD(_Bits,'10001100')
AADD(_Bits,'10001101')
AADD(_Bits,'10001110')
AADD(_Bits,'10001111')
AADD(_Bits,'10010000')
AADD(_Bits,'10010001')
AADD(_Bits,'10010010')
AADD(_Bits,'10010011')
AADD(_Bits,'10010100')
AADD(_Bits,'10010101')
AADD(_Bits,'10010110')
AADD(_Bits,'10010111')
AADD(_Bits,'10011000')
AADD(_Bits,'10011001')
AADD(_Bits,'10011010')
AADD(_Bits,'10011011')
AADD(_Bits,'10011100')
AADD(_Bits,'10011101')
AADD(_Bits,'10011110')
AADD(_Bits,'10011111')
AADD(_Bits,'10100000')
AADD(_Bits,'10100001')
AADD(_Bits,'10100010')
AADD(_Bits,'10100011')
AADD(_Bits,'10100100')
AADD(_Bits,'10100101')
AADD(_Bits,'10100110')
AADD(_Bits,'10100111')
AADD(_Bits,'10101000')
AADD(_Bits,'10101001')
AADD(_Bits,'10101010')
AADD(_Bits,'10101011')
AADD(_Bits,'10101100')
AADD(_Bits,'10101101')
AADD(_Bits,'10101110')
AADD(_Bits,'10101111')
AADD(_Bits,'10110000')
AADD(_Bits,'10110001')
AADD(_Bits,'10110010')
AADD(_Bits,'10110011')
AADD(_Bits,'10110100')
AADD(_Bits,'10110101')
AADD(_Bits,'10110110')
AADD(_Bits,'10110111')
AADD(_Bits,'10111000')
AADD(_Bits,'10111001')
AADD(_Bits,'10111010')
AADD(_Bits,'10111011')
AADD(_Bits,'10111100')
AADD(_Bits,'10111101')
AADD(_Bits,'10111110')
AADD(_Bits,'10111111')
AADD(_Bits,'11000000')
AADD(_Bits,'11000001')
AADD(_Bits,'11000010')
AADD(_Bits,'11000011')
AADD(_Bits,'11000100')
AADD(_Bits,'11000101')
AADD(_Bits,'11000110')
AADD(_Bits,'11000111')
AADD(_Bits,'11001000')
AADD(_Bits,'11001001')
AADD(_Bits,'11001010')
AADD(_Bits,'11001011')
AADD(_Bits,'11001100')
AADD(_Bits,'11001101')
AADD(_Bits,'11001110')
AADD(_Bits,'11001111')
AADD(_Bits,'11010000')
AADD(_Bits,'11010001')
AADD(_Bits,'11010010')
AADD(_Bits,'11010011')
AADD(_Bits,'11010100')
AADD(_Bits,'11010101')
AADD(_Bits,'11010110')
AADD(_Bits,'11010111')
AADD(_Bits,'11011000')
AADD(_Bits,'11011001')
AADD(_Bits,'11011010')
AADD(_Bits,'11011011')
AADD(_Bits,'11011100')
AADD(_Bits,'11011101')
AADD(_Bits,'11011110')
AADD(_Bits,'11011111')
AADD(_Bits,'11100000')
AADD(_Bits,'11100001')
AADD(_Bits,'11100010')
AADD(_Bits,'11100011')
AADD(_Bits,'11100100')
AADD(_Bits,'11100101')
AADD(_Bits,'11100110')
AADD(_Bits,'11100111')
AADD(_Bits,'11101000')
AADD(_Bits,'11101001')
AADD(_Bits,'11101010')
AADD(_Bits,'11101011')
AADD(_Bits,'11101100')
AADD(_Bits,'11101101')
AADD(_Bits,'11101110')
AADD(_Bits,'11101111')
AADD(_Bits,'11110000')
AADD(_Bits,'11110001')
AADD(_Bits,'11110010')
AADD(_Bits,'11110011')
AADD(_Bits,'11110100')
AADD(_Bits,'11110101')
AADD(_Bits,'11110110')
AADD(_Bits,'11110111')
AADD(_Bits,'11111000')
AADD(_Bits,'11111001')
AADD(_Bits,'11111010')
AADD(_Bits,'11111011')
AADD(_Bits,'11111100')
AADD(_Bits,'11111101')
AADD(_Bits,'11111110')
AADD(_Bits,'11111111')

Endif

Return _Bits

Para se ter uma ideia de desempenho, o teste no meu ambiente realizou a conversão 2.560.000 conversões em 1,932 segundos. Usando uma função que aplica a regra básica de conversão para binário (), o tempo aumentou para 28 segundos para processar a mesma massa de dados. Veja abaixo como uma função “tradicional” de conversão binária poderia ser implementada:

Static function slowbit8(nNum)
LOcal cBits := ""
Local nMod
While nNum > 0    
	nMod := nNum % 2 
	cBits := IIF( nMod > 0 , '1' , '0') + cBits
	nNum :=  ( ( nNum - nMod ) / 2 )
Enddo
Return padl(cBits,8,"0")

Conclusão

Não é toda hora que precisamos disso, mas quando precisar, que seja rápido !!! Existe uma terceira forma bem eficiente, sem gastar 256 elementos cacheados na memória, sem envolver divisão e módulo, porém usando comparação e subtrações , mas muito eficaz — embora com um fonte maior, a função fez o mesmo processamento de teste em apenas 6,8  segundos:

Static Function FastBit8(nNum)
Local cStrBit := ''
IF nNum > 127
	cStrBit += '1'
	nNum -= 128
Else 
	cStrBit += '0'
Endif	
IF nNum > 63
	cStrBit += '1'
	nNum -= 64
Else 
	cStrBit += '0'
Endif	
IF nNum > 31
	cStrBit += '1'
	nNum -= 32
Else 
	cStrBit += '0'
Endif	
IF nNum > 15
	cStrBit += '1'
	nNum -= 16
Else 
	cStrBit += '0'
Endif	
IF nNum > 7
	cStrBit += '1'
	nNum -= 8
Else 
	cStrBit += '0'
Endif	     
IF nNum > 3
	cStrBit += '1'
	nNum -= 4
Else 
	cStrBit += '0'
Endif	
IF nNum > 1
	cStrBit += '1'
	nNum -= 2
Else 
	cStrBit += '0'
Endif	
IF nNum > 0
	cStrBit += '1'
Else 
	cStrBit += '0'
Endif	
Return cStrBit

Agradeço novamente a audiência e desejo a todos TERABYTES DE SUCESSO !!!

Referências

 

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s