Multiplicação Egípcia

Desde da antiguidade, os egípcios conheciam o poder do sistema binário que hoje é o coração do nosso mundo tecnológico. No Egito Antigo, eles desenvolveram um método curioso de multiplicação baseado no sistema binária.

Imagine que você queira calcular 21 x 43. Na primeira linha, você coloca

 A próxima linha é obtida a partir da anterior multiplicando por 2. Assim por diante,

Observe que a operação de duplicar é bastante simples. Logo depois, precisamos descobrir quais são as linhas que somadas a primeira coluna dá 43.

1 + 2 + 8 + 32 = 43

Somando a segunda coluna dessa linhas obtemos o valor de 21 x 43.

Podemos escrever o seguinte programa para multiplicar dois números:

int multiplica(int a, int b){
  int resultado = 0;
  while(b!=0){
   if(b%2==1){
    resultado += a;
   }
   b = b/2;
   a = a*2;
  }  
  return resultado;
}

Neste algoritmo, os valores de a (segunda coluna) são somados em resultado na posição dos bits ligados (primeira coluna) da representação binária de b.

Esse algoritmo pode ser reescrito utilizando operações bit-a-bit da seguinte maneira:

int multiplica2(int a, int b){
  int resultado = 0;
  while(b!=0){
   if(b & 1 ==1){
    resultado += a;
   }
   b = b >> 1; //deslocamento de 1 bit  para direita
   a = a << 1; //deslocamento de 1 bit  para a esquerda
  }  
  return resultado;
}

A operação de deslocamento para a direita equivale a dividir por 2 e deslocamento para esquerda equivale a multiplicar por 2.

5 =  101

5 >> 1 = 10 = 2

5 >> 1 = 1010 = 10

O mesmo acontece na base 10, para multiplicar por 10 basta adicionar um zero no final e dividir por 10 basta apagar o último dígito.

Fonte: 

http://professoraju-mat.blogspot.com.br/2010/07/jura-multiplicacao-egipcia.html