Raramente, mas ainda assim, as tarefas de entrevistas e treinamentos têm valor prático. Portanto, eu precisava implementar em Java uma alternativa às operações aritméticas em valores inteiros. Felizmente, as primeiras páginas dos motores de busca estão cheias de soluções prontas para análogos bit a bit, e você não precisava quebrar a cabeça com a maioria delas.
Francamente, fiquei um tanto surpreso com a falta de tal material sobre Habré (eu estava mal?), E, portanto, decidi preencher essa lacuna, com meus comentários e acréscimos.
Observe que nos exemplos com operações bit a bit, os valores são truncados para um nibble: não haverá nenhuma diferença fundamental, mas mais fácil de entender.
Adição
Algoritmo:
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
Primeiro, você precisa se lembrar da transferência para a categoria sênior. No sistema decimal, sua definição (para o dígito atual) inclui valores na faixa de 10 a 18:
109 +
019 =
128
No sistema binário, tudo o que é maior do que um é transferido:
0001 +
0001 =
----
0010
ou assim:
0011 +
0011 =
----
0110
No último exemplo, os bits menos significativos são adicionados primeiro:
1 + 1 = 10 ()
O zero fica no bit atual, e o um vai para o mais significativo, onde participa adicionalmente:
1 + 1 + 1 = 11 ()
o mais baixo permanece no atual, o mais velho avança. A partir daqui, você pode deduzir a regra de que, no sistema binário para um bit atual, os valores de dois a três, inclusive, se enquadram no transporte.
Na parte referente ao algoritmo, vale atentar para a instrução de determinação da presença / ausência de transferência a partir do exemplo dos valores anteriores:
carry = (summand & addend);
0011 = 0011 & 0011
Isso ainda não é uma transferência, mas a configuração de "sinalizadores" sobre os dígitos, cuja adição deixa a transferência, ou seja, add carry é quando os bits são iguais.
Assim que algo já tenha sido esclarecido, agora o primeiro termo deve ser liberado dos bits para os quais a transferência é levada em consideração:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Como você sabe, o operador XOR bit a bit definirá bits apenas se os valores dos bits forem opostos.
A terceira etapa do loop é converter os sinalizadores de transporte diretamente em um transporte. Para fazer isso, eles são deslocados uma etapa para a esquerda e atribuídos ao segundo termo:
addend = (carry << 1);
0110 = (0011 << 1);
Na próxima iteração, a transferência não será corrigida, porque:
carry = (summand & addend);
0000 = 0000 & 0110
A segunda etapa nos dará:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Qual é a soma desejada, e a terceira etapa encerrará o loop while ():
addend = (carry << 1);
0000 = (0000 << 1)
Subtração
Algoritmo:
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
Equivalente ao anterior, com a única diferença de que o empréstimo de bits dos bits mais significativos é implementado inversão de implicação inversa . Bem, renomeamos as variáveis locais.
Multiplicação
Algoritmo:
public int multiply(int mul1, int mul2)
{
int result = 0;
/* .*/
while(mul2 != 0)
{
/* ...*/
if ((mul2 & 1) == 1)
{
/* .*/
result = add(result, mul1);
}
/* ("")*/
mul1 <<= 1;
/* if()*/
mul2 >>>= 1;
}
return result;
}
De volta ao básico: multiplicação longa no sistema decimal:
25 *
05 =
--
125 +
00
---
125
Essa. multiplicamos cada dígito do segundo fator pelo primeiro fator. A partir daqui, segue-se que o produto do bit mais significativo é deslocado um passo para a esquerda. Finalmente, adicione os valores intermediários. A mesma coisa acontece no nível bit a bit:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Concluímos que o algoritmo só tem que adicionar o primeiro fator a si mesmo sempre que um bit definido for encontrado no segundo fator, naturalmente, levando em consideração a regra de transferência para o bit mais significativo:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Em seguida, o primeiro multiplicador é deslocado um bit para a esquerda (formamos uma "escada"):
mul1 <<= 1; //1100 = 0110 << 1;
Agora determinamos se há um bit no segundo bit mais importante do segundo fator:
mul2 >>>= 1; //0001 = 0011 >>> 1;
O ciclo continua até que o segundo fator seja zero. Gostaria de chamar sua atenção para o seguinte: uma instância desse algoritmo caminha de recurso para recurso, onde a mudança lógica do segundo fator (mul2 >>> = 1) é substituída por uma aritmética (mul2 >> = 1) . Provavelmente se origina da implementação em C / C ++, onde existe a palavra - chave unsigned e tal substituição não é um problema. No entanto, em Java todos os tipos de números são assinados, e se o segundo fator for representado por um valor negativo, tal descuido levará o algoritmo a cair em um loop infinito, uma vez que o segundo fator sempre atenderá sua condição:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
Divisão
Algoritmo:
private int divide(int dividend, int divisor)
{
/*, .*/
int quotient = 0x00, mask = 0x01;
/* .*/
int temp = divisor;
/* .*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/* .*/
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
/* 0 .*/
if (dividend < divisor) return quotient;
while(dividend > 0 || divisor != 0)
{
/* .*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/* .*/
else
{
/* "" .*/
quotient = quotient | mask;
/* .*/
dividend = sub(dividend, divisor);
/* .*/
divisor = temp;
mask = 0x01;
}
}
return multiply(quotient, sign);
}
A divisão não funcionou tão bem como nos exemplos anteriores: eu tive que escrever uma bicicleta (não bater forte).
Divisão é a subtração do divisor do dividendo, desde que o quociente seja maior ou igual a zero. Com esta abordagem, é suficiente definir um contador cujo valor é incrementado após cada operação de subtração. Seu valor final é o particular:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
A desvantagem desta abordagem torna-se especialmente perceptível ao fornecer um dispositivo com recursos limitados de uma sequência de instruções, como: 2147483647/1; 2147483647/2; 2147483647/3 , parece que o aplicativo está congelado.
O trabalho no nível de bits seria muito mais eficiente. Mas a única solução encontrada tem a desvantagem de que, para inferência correta, o tipo de variável é necessário, um passo acima da faixa coberta, ou seja, se a entrada for curta , o tipo de variáveis locais deve ser int , caso contrário, o resultado da divisão de grandes valores será surpreendente. No meu caso, a situação foi agravada pela ausência do tipo longo.
Mas voltando aos nossos carneiros.
Para entender como o algoritmo funciona, você precisa se lembrar da ordem de divisão das colunas:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Aqui com mais detalhes. No escapamento, obtivemos o seguinte: "empurramos" o divisor para a esquerda até a descarga onde minimizamos a diferença com o divisível:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
Este mecanismo é implementado no algoritmo. Em um loop while (), o divisor deve ser deslocado para a esquerda até que satisfaça a regra acima. Paralelamente, a máscara privada é deslocada. O operador de ramificação if () diz: "Você pode mudar se apenas o resultado desta operação não violar a regra básica." Uma verificação adicional de um número negativo é devido ao fato de que em Java, o conjunto de bits mais significativo é um número negativo. Sem ele, o ciclo cairá para o infinito:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
Assim que o algoritmo deixa de atender às condições if (), o código insere o else, onde o bit de máscara é definido no quociente:
quotient = quotient | mask;
0010 = 0000 | 0010
Isso é o mesmo que definir os bits para divisão longa. Em seguida, o divisor é subtraído do dividendo:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
Depois disso, o divisor e a máscara voltam ao seu estado original e o ciclo começa novamente:
divisor = temp;
mask = 0x01;
Finalmente, gostaria de acrescentar algumas palavras sobre código adicional.
O algoritmo acima assume a divisão apenas de números positivos que são obtidos pelo código complementar:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Aqui acontece o seguinte: se o número for negativo, então seus bits são invertidos e o resultado é adicionado a um e obtemos um valor positivo (absoluto). A mesma regra se aplica a números positivos, por exemplo:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Mas há uma exceção - este é o maior número negativo de um determinado tipo, por exemplo:
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
Seja cuidadoso.