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!

Galaretka , 11 bajtów

~1¦&N$^µ</¿

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Możemy wyodrębnić ostatni zestaw bitów liczby całkowitej n w następujący sposób.

n + 1 przełącza wszystkie końcowe ustawione bity n i sąsiedni niezbity bit. Na przykład 10011 ₂ + 1 = 10100 ₂ .

Ponieważ ~ n = - (n + 1) = -n - 1 , -n = ~ n + 1 , więc -n stosuje powyższe do bitowego NOT z n (który przełącza wszystkie bity), w ten sposób przełączając wszystkie bity przed ostatnim 1 .

Na przykład -10100 ₂ = ~ 10100 ₂ + 1 = 01011 ₂ + 1 = 01100 ₂ .

Przyjmując n & -n bitowo AND z n i -n wszystkie bity przed ostatnim bitem zestawu są zerowane (ponieważ nierówne w n i -n ), w ten sposób uzyskując ostatni bit zestawu n .

Na przykład 10100 ₂ i -10100 ₂ = 10100 ₂ i 01100 ₂ = 00100 ₂ .

Zatem XORing N o N & -n unsets ostatni ustawiony trochę n .

I odwrotnie, aby rozbroić ostatni ustawiony bit n , wystarczy zastosować powyższe do ~ n , skąd wyprowadzamy wzór n ^ (~ n & - ~ n) .

Jak to działa

~1¦&N$^µ</¿  Main link. Argument: A (list of pairs)

          ¿  While loop:
        </     Condition: Reduce p by less-than. True iff x < y.
       µ       Body chain:
~1¦              Apply bitwise NOT to the x, first item of the pair.
     $           Convert the two links to the left into a monadic chain.
    N              Negate; multiply [~x, y] by -1, yielding [-~x, -y].
   &               Logical AND. Yields [-~x & ~x, -y & y].
      ^            Vectorized XOR with p. Yields [(-~x & ~x) ^ x, (-y & y) ^ y].

J, 31 26 bajtów

,`(($:~(OR>:))~(AND<:))@.<

Proste podejście przy użyciu rekurencji i bitowych sztuczek. Aby wyłączyć (ustawić na 0 ) najbardziej prawy bit on ( 1 ) dla wartości n , możesz wykonać bitowo - i między n i n -1, i włączyć (ustawić na 1 ) najbardziej prawy off ( 0 ) bit dla wartości n , możesz wykonać bitowo lub między n i n +1.

Stosowanie

Dane wejściowe składają się z dwóch liczb całkowitych, jednej zastosowanej w LHS, a drugiej w RHS, a wyjściem jest lista wartości pożyczonych bitów.

   f =: ,`(($:~(OR>:))~(AND<:))@.<
   2 f 3
3 2
   3 f 2
3 2
   8 f 23
31 0
   42 f 81
63 0
   38 f 41
47 32
   16 f 73
23 0
   17 f 17
17 17

Wyjaśnienie

,`(($:~(OR>:))~(AND<:))@.<  Input: x on LHS, y on RHS
                            If x < y,
,                             Form a 2-element array [x, y] and return
                            Else
                   <:         Decrement y
                AND           Perform bitwise-and on y and y-1, call it y'
          >:                  Increment x
        OR                    Perform bitwise-or on x and x+1, call it x'
    $:                        Call recursively on x' and y' and return

Python, 42 bajty

f=lambda x,y:x<y and f(x|x+1,y&y-1)or(x,y)

Dzięki @ jimmy23013 za grę w golfa z 4 bajtów! Dzięki @LeakyNun za grę w golfa na 2 bajtach!

Przetestuj na Ideone .

Mathematica, 46 bajtów

If[#<#2,BitOr[#,#+1]~#0~BitAnd[#2,#2-1],{##}]&

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.

Pyth, 29 27 25 22 21 20 19 18 16 bajtów

MxG ^ 2x _ + \ 0.BG`HCm.W <FHgVZU2dC 
MxG ^ 2x_ + 0jG2HCm.W <FHgVZU2dC 
Cm.W <FH.bxN ^ 2x_ + 0jN2YZ2dC 
m.W <FH.bxN ^ 2x_ + 0jN2YZ2       <- zmienione wejście / wyjście format
 mW <FH.exb ^ 2x_ + 0jb2kZ 
m.W <FH.U. | bhb. & ZtZZ 
.W <FH.U. | bhb. & ZtZZ          <- zmieniono format wejścia / wyjścia
 .W <FH.U. | bhb. i ZtZ
.W <FH.U. | Bhb. & T

Zestaw testowy.

05AB1E, 16 15 bajtów

[D`›#`D<&sD>~s‚

Wypróbuj online

Labirynt , 37 34 bajtów

?"
}
|=:{:
)   }
: :;-{
=&( {!;\!@

Wypróbuj online!

Wyjaśnienie

Podkład Quick Labyrinth:

• Labirynt działa na dwóch stosach liczb całkowitych o dowolnej dokładności, głównej i pomocniczej , które są początkowo wypełnione (domyślną) nieskończoną liczbą zer.
• Kod źródłowy przypomina labirynt, w którym wskaźnik instrukcji (IP) podąża za korytarzami. Cały interesujący przepływ sterowania odbywa się na skrzyżowaniach: gdy adres IP ma więcej niż jedną komórkę, do której należy przejść, sprawdzany jest szczyt głównego stosu. Jeśli wartość jest ujemna, IP skręca w lewo, jeśli jest dodatnie, IP skręca w prawo, w przeciwnym razie porusza się prosto. Jeśli wybrany kierunek jest blokowany przez ścianę (tj. Spację), IP przesuwa się w przeciwnym kierunku.

Program korzysta z tego samego algorytmu jak inne odpowiedzi: zamieniamy (a, b)z (a | a+1, b & b-1)jak długo a < 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 przechodzi bz głównego do Aux , więc teraz mamy:

Main [ ... 0 a | b 0 ...] Aux

|Wtedy nic nie robi, bo to trwa bitowe OR ai 0. Ponieważ wiemy, że azawsze 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ównania ai b:

=   Swap tops of stacks, i.e. swap a and b.
:   Duplicate b.
{   Pull a over to main.
:   Duplicate a.
}   Push one copy back to aux.
-   Compute b-a.

Adres IP znajduje się teraz na innym skrzyżowaniu. Najpierw rozważmy przypadek, w którym wynik jest pozytywny. To oznacza b > ai musimy wykonać jeszcze jedną iterację. Ta iteracja jest również całkowicie liniowa. Pamiętaj, że stosy są obecnie:

Main [ ... 0 b (b-a) | a 0 ...] Aux

;   Discard b-a.
:   Duplicate b.
(   Decrement.
&   Bitwise AND with b, clearing the least-significant 1.
=   Swap new b with old a.
:   Duplicate a.
)   Increment.
|   Bitwise OR with a, setting the least-significant 0.

A potem wracamy do początku pętli (ponieważ aznów jest dodatnia, IP ponownie skręca na wschód).

Jeśli w którymś momencie b-anie będzie już dodatni, adres IP przejdzie jedną z dwóch pozostałych ścieżek. Zauważ, że w obu przypadkach pobieramy za apomocą {, następnie uderzamy w róg, w którym IP następuje po zakręcie, a następnie drukujemy za apomocą !. Teraz górna część stosu jest ponownie, b-aco oznacza, że ​​w obu przypadkach IP skończy się na wschodzie. Pozostaje teraz tylko krótki liniowy fragment:

;   Discard b-a.
\   Print a linefeed.
!   Print b.
@   Terminate the program.

Java 7, 73 bajty

void d(int x,int y){while(x<y){x|=x+1;y&=y-1;}System.out.print(x+","+y);}

Przypadki bez golfa i testy:

Wypróbuj tutaj.

public class Main{
  static void d(int x, int y){
    while(x < y){
      x |= x + 1;
      y &= y - 1;
    }
    System.out.print(x + "," + y);
  }

  public static void main(String[] a){
    print(2, 3);
    print(3, 2);
    print(8, 23);
    print(42, 81);
    print(38, 41);
    print(16, 73);
    print(17, 17);
  }

  public static void print(int a, int b){
    d(a, b);
    System.out.println();
  }
}

Wynik:

3,2
3,2
31,0
63,0
47,32
23,0
17,17

Stare reguły wyzwania [ 126 125 123 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.

void d(int[]a,int[]b){int i=-1,x,y;while(++i<a.length){x=a[i];y=b[i];for(;x<y;x|=x+1,y&=y-1);System.out.println(x+","+y);}}

JavaScript (ES6), 33 bajty

f=(n,m)=>n<m?f(n|n+1,m&m-1):[n,m]

Prosty port odpowiedzi @miles.

Julia, 27 bajtów

x<|y=x<y?x|-~x<|y&~-y:[x,y]

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ąpienia x|-~x<|y&~-ygo (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] .

MATLAB, 67 66 bajtów

pętla:

function[]=f(x,y)
while x<y
x=bitor(x,x+1);y=bitand(y,y-1);end
x,y

rekurencyjny (67 bajtów):

function[]=f(x,y)
if x<y
f(bitor(x,x+1),bitand(y,y-1))
else
x,y
end

Takie samo podejście do zmiany bitów, jak wiele innych anwersów.

Clojure, 63 bajty

#(if(< % %2)(recur(bit-or %(inc %))(bit-and %2(dec %2)))[% %2])

Ta sama metoda, jak w moim rozwiązaniu w J.

Stosowanie

=> (def f #(if(< % %2)(recur(bit-or %(inc %))(bit-and %2(dec %2)))[% %2]))
=> (f 38 41)
[47 32]
=> (map (partial apply f) [[2 3] [3 2] [8 23] [42 81] [38 41] [16 73] [17 17]])
([3 2] [3 2] [31 0] [63 0] [47 32] [23 0] [17 17])