Bitwise: Multiplicando números inteiros

Nesse artigo quero mostrar como realizar a multiplicação de números inteiros utilizando apenas os operadores de bitwise da linguagem Java. Esses operadores realizam alterações diretamente nos bits e são extremamente rápidos.

A ideia para esse artigo surgiu de um exercício de lógica de programação que pedia para implementar um método de multiplicação de inteiros sem utilizar o operador da linguagem( * ). Esse é um exercício bem simples e a implementação mais comum pode ser escrita da seguinte maneira:



public static int multiplicar( int numero1, int numero2 ) {

int resultado = 0;

for( int i = 0; i < numero1; i++ )
resultado += numero2;

return resultado;
}

Esse método funciona, mas é lento… Utilizando operadores bitwise é possível implementar um método bem mais eficiente…

Apesar de oferecer maior desempenho, utilizar operadores de bitwise é mais trabalhoso e exige um pouco mais de prática. Por isso, é fortemente recomendado, antes de continuar, que seja feita a leitura desse outro artigo: http://www.prminformatica.com.br/2014/01/bitwise-escovar-bits.html.

O algoritmo que vou utilizar é similar ao método de multiplicação ensinado nas escolas. Ele é apresentado em detalhes nesse link http://www.exploringbinary.com/binary-multiplication/. Também sugiro realizar a leitura desse artigo antes de continuar…

Feita a introdução, o primeiro passo é implementar um método auxiliar que seja capaz de realizar adição dos bits. Basicamente, a adição de binários pode ser realizada com o operador xor ( em Java ^ ). Veja:

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0 ( e vai 1) == 10

Perceba que exceto pelo último caso de teste, 1 + 1 = 10, o operador xor devolve o resultado correto. Assim sendo, para realizar a adição é possível usar o operador xor e em seguida identificar se existe o caso de teste problemático( 1 + 1 = 10 ). Se existir, é necessário utilizar novamente o xor para adicionar o 1 do ‘vai 1’. Obviamente, essa segunda operação com o xor também pode ter o caso de teste problemático… Então, é necessário refazer o teste e repetir a operação até que isso não ocorra ( uma boa oportunidade para utilizar recursividade ).

Para identificar se existe o caso de teste 1 + 1 = 10 basta utilizar o operador and ( em Java & ) com os 2 números. Veja:

0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

Assim, se o resultado da operação and entre os 2 números for igual a zero, o caso de teste problemático não existe. Senão, o caso de teste problemático existe.

Veja uma implementação possível para o método somar:



public static int somar(int numero1, int numero2) {

if(numero2 == 0)
return numero1;

return somar( numero1 ^ numero2, (numero1 & numero2) << 1);
}

Observação: o << 1 coloca, se existir, o 1 na próxima posição a esquerda de onde ocorreu o caso de teste problemático. ( O 1 deve ser adicionado na próxima coluna da esquerda )

Com o método de adição pronto, já é possível iniciar a construção de um método para realizar a multiplicação. A multiplicação de bits pode ser realizada com o operador and, mas será necessário pegar o primeiro bit do número1 e realizar a operação and com cada um dos bits do número2 e em seguida pegar o segundo bit do número1 e realizar a operação and com cada um dos bits do número2 e assim por diante… ( Veja o link que explica o algoritmo de multiplicação )

Para pegar um bit especifico de uma variável é possível usar esse código:



int bitPosicao = ( numero & ( 0b1 << posicao ) ) >> posicao;

Nesse código, se o bit da posição escolhida for zero, bitPosicao recebe zero. Se o bit da posição escolhida for 1, bitPosicao recebe um valor diferente de zero.

Com isso, basta pegar os bits ( um do primeiro número e outro do segundo ), realizar a operação and, e armazenar o bit resultante em uma variável auxiliar de forma que ele ocupe a posição correta. Veja:



int numero1 = 0b1; //0000 0001 (apenas o primeiro byte)

int numero2 = 0b10; //0000 0010


int resultadoParcial = 0b0; //0000 0000


int posicaoBitNumero1 = 0;

int bitNumero1 = ( numero1 & ( 0b1 << posicaoBitNumero1 ) ) >> posicaoBitNumero1; // 0000 0001


int posicaoBitNumero2 = 0;

int bitNumero2 = ( numero2 & ( 0b1 << posicaoBitNumero2 ) ) >> posicaoBitNumero2; // 0000 0000

//guarda o primeiro teste na posição do bitNumero2
resultadoParcial = resultadoParcial | ( ( bitNumero1 & bitNumero2 ) << posicaoBitNumero2 ); // 0000 0000


posicaoBitNumero2 = 1; //para pegar o segundo bit do numero2

bitNumero2 = ( numero2 & ( 0b1 << posicaoBitNumero2 ) ) >> posicaoBitNumero2; // 0000 0001

//guarda o segundo teste na posição do bitNumero2
resultadoParcial = resultadoParcial | ( ( bitNumero1 & bitNumero2 ) << posicaoBitNumero2 ); // 0000 0010

Nesse exemplo, pego o primeiro bit da variável numero1 e realizo a operação and com esse bit e cada um dos bits da variável numero2. Após cada teste é usada a posição do bit da variável numero2 para armazenar o bit resultante na variável resultadoParcial. Veja que a operação or( em Java | ) entre a variável resultadoParcial e o bit resultante da operação and entre a variável numero1 e a variável numero2 não altera os bits que foram armazenados anteriormente.

Com esse exemplo, já é possível ter uma ideia dos passos necessários, mas esse processo deve ser repetido para todos os bits das variáveis numero1 e numero2. Para isso, é necessário saber qual a quantidade de bits dessas variáveis( a quantidade é igual para ambas, as duas são do tipo int ).

Em Java não existe um operador semelhante ao sizeof do C, mas a quantidade de bits de cada tipo pode ser previamente verificada. Veja esse link: https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html. Utilizando esse link é possível afirmar que o tipo int têm 32 bits.

Assim sendo, é possível criar um for para pegar todos os bits da variável numero1 e um segundo for, aninhado no primeiro, para pegar todos os bits da variável numero2. Veja:



public static int multiplicarBit(int numero1, int numero2) {

int resultadoFinal = 0b0;

for (int i = 0; i < 32; i++) {

int resultadoParcial = 0b0;

int bitNumero1 = (numero1 & (0b1 << i)) >> i;

for (int j = 0; j < 32; j++) {

int bitNumero2 = (numero2 & (0b1 << j)) >> j;

resultadoParcial = resultadoParcial | ((bitNumero1 & bitNumero2) << j);
}

resultadoFinal = somar(resultadoFinal, (resultadoParcial << i));
}

return resultadoFinal;
}

Observação: Assim, estão sendo calculados zeros que não têm significância( zeros à esquerda ). É possível usar alguns métodos específicos da classe Integer para evitar isso… Fica a dica 🙂

Para testar a eficiência desse método em comparação com o método de adições consecutivas criei o seguinte código :



package javaapplication1;

public class JavaApplication1 {

public static int multiplicarSimples(int numero1, int numero2) {

int resultado = 0;

for (int i = 0; i < numero1; i++) {
resultado += numero2;
}

return resultado;
}

public static int multiplicarBit(int numero1, int numero2) {

int resultadoFinal = 0b0;

for (int i = 0; i < 32; i++) {

int resultadoParcial = 0b0;

int bitNumero1 = (numero1 & (0b1 << i)) >> i;

for (int j = 0; j < 32; j++) {

int bitNumero2 = (numero2 & (0b1 << j)) >> j;

resultadoParcial = resultadoParcial | ((bitNumero1 & bitNumero2) << j);
}

resultadoFinal = somar(resultadoFinal, (resultadoParcial << i));
}

return resultadoFinal;
}

public static int somar(int numero1, int numero2) {

if (numero2 == 0) {
return numero1;
}

return somar(numero1 ^ numero2, (numero1 & numero2) << 1);
}

public static void main(String[] args) {

int numero1 = 732222;
int numero2 = 345;

long tempoInicial = System.currentTimeMillis();

int resultado = multiplicarSimples( numero1, numero2 );

long tempoFinal = System.currentTimeMillis();

System.out.println( "Resultado simples = " + resultado + " tempo = " + (tempoFinal - tempoInicial) );

tempoInicial = System.currentTimeMillis();

resultado = multiplicarBit( numero1, numero2 );

tempoFinal = System.currentTimeMillis();

System.out.println( "Resultado bitwise = " + resultado + " tempo = " + (tempoFinal - tempoInicial) );

}

}

Observação: Eu sei que existem formas melhores de comparar a eficiência desses códigos, mas, para esse exemplo, acredito que pegar a diferença de tempo é o suficiente.

Segue os testes realizados:



//teste 0
Numero1 = 732222
Numero2 = 345
Resultado simples = 252616590 tempo = 6
Resultado bitwise = 252616590 tempo = 0

//teste 1
Numero1 = 732222
Numero2 = 9
Resultado simples = 6589998 tempo = 5
Resultado bitwise = 6589998 tempo = 0

//teste 2
Numero1 = 86
Numero2 = 3
Resultado simples = 258 tempo = 0
Resultado bitwise = 258 tempo = 0

//teste 3 - o resultado foi maior que um int
Numero1 = 123456
Numero2 = 654321
Resultado simples = -824525248 tempo = 5
Resultado bitwise = -824525248 tempo = 0

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *