Algorithmus für binäre Arithmetik in Java

Question

Auf dem Papier ist die binäre Arithmetik einfach, aber als ein beginnender Programmierer finde ich es etwas schwierig, Algorithmen für die Addition, Subtraktion, Multiplikation und Division von Binärzahlen zu finden.

Ich habe zwei Binärzahlen als Strings gespeichert, vorausgesetzt, dass führende Nullen fallen gelassen wurden. Wie würde ich diese Operationen mit den beiden Zahlen durchführen?

Edit: Ich muss vermeiden, sie zu einem Int oder Long zu konvertieren.

Answer 1

Der folgende Code implementiert die binäre Addition, ohne dass irgendeine arithmetische, binäre oder andere Prozedur ausgeführt wird. Der eigentliche "Zusatz" wird von lookupTable erledigt, und alles andere ist eine direkte String-Manipulation. Ich habe es mit der Absicht geschrieben, es so lehrreich wie möglich zu machen und den Prozess statt der Effizienz zu betonen. Ich hoffe es hilft.

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")); 
    } 
} 

---

Während wir gerade dabei sind, könnte ich auch multiply tun.

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; 
} 

Answer 2

Binärkette int:

int i = Integer.parseInt("10101011", 2); 
int j = Integer.parseInt("00010", 2); 

Dann können Sie tun, was Sie mit den beiden Ints bitte, zB:

i = i + j; 
i = i - j; 

Und sie in eine binäre Zeichenfolge zurück:

String s = Integer.toBinaryString(i); 

Answer 3

Konvertieren Sie die binären Zeichenfolgen in Ganzzahlen und arbeiten Sie dann mit den Ganzzahlen, z

String add(String s1, String s2) { 
    int i1 = Integer.parseInt(s1); 
    int i2 = Integer.parseInt(s2); 
    return Integer.toBinaryString(i1 + i2); 
} 

Answer 4

Die Algorithmen, von wikipedia:

Zusatz:

Die einfachste Rechenoperation in binär ist zusätzlich. Hinzufügen von zwei einem einstelligen Binärzahlen ist relativ einfach, eine Form von Buch mit:

0 + 0 → 0 
0 + 1 → 1 
1 + 0 → 1 
1 + 1 → 0, carry 1 (since 1 + 1 = 0 + 1 × 10 in binary) 

Hinzufügen von zwei „1“ Ziffern erzeugt eine Ziffer „0“ ist, während 1 muss hinzugefügt werden, um die nächste Spalte.

Subtraction:

Subtraction arbeitet in der gleichen Weise:

0 − 0 → 0 
0 − 1 → 1, borrow 1 
1 − 0 → 1 
1 − 1 → 0 

eine "1" Ziffer von einer "0" Ziffer Subtrahierend erzeugt die Ziffer „1 ", während 1 von der nächsten Spalte abgezogen werden muss. Dies ist bekannt als Ausleihe. Das Prinzip ist das gleiche wie zum Tragen. Wenn das Ergebnis einer Subtraktion kleiner als 0 ist, der kleinste mögliche Wert einer Ziffer, ist die Prozedur, das Defizit dividiert durch die Radix (das heißt 10/10) von links, Subtrahieren es aus dem nächsten Positionswert.

Multiplication:

Multiplikation in binärer ähnelt dezimalen Gegenstück. Zwei Zahlen A und B können durch partielle Produkte multipliziert werden: für jede Ziffer in B, das Produkt dieser Ziffer in A wird berechnet und in einer neuen Zeile geschrieben, verschoben nach links, so daß seine äußersten rechten digit Linien mit die Ziffer in B , die verwendet wurde. Die Summe aller dieser Teilprodukte ergibt das endgültige Ergebnis.

Da es nur zwei Stellen in binär, gibt es nur zwei mögliche Ergebnisse jeder Teil Multiplikation:

* 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 A 

Zum Beispiel sind die Binärzahlen 1011 und 1010 multipliziert werden, wie folgt:

 

      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 

Answer 5

Der eingebaute in BitSet Klasse ist sehr geradlinig uns e für Bit-Level-Operationen.

Answer 6

mit binärer Arithmetik zu arbeiten, ist wirklich nicht anders als die bekannteren Basis 10 sind zusätzlich zum Beispiel nehmen lassen

    (1)  (1) 
182  182  182  182  182 
845  845  845  845  845 
--- + --- + --- + --- + --- + 
      7  27  027  1027 

Also, was hast du getan? Richten Sie die hinzuzufügenden Zahlen rechtsbündig aus, und fahren Sie von rechts nach links fort, indem Sie eine Ziffer nach der anderen hinzufügen und dabei je nach Bedarf +1 nach links tragen.

Im Binärformat ist der Prozess genau gleich. In der Tat ist es noch einfacher, weil Sie jetzt nur 2 "Ziffern" haben, 0 und 1!

   (1)       (1)  (1) 
11101  11101  11101  11101  11101  11101  11101 
1001  1001  1001  1001  1001  1001  1001 
----- + ----- + ----- + ----- + ----- + ----- + ----- + 
       0   10  110  0110  00110  100110 

Der Rest der Operationen funktionieren ähnlich zu: der gleiche Prozess, den Sie für die Basis 10 verwendet wird, arbeitet für die Basis 2. Und wieder, es ist tatsächlich einfacher, weil es nur 2 „Ziffern“ sind, 0 und 1. Diese Einfachheit ist der Grund, warum Hardware das binäre System mag.