Wussten Sie, dass eine kleine Anzahl Bits von einer größeren Anzahl ausleihen kann ? Hier ist ein Beispiel. Sagen wir unsere beiden Zahlen 5 und 14. Schreiben Sie sie zunächst binär auf:
5 14
000101 001110
Zunächst nehmen wir die kleinste auf etwas weg von der größeren Zahl, und wir geben es auf den kleinsten aus Bit auf der anderen Nummer. So
This bit turns off
|
v
000101 001110
^
|
This bit turns on
Jetzt haben wir
000111 001100
und unsere Zahlen sind 7 und 12. Die erste Zahl ist immer noch kleiner, also fahren wir fort.
000111 001100
001111 001000
Jetzt haben wir 15 und 8, damit wir aufhören können. Wir werden diese Menge von Operationen "Bit-Borrowing" zwei Zahlen nennen. Lassen Sie uns ein anderes Beispiel machen. 20 und 61.
20 61
010100 111101
010101 111100
010111 111000
111111 100000
63 32
Unser Endresultat ist also 32, 63. Lassen Sie uns noch eines tun . 31 und 12. 31 ist bereits größer als 12, es gibt also nichts zu tun! Bit-Ausleihe 31 und 12 ergibt 31 und 12, keine Änderung.
Die Herausforderung
Ihre Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die zwei Zahlen aufnimmt und diese ausleiht. Die beiden Zahlen sind immer positive ganze Zahlen. Ihre Eingabe und Ausgabe kann in jedem vernünftigen Format erfolgen.
Test IO:
Input: 2, 3
Output: 3, 2
Input: 3, 2
Output: 3, 2
Input: 8, 23
Output: 31, 0
Input: 42, 81
Output: 63, 0
Input: 38, 41
Output: 47, 32
Input: 16, 73
Output: 23, 0
Input: 17, 17
Output: 17, 17
Es gelten Standardlücken und die kürzeste Antwort in Bytes gewinnt!
Python, 42 Bytes
Danke an @ jimmy23013 für das Golfen mit 4 Bytes! Vielen Dank an @LeakyNun für das Golfen mit 2 Bytes!
Teste es auf Ideone .
quelle
Mathematica, 46 Bytes
Gleiche Methode wie in meiner Lösung in J.
Vielen Dank an @ Martin für das Speichern von 1 Byte und das Erinnern an die Infix-Anwendung
~
.Verwendung
Die Eingabe besteht aus zwei ganzzahligen Argumenten und die Ausgabe ist eine Liste mit den Bit-geliehenen Werten.
quelle
#//.{x_,y_}/;x<y:>{BitOr[x,x+1],BitAnd[y,y-1]}&
(Vielleicht hast du eine Idee, wie man es verkürzt)/.
und Bedingung/;
. Wünschte, Mathematica könnte zwischen boolesch und bitweise wechseln, indem Sie die Argumenttypen auf&&
und so untersuchen.Pyth,
292725222120191816 BytesTestsuite.
quelle
05AB1E,
1615 BytesProbieren Sie es online aus
quelle
Labyrinth ,
3734 BytesProbieren Sie es online!
Erläuterung
Schnelle Labyrinth-Grundierung:
Das Programm verwendet den gleichen Algorithmus wie die anderen Antworten: Wir ersetzen
(a, b)
durch(a | a+1, b & b-1)
so langea < b
. Ich werde eine vollständige Erklärung hinzufügen, nachdem ich versucht habe, noch mehr Golf zu spielen.Die IP beginnt in der oberen linken Ecke und geht nach rechts.
?
liest eine ganze Zahla
. Dann"
ist es ein No-Op, aber es ist notwendig zu verhindern, dass sich die IP sofort nach unten bewegt. Dies ist auch eine Sackgasse, so dass sich die IP umdreht und?
erneut ausgeführt wird, um zu lesenb
.}
dann wechselt manb
von main nach aux , also haben wir jetzt:Das macht
|
dann nichts, weil es das bitweise ODER vona
und nimmt0
. Da wir wissen, dassa
es immer positiv ist, dreht sich die IP nach Osten (weil sie nicht nach Westen drehen kann). Dies beginnt die Hauptschleife des Programms. Wir beginnen mit einem kurzen linearen Abschnitt, um zu vergleichena
undb
:Die IP ist jetzt an einer anderen Kreuzung. Betrachten wir zunächst den Fall, in dem das Ergebnis positiv ist. Das bedeutet
b > a
und wir müssen noch eine Iteration durchführen. Diese Iteration ist auch vollständig linear. Beachten Sie, dass die Stapel derzeit:Und dann sind wir wieder am Anfang der Schleife (da
a
es wieder positiv ist, dreht sich die IP wieder nach Osten).Wenn irgendwann
b-a
nicht mehr positiv ist, nimmt die IP einen der beiden anderen Pfade. Beachten Sie, dass in beiden Fällen holen wira
mit{
, dann eine Ecke treffen , wo die IP die Kurve folgt und dann druckena
mit!
. Jetzt befindet sich der Stack wieder oben,b-a
was bedeutet, dass sich die IP in beiden Fällen nach Osten bewegt. Jetzt bleibt nur noch ein kurzes lineares Bit:quelle
Java 7, 73 Bytes
Ungolfed & Testfälle:
Probieren Sie es hier aus.
Ausgabe:
Alte Herausforderungsregeln [
126125123 Bytes]:ANMERKUNG: Die alten Abfrageregeln verwendeten zwei Ganzzahl-Arrays als Eingabe anstelle von zwei losen Ganzzahlen.
quelle
while
Schleife wiefor(;x<y;x|=x+1,y&=y-1);
-_-
Ich wünschte, ich hätte es von Anfang an besser geschrieben. Zum Glück ist es keine unvernünftige oder drastische Veränderung. Auch ja, ich habe nicht jede Antwort kommentiert, aber ich habe jeden Benutzer informiert. Ich hatte keine Lust, denselben Benutzer mehrmals zu informieren. Ich habe Dennis 'Post nicht kommentiert, aber das liegt daran, dass er einer der Benutzer war, die mich dazu ermutigten, ihn anfangs zu ändern.JavaScript (ES6), 33 Byte
Einfacher Port der Antworten von @miles.
quelle
f=
Ath am Anfang vergessen : PJulia, 27 Bytes
Probieren Sie es online!
Wie es funktioniert
Wir definieren den binären Operator
<|
für unsere Zwecke. Es ist in neueren Versionen von Julia undefiniert, wird jedoch vom Parser weiterhin als Operator erkannt. Während\
(nicht explizit für Ganzzahlen definiert) ein Byte kürzer ist, müsste esx|-~x<|y&~-y
bei seiner hohen Priorität durch ersetzt werden(x|-~x)\(y&~-y)
, wodurch die Byte-Anzahl erhöht wird.<|
prüft, ob das erste Argument genau kleiner als das zweite ist. Wenn ja, ruft es sich rekursiv mit den Argumenten x | auf - ~ x = x | (x + 1) und y & ndash; y = y & ndash; (y - 1) .Durch das Hinzufügen von 1 zu x werden alle nachfolgenden gesetzten Bits und das niedrigste nicht gesetzte Bit umgeschaltet, x | (x + 1) schaltet das niedrigste nicht gesetzte Bit (und keine anderen Bits) um. Ebenso, da durch Subtrahieren von 1 von y alle nachfolgenden nicht gesetzten Bits und das niedrigste gesetzte Bit umgeschaltet werden, ist y & (y + 1) das niedrigste gesetzte Bit um.
Schließlich, wenn die Ungleichung x <y nicht mehr gilt,
<|
das Paar [x, y] zurückgegeben .quelle
MATLAB,
6766 BytesSchleife:
rekursiv (67 Bytes):
Gleicher Ansatz zum Ändern von Bits wie bei vielen anderen Antworten.
quelle
Clojure, 63 Bytes
Gleiche Methode wie in meiner Lösung in J.
Verwendung
quelle