En papel, la aritmética binaria es simple, pero como programador principiante, me resulta un poco difícil encontrar algoritmos para sumar, restar, multiplicar y dividir números binarios.Algoritmo para la aritmética binaria en Java
Tengo dos números binarios almacenados como cadenas, suponga que se han eliminado los ceros a la izquierda. ¿Cómo voy a realizar estas operaciones en los dos números?
Editar: Necesito evitar convertirlos a int o long.
El siguiente código implementa la adición binaria sin realizar ninguna operación aritmética, binaria o de otro tipo. La "adición" real se realiza por lookupTable, y todo lo demás es manipulación directa de cadena. Lo escribí con la intención de hacerlo lo más instructivo posible, enfatizando el proceso en lugar de la eficiencia. Espero eso ayude.
public class BinaryArithmetic {
static String[] lookupTable = {
"0+0+0=00",
"0+0+1=01",
"0+1+0=01",
"0+1+1=10",
"1+0+0=01",
"1+0+1=10",
"1+1+0=10",
"1+1+1=11",
};
static String lookup(char b1, char b2, char c) {
String formula = String.format("%c+%c+%c=", b1, b2, c);
for (String s : lookupTable) {
if (s.startsWith(formula)) {
return s.substring(s.indexOf("=") + 1);
}
}
throw new IllegalArgumentException();
}
static String zeroPad(String s, int length) {
while (s.length() < length) {
s = "0" + s;
}
return s;
}
static String add(String s1, String s2) {
int length = Math.max(s1.length(), s2.length());
s1 = zeroPad(s1, length);
s2 = zeroPad(s2, length);
String result = "";
char carry = '0';
for (int i = length - 1; i >= 0; i--) {
String columnResult = lookup(s1.charAt(i), s2.charAt(i), carry);
result = columnResult.charAt(1) + result;
carry = columnResult.charAt(0);
}
if (carry == '1') {
result = carry + result;
}
return result;
}
public static void main(String args[]) {
System.out.println(add("11101", "1001"));
}
}
Mientras estamos en ello, que también podría hacer multiply también.
static String multiply(String s1, String s2) {
String result = "";
String zeroSuffix = "";
for (int i = s2.length() - 1; i >= 0; i--) {
if (s2.charAt(i) == '1') {
result = add(result, s1 + zeroSuffix);
}
zeroSuffix += "0";
}
return result;
}
cadena binaria a int:
int i = Integer.parseInt("10101011", 2);
int j = Integer.parseInt("00010", 2);
A continuación, puede hacer lo que quieras con los dos enteros, por ejemplo:
i = i + j;
i = i - j;
Y para que vuelvan a una cadena binaria:
String s = Integer.toBinaryString(i);
Lo siento, debería haber notado que debo evitar convertirlos a int o long. –
Convierta las cadenas binarias en enteros y luego opere en los enteros, por ejemplo
String add(String s1, String s2) {
int i1 = Integer.parseInt(s1);
int i2 = Integer.parseInt(s2);
return Integer.toBinaryString(i1 + i2);
}
Los algoritmos, de Wikipedia:
de adición:
la operación aritmética simple en binario es adición. Adición de dos números binarios de un solo dígito es relativamente simple, utilizando una forma de en libros:
0 + 0 → 0 0 + 1 → 1 1 + 0 → 1 1 + 1 → 0, carry 1 (since 1 + 1 = 0 + 1 × 10 in binary)Adición de dos "1" dígitos produce un dígito "0", mientras que 1 tendrá que ser añadido a la próxima columna
Resta:
substracción funciona de la misma manera:
0 − 0 → 0 0 − 1 → 1, borrow 1 1 − 0 → 1 1 − 1 → 0Restar un "1" dígitos de un "0" dígitos produce el dígito "1 ", mientras que 1 tendrá que restarse de la siguiente columna . Esto se conoce como préstamo. El principio es el mismo en cuanto a llevar. Cuando el resultado de una resta es menor que 0, el menor valor posible de de un dígito, el procedimiento consiste en "tomar prestado" el déficit dividido por el radix (es decir, 10/10) desde la izquierda, restando desde el siguiente valor posicional .
Multiplicación:
multiplicación en binario es similar a su contraparte decimal. Dos números A y B pueden ser multiplicados por parciales productos: de cada dígito en B, el producto de ese dígito en A se calculan y se escriben en una nueva línea, desplazado hacia la izquierda de modo que su extremo derecho líneas dígito hasta con el dígito en B que se utilizó. La suma de todos estos productos parciales da el resultado final .
Puesto que hay sólo dos dígitos en binario, sólo hay dos posibles resultados de cada multiplicación parcial:
* If the digit in B is 0, the partial product is also 0 * If the digit in B is 1, the partial product is equal to APor ejemplo, los números binarios 1011 y 1010 se multiplican como sigue:
1 0 1 1 (A)
× 1 0 1 0 (B)
---------
0 0 0 0 ← Corresponds to a zero in B
+ 1 0 1 1 ← Corresponds to a one in B
+ 0 0 0 0
+ 1 0 1 1
---------------
= 1 1 0 1 1 1 0
El built-in BitSet clase es muy recta hacia adelante para nosotros e para operaciones a nivel de bit.
Trabajar con aritmética binaria es realmente diferente de la base más familiar 10. Tomemos, por ejemplo, además
(1) (1)
182 182 182 182 182
845 845 845 845 845
--- + --- + --- + --- + --- +
7 27 027 1027
Entonces, ¿qué hizo usted? Alinea los números para agregarlos, y avanza de derecha a izquierda, agregando un dígito a la vez, llevando +1 a la izquierda según sea necesario.
En binario, el proceso es exactamente el mismo. ¡De hecho, es incluso más simple porque ahora solo tienes 2 "dígitos", 0 y 1!
(1) (1) (1)
11101 11101 11101 11101 11101 11101 11101
1001 1001 1001 1001 1001 1001 1001
----- + ----- + ----- + ----- + ----- + ----- + ----- +
0 10 110 0110 00110 100110
El resto de las operaciones funcionan de manera similar también: el mismo proceso que se utiliza para la base 10, trabaja para la base 2. Y de nuevo, en realidad es más simple porque sólo hay 2 "dígitos", 0 y 1. Esta simplicidad es la razón por la cual al hardware le gusta el sistema binario.
¿Desea obtener información sobre cómo implementar el algoritmo real o simplemente realizar operaciones aritméticas con estas cadenas? – Daff
http://stackoverflow.com/questions/1218149/arbitrary-precision-arithmetic-explanation – paxdiablo
Daff, me gustaría aprender cómo implementar el algoritmo. –