Bitwise: Multiplicando números inteiros

2 de abr de 2016 - Paulo Dias


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


Paulo Dias

Graduado no curso tecnólogo em análise e desenvolvimento de sistemas. Defensor do Software Livre e da democratização da informação. Possui as certificações Linux LPIC-1 e Java OCA. Atualmente exerce a função de coordenador técnico na área de telecomunicações.

Siga-me no Twitter