Selten, aber dennoch sind Aufgaben aus Interviews und Schulungen von praktischem Wert. Daher musste ich in Java eine Alternative zu arithmetischen Operationen für ganzzahlige Werte implementieren. Glücklicherweise sind die ersten Seiten von Suchmaschinen voll von vorgefertigten Lösungen für bitweise Analoga, und Sie mussten sich über die meisten nicht den Kopf brechen.
Ehrlich gesagt war ich etwas überrascht über den Mangel an solchem Material auf Habré (sah ich schlecht aus?) Und beschloss daher, dieses Manko mit meinen Kommentaren und Ergänzungen zu füllen.
Bitte beachten Sie, dass in den Beispielen mit bitweisen Operationen die Werte auf ein Halbbyte gekürzt werden: Es gibt keinen grundlegenden Unterschied, aber es ist einfacher zu verstehen.
Zusatz
Algorithmus:
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
Zunächst müssen Sie sich an die Übertragung in die Seniorenkategorie erinnern. Im Dezimalsystem enthält seine Definition (für die aktuelle Ziffer) Werte im Bereich von 10 bis 18:
109 +
019 =
128
Im binären System wird alles übertragen, was größer als eins ist:
0001 +
0001 =
----
0010
oder so:
0011 +
0011 =
----
0110
Im letzten Beispiel werden zuerst die niedrigstwertigen Bits hinzugefügt:
1 + 1 = 10 ()
Null bleibt im aktuellen Bit, und dasjenige geht zum höchstwertigen, wo es zusätzlich teilnimmt:
1 + 1 + 1 = 11 ()
der niedrigste bleibt im aktuellen, der ältere bewegt sich weiter. Hier können Sie die Regel ableiten, dass im Binärsystem für ein aktuelles Bit Werte von zwei bis einschließlich drei unter den Übertrag fallen.
In dem Teil, der den Algorithmus betrifft, lohnt es sich, die Anweisung zum Bestimmen des Vorhandenseins / Nichtvorhandenseins einer Übertragung am Beispiel vorheriger Werte zu beachten:
carry = (summand & addend);
0011 = 0011 & 0011
Dies ist noch keine Übertragung, sondern das Setzen von "Flags" über den Ziffern, deren Addition die Übertragung verlässt, d.h. Add Carry ist, wenn die Bits gleich sind.
Sobald bereits etwas klar geworden ist, sollte nun der erste Term von den Bits befreit werden, für die die Übertragung berücksichtigt wird:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Wie Sie wissen, setzt der bitweise XOR-Operator nur dann Bits, wenn die Bitwerte entgegengesetzt sind.
Der dritte Schritt in der Schleife besteht darin, die Übertragsflags direkt in einen Übertrag umzuwandeln. Dazu werden sie einen Schritt nach links verschoben und dem zweiten Term zugeordnet:
addend = (carry << 1);
0110 = (0011 << 1);
Bei der nächsten Iteration wird die Übertragung nicht behoben, weil:
carry = (summand & addend);
0000 = 0000 & 0110
Der zweite Schritt wird uns geben:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Welches ist die gewünschte Summe, und der dritte Schritt beendet die while () - Schleife:
addend = (carry << 1);
0000 = (0000 << 1)
Subtraktion
Algorithmus:
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
Entspricht dem vorherigen, mit dem einzigen Unterschied, dass das Ausleihen von Bits von den höchstwertigen Bits eine inverse Implikationsinversion implementiert ist . Nun, wir benennen die lokalen Variablen um.
Multiplikation
Algorithmus:
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;
}
Zurück zu den Grundlagen: lange Multiplikation im Dezimalsystem:
25 *
05 =
--
125 +
00
---
125
jene. Wir multiplizieren jede Ziffer des zweiten Faktors mit dem ersten Faktor. Daraus folgt, dass das Produkt vom höchstwertigen Bit einen Schritt nach links verschoben wird. Fügen Sie abschließend die Zwischenwerte hinzu. Das gleiche passiert auf bitweiser Ebene:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Wir schließen daraus, dass der Algorithmus nur muss, dass das Hinzufügen des ersten Faktors zu sich selbst, wenn ein gesetztes Bit im zweiten Faktor angetroffen wird, natürlich unter Berücksichtigung der Regel für die Übertragung auf das höchstwertige Bit:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Dann wird der erste Multiplikator ein Bit nach links verschoben (wir bilden eine "Leiter"):
mul1 <<= 1; //1100 = 0110 << 1;
Nun bestimmen wir, ob das zweitwichtigste Bit des zweiten Faktors ein Bit enthält:
mul2 >>>= 1; //0001 = 0011 >>> 1;
Der Zyklus läuft, bis der zweite Faktor Null ist. Ich möchte Ihre Aufmerksamkeit auf Folgendes lenken: Eine Instanz dieses Algorithmus geht von Ressource zu Ressource, wobei die logische Verschiebung des zweiten Faktors (mul2 >>> = 1) durch einen arithmetischen Faktor (mul2 >> = 1) ersetzt wird . Es stammt wahrscheinlich aus der Implementierung in C / C ++, wo das Schlüsselwort ohne Vorzeichen vorhanden ist und eine solche Ersetzung kein Problem darstellt. In Java sind jedoch alle Arten von Zahlen signiert, und wenn der zweite Faktor durch einen negativen Wert dargestellt wird, führt ein solches Versehen dazu, dass der Algorithmus in eine Endlosschleife fällt, da Der zweite Faktor wird immer seine Bedingung erfüllen:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
Einteilung
Algorithmus:
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);
}
Die Aufteilung verlief nicht so reibungslos wie bei den vorherigen Beispielen: Ich musste ein Fahrrad schreiben (nicht hart getroffen).
Division ist die Subtraktion des Divisors von der Dividende, solange der Quotient größer oder gleich Null ist. Bei diesem Ansatz ist es ausreichend, einen Zähler zu definieren, dessen Wert nach jeder Subtraktionsoperation erhöht wird. Sein Endwert ist das Besondere:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
Der Nachteil dieses Ansatzes macht sich insbesondere dann bemerkbar, wenn ein Gerät mit begrenzten Ressourcen für die Reihenfolge von Anweisungen versorgt wird, wie z. B .: 2147483647/1; 2147483647/2; 2147483647/3 sieht es so aus, als ob die Anwendung eingefroren ist.
Arbeiten auf Bitebene wäre viel effizienter. Die einzige gefundene Lösung hat jedoch den Nachteil, dass für eine korrekte Folgerung die Art der Variablen erforderlich ist, einen Schritt über dem abgedeckten Bereich, d. H. Wenn die Eingabe kurz ist , muss der Typ der lokalen Variablen int sein , andernfalls ist das Ergebnis der Division großer Werte überraschend. In meinem Fall wurde die Situation durch das Fehlen des langen Typs verschärft.
Aber zurück zu unseren Widdern.
Um das Prinzip des Algorithmus zu verstehen, müssen Sie sich die Reihenfolge der Division durch eine Spalte merken:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Hier ausführlicher. Am Auspuff haben wir folgendes erreicht: Wir haben den Teiler nach links bis zur Entladung "geschoben", wo er den Unterschied zum Teilbaren minimierte:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
Dieser Mechanismus ist im Algorithmus implementiert. In einer while () - Schleife muss der Divisor nach links verschoben werden, bis er die obige Regel erfüllt. Parallel dazu wird die private Maske verschoben. Der Verzweigungsoperator if () sagt: "Sie können verschieben, wenn nur das Ergebnis dieser Operation nicht gegen die Grundregel verstößt." Eine zusätzliche Überprüfung auf eine negative Zahl ist darauf zurückzuführen, dass das höchstwertige in Java gesetzte Bit eine negative Zahl ist. Ohne sie wird der Zyklus ins Unendliche fallen:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
Sobald der Algorithmus die if () - Bedingungen nicht mehr erfüllt, gibt der Code das else ein, in dem das Maskenbit für den Quotienten gesetzt ist:
quotient = quotient | mask;
0010 = 0000 | 0010
Dies entspricht dem Setzen der Bits für eine lange Division. Dann wird der Divisor von der Dividende abgezogen:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
Danach kehren der Teiler und die Maske in ihren ursprünglichen Zustand zurück und der Zyklus beginnt erneut:
divisor = temp;
mask = 0x01;
Abschließend möchte ich noch ein paar Worte zu zusätzlichem Code hinzufügen.
Der obige Algorithmus geht davon aus, dass nur positive Zahlen geteilt werden, die durch den komplementären Code erhalten werden:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Hier passiert Folgendes: Wenn die Zahl negativ ist, werden ihre Bits invertiert, und das Ergebnis wird mit eins addiert, und wir erhalten einen positiven (absoluten) Wert. Die gleiche Regel gilt für positive Zahlen, zum Beispiel:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Es gibt jedoch eine Ausnahme: Dies ist die größte negative Zahl eines bestimmten Typs, zum Beispiel:
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.
Seid vorsichtig.