Rara vez, pero aún así, las tareas de entrevistas y capacitaciones son de valor práctico. Entonces, necesitaba implementar en Java una alternativa a las operaciones aritméticas en valores enteros. Afortunadamente, las primeras páginas de los motores de búsqueda están llenas de soluciones listas para usar para análogos bit a bit, y no tuvo que romperse la cabeza con la mayoría de ellas.
Francamente, me sorprendió un poco la falta de dicho material en Habré (¿me veía mal?), Y por eso decidí llenar este defecto con mis comentarios y adiciones.
Tenga en cuenta que en los ejemplos con operaciones bit a bit, los valores se truncan en un nibble: no habrá diferencia fundamental, pero es más fácil de entender.
Adición
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;
}
Primero debe recordar acerca de la transferencia a la categoría senior. En el sistema decimal, su definición (para el dígito actual) incluye valores en el rango de 10 a 18:
109 +
019 =
128
En el sistema binario, todo lo que sea mayor que uno se transfiere:
0001 +
0001 =
----
0010
o así:
0011 +
0011 =
----
0110
En el último ejemplo, los bits menos significativos se agregan primero:
1 + 1 = 10 ()
El cero queda en el bit actual, y uno pasa al más significativo, donde participa además:
1 + 1 + 1 = 11 ()
el más bajo permanece en el actual, el más antiguo avanza. A partir de aquí, puede deducir la regla de que en el sistema binario para un bit actual, los valores de dos a tres, inclusive, caen bajo el acarreo.
En la parte relativa al algoritmo, vale la pena prestar atención a la instrucción para determinar la presencia / ausencia de transferencia utilizando el ejemplo de valores anteriores:
carry = (summand & addend);
0011 = 0011 & 0011
Esta no es una transferencia todavía, sino la configuración de "banderas" sobre los dígitos, cuya adición deja la transferencia, es decir add carry es cuando los bits son iguales.
Tan pronto como algo ya se haya aclarado, ahora el primer término debe liberarse de los bits para los que se tiene en cuenta la transferencia:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Como sabe, el operador XOR bit a bit establecerá bits solo si los valores de bit son opuestos.
El tercer paso en el ciclo es convertir las banderas de acarreo directamente en un acarreo. Para hacer esto, se desplazan un paso hacia la izquierda y se asignan al segundo término:
addend = (carry << 1);
0110 = (0011 << 1);
En la siguiente iteración, la transferencia no se solucionará porque:
carry = (summand & addend);
0000 = 0000 & 0110
El segundo paso nos dará:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Cuál es la suma deseada, y el tercer paso finalizará el ciclo while ():
addend = (carry << 1);
0000 = (0000 << 1)
Sustracción
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 al anterior, con la única diferencia de que el préstamo de bits de los bits más significativos se implementa con inversión de implicación inversa . Bueno, cambiamos el nombre de las variables locales.
Multiplicación
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 vuelta a lo básico: multiplicación larga en sistema decimal:
25 *
05 =
--
125 +
00
---
125
aquellos. multiplicamos cada dígito del segundo factor por el primer factor. De aquí se deduce que el producto del bit más significativo se desplaza un paso hacia la izquierda. Finalmente, agregue los valores intermedios. Lo mismo sucede a nivel bit a bit:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Concluimos que el algoritmo solo tiene que agregar el primer factor a sí mismo cada vez que se encuentra un bit establecido en el segundo factor, naturalmente, teniendo en cuenta la regla de transferir al bit más significativo:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Luego, el primer multiplicador se desplaza un bit hacia la izquierda (formamos una "escalera"):
mul1 <<= 1; //1100 = 0110 << 1;
Ahora determinamos si hay un bit en el segundo bit más importante del segundo factor:
mul2 >>>= 1; //0001 = 0011 >>> 1;
El ciclo se ejecuta hasta que el segundo factor es cero. Me gustaría llamar su atención sobre lo siguiente: una instancia de este algoritmo camina de un recurso a otro, donde el cambio lógico del segundo factor (mul2 >>> = 1) es reemplazado por uno aritmético (mul2 >> = 1) . Probablemente se origina en la implementación en C / C ++, donde existe la palabra clave unsigned y tal sustitución no es un problema. Sin embargo, en Java todos los tipos de números están firmados, y si el segundo factor está representado por un valor negativo, tal descuido conducirá a que el algoritmo caiga en un ciclo infinito, ya el segundo factor siempre cumplirá su condición:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
División
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);
}
La división no funcionó tan bien como en los ejemplos anteriores: tuve que escribir una bicicleta (no pegar fuerte).
La división es la resta del divisor del dividendo siempre que el cociente sea mayor o igual a cero. Con este enfoque, es suficiente definir un contador, cuyo valor se incrementa después de cada operación de resta. Su valor final es el particular:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
La desventaja de este enfoque se vuelve especialmente notable cuando se suministra un dispositivo con recursos limitados de secuencia de instrucciones, como: 2147483647/1; 2147483647/2; 2147483647/3 , parece que la aplicación está congelada.
El trabajo a nivel de bits sería mucho más eficiente. Pero la única solución encontrada tiene la desventaja de que para una inferencia correcta, se requiere el tipo de variables, un paso por encima del rango cubierto, es decir si la entrada es corta , entonces el tipo de variables locales debe ser int ; de lo contrario, el resultado de dividir valores grandes será sorprendente. En mi caso, la situación se vio agravada por la ausencia del tipo largo.
Pero volvamos a nuestros carneros.
Para comprender cómo funciona el algoritmo, debe recordar el orden de división de las columnas:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Aquí con más detalle. En el escape, obtuvimos lo siguiente: "empujamos" el divisor hacia la izquierda hasta la descarga donde minimizó la diferencia con el divisible:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
Este mecanismo está implementado en el algoritmo. En un ciclo while (), el divisor debe desplazarse hacia la izquierda hasta que satisfaga la regla anterior. Paralelamente, se cambia la máscara privada. El operador de bifurcación if () dice: "Puede cambiar si solo el resultado de esta operación no infringe la regla básica". Una verificación adicional para un número negativo se debe al hecho de que en Java, el conjunto de bits más significativo es un número negativo. Sin él, el ciclo caerá al infinito:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
Tan pronto como el algoritmo deja de cumplir las condiciones if (), el código ingresa el else, donde el bit de máscara se establece en el cociente:
quotient = quotient | mask;
0010 = 0000 | 0010
Esto es lo mismo que configurar los bits para una división larga. Luego, el divisor se resta del dividendo:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
Después de eso, el divisor y la máscara vuelven a su estado original y el ciclo comienza de nuevo:
divisor = temp;
mask = 0x01;
Finalmente, me gustaría agregar algunas palabras sobre código adicional.
El algoritmo anterior asume la división solo de números positivos que se obtienen mediante el código complementario:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Aquí ocurre lo siguiente: si el número es negativo, entonces sus bits se invierten, y al resultado se le suma uno y obtenemos un valor positivo (absoluto). La misma regla se aplica a los números positivos, por ejemplo:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Pero hay una excepción: este es el número negativo más grande de un tipo determinado, por ejemplo:
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.
Ten cuidado.