Czy wiesz, że mała liczba może pożyczyć bity od większej liczby? Oto przykład. Powiedzmy, że nasze dwie liczby 5 i 14. Najpierw napisz je dwójkowo:
5 14
000101 001110
Pierwszy bierzemy najmniejszy na nieco z dala od większej liczby i dajemy je do najmniejszego off nieco na inny numer. Więc
This bit turns off
|
v
000101 001110
^
|
This bit turns on
Teraz mamy
000111 001100
a nasze liczby to 7 i 12. Pierwsza liczba jest jeszcze mniejsza, więc kontynuujemy.
000111 001100
001111 001000
Teraz mamy 15 i 8, więc możemy przestać. Ten zestaw operacji nazwiemy „pożyczaniem bitów” dwoma liczbami. Zróbmy inny przykład. 20 i 61.
20 61
010100 111101
010101 111100
010111 111000
111111 100000
63 32
Więc nasz wynik końcowy to 32, 63. Zróbmy jeszcze jeden . 31 i 12. 31 jest już większy niż 12, więc nie ma nic do roboty! Pożyczanie bitów 31 i 12 daje 31 i 12, bez zmian.
Wyzwanie
Twoim wyzwaniem jest napisanie programu lub funkcji, która pobierze dwie liczby i pożyczy je bit. Te dwie liczby zawsze będą dodatnimi liczbami całkowitymi. Twoje dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie.
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
Obowiązują standardowe luki, a najkrótsza odpowiedź w bajtach wygrywa!
Python, 42 bajty
Dzięki @ jimmy23013 za grę w golfa z 4 bajtów! Dzięki @LeakyNun za grę w golfa na 2 bajtach!
Przetestuj na Ideone .
źródło
Mathematica, 46 bajtów
Ta sama metoda, jak w moim rozwiązaniu w J.
Dzięki @ Martin za uratowanie 1 bajtu i przypomnienie mi o aplikacji infix
~
.Stosowanie
Dane wejściowe składają się z dwóch argumentów liczb całkowitych, a dane wyjściowe to lista z zapożyczonymi bitami wartościami.
źródło
#//.{x_,y_}/;x<y:>{BitOr[x,x+1],BitAnd[y,y-1]}&
(może masz pomysł, jak to skrócić)/.
i warunku/;
. Wish Mathematica może przełączać się między wartościami logicznymi i bitowymi, sprawdzając typy argumentów na&&
i takie.Pyth,
292725222120191816 bajtówZestaw testowy.
źródło
05AB1E,
1615 bajtówWypróbuj online
źródło
Labirynt ,
3734 bajtówWypróbuj online!
Wyjaśnienie
Podkład Quick Labyrinth:
Program korzysta z tego samego algorytmu jak inne odpowiedzi: zamieniamy
(a, b)
z(a | a+1, b & b-1)
jak długoa < b
. Dodam pełne wyjaśnienie po tym, jak spróbuję trochę zagrać w golfa.Adres IP zaczyna się w lewym górnym rogu i biegnie w prawo.
?
czyta liczbę całkowitąa
. Wtedy"
nie ma operacji, ale konieczne jest, aby zapobiec natychmiastowemu obniżeniu adresu IP. Jest to również ślepy zaułek, więc adres IP odwraca się i wykonuje?
ponownie, aby odczytaćb
.}
następnie przechodzib
z głównego do Aux , więc teraz mamy:|
Wtedy nic nie robi, bo to trwa bitowe ORa
i0
. Ponieważ wiemy, żea
zawsze jest pozytywna, IP skręca na wschód (ponieważ nie może skręcić na zachód). Rozpoczyna się główna pętla programu. Zaczynamy od krótkiego odcinka liniowego w celu porównaniaa
ib
:Adres IP znajduje się teraz na innym skrzyżowaniu. Najpierw rozważmy przypadek, w którym wynik jest pozytywny. To oznacza
b > a
i musimy wykonać jeszcze jedną iterację. Ta iteracja jest również całkowicie liniowa. Pamiętaj, że stosy są obecnie:A potem wracamy do początku pętli (ponieważ
a
znów jest dodatnia, IP ponownie skręca na wschód).Jeśli w którymś momencie
b-a
nie będzie już dodatni, adres IP przejdzie jedną z dwóch pozostałych ścieżek. Zauważ, że w obu przypadkach pobieramy zaa
pomocą{
, następnie uderzamy w róg, w którym IP następuje po zakręcie, a następnie drukujemy zaa
pomocą!
. Teraz górna część stosu jest ponownie,b-a
co oznacza, że w obu przypadkach IP skończy się na wschodzie. Pozostaje teraz tylko krótki liniowy fragment:źródło
Java 7, 73 bajty
Przypadki bez golfa i testy:
Wypróbuj tutaj.
Wynik:
Stare reguły wyzwania [
126125123 bajtów]:UWAGA: Stare reguły wyzwań wykorzystywały dwie tablice liczb całkowitych jako dane wejściowe, zamiast dwóch luźnych liczb całkowitych.
źródło
while
pętlę w ten sposóbfor(;x<y;x|=x+1,y&=y-1);
-_-
Chciałbym napisać to lepiej od samego początku. Na szczęście nie jest to nieuzasadniona ani drastyczna zmiana. Tak, nie komentowałem każdej odpowiedzi, ale poinformowałem każdego użytkownika. Nie miałem ochoty wiele razy informować tego samego użytkownika. Nie skomentowałem posta Dennisa, ale to dlatego, że był jednym z użytkowników, którzy początkowo zachęcali mnie do zmiany.JavaScript (ES6), 33 bajty
Prosty port odpowiedzi @miles.
źródło
f=
sportowca na początku: PJulia, 27 bajtów
Wypróbuj online!
Jak to działa
Definiujemy operatora binarnego
<|
do naszych celów. Nie jest zdefiniowane w najnowszych wersjach Julii, ale nadal jest rozpoznawane przez parser jako operator. Chociaż\
(nie zdefiniowany wyraźnie dla liczb całkowitych) jest o jeden bajt krótszy, jego wysoki priorytet wymagałby zastąpieniax|-~x<|y&~-y
go(x|-~x)\(y&~-y)
, zwiększając w ten sposób liczbę bajtów.<|
sprawdza, czy jego pierwszy argument jest ściśle mniejszy niż drugi. Jeśli tak, rekurencyjnie wywołuje się z argumentami x | - ~ x = x | (x + 1) oraz y & ~ -y = y & (y - 1) .Ponieważ dodanie 1 do x przełącza wszystkie końcowe bity zestawu i najniższy niezbity bit, x | (x + 1) przełącza najniższy niezbity bit (i żadnych innych bitów). Podobnie, ponieważ odjęcie 1 od y przełącza wszystkie końcowe nieuzbrojone bity i najniższy ustawiony bit, y & (y + 1) przełącza najniższy ustawiony bit.
Wreszcie, gdy nierówność x <y już się nie utrzymuje,
<|
zwraca parę [x, y] .źródło
MATLAB,
6766 bajtówpętla:
rekurencyjny (67 bajtów):
Takie samo podejście do zmiany bitów, jak wiele innych anwersów.
źródło
Clojure, 63 bajty
Ta sama metoda, jak w moim rozwiązaniu w J.
Stosowanie
źródło