Знаете ли вы, что небольшое число может позаимствовать биты у большего числа? Вот пример. Допустим, наши два числа 5 и 14. Сначала запишите их в двоичном виде:

5       14
000101  001110

Сначала мы берем наименьшее на бит от большего числа, и мы даем его наименьший от бита на другой номер. Так

This bit turns off
            |
            v
000101  001110
    ^
    |
This bit turns on

Теперь у нас есть

000111  001100

и наши числа 7 и 12. Первое число все еще меньше, поэтому мы продолжим.

000111  001100
001111  001000

Теперь у нас 15 и 8, поэтому мы можем остановиться. Мы назовем этот набор операций «заимствование битов» двумя числами. Давайте сделаем еще один пример. 20 и 61.

20        61
010100    111101
010101    111100
010111    111000
111111    100000
63        32

Таким образом, наш конечный результат 32, 63. Давайте сделаем еще один . 31, а 12. 31 уже больше 12, так что ничего не поделаешь! Заимствование битов 31 и 12 дает 31 и 12, без изменений.

Соревнование

Ваша задача - написать программу или функцию, которая принимает два числа и заимствует их. Два числа всегда будут положительными целыми числами. Ваш ввод и вывод могут быть в любом разумном формате.

Тест 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

Применяются стандартные лазейки, и выигрывает кратчайший ответ в байтах!

Желе , 11 байт

~1¦&N$^µ</¿

Попробуйте онлайн! или проверьте все контрольные примеры .

Фон

Мы можем извлечь последний установленный бит целого числа n следующим образом.

n + 1 переключает все завершающие установленные биты n и соседний неустановленный бит. Например, 10011 ₂ + 1 = 10100 ₂ .

Так как ~ n = - (n + 1) = -n - 1 , -n = ~ n + 1 , то -n применяет вышеупомянутое к битовому НЕ из n (который переключает все биты), таким образом переключая все биты перед последним 1 .

Например, -10100 ₂ = ~ 10100 ₂ + 1 = 01011 ₂ + 1 = 01100 ₂ .

Принимая n & -n, побитовое И из n и -n все биты перед последним установленным битом обнуляются (поскольку они неравны по n и -n ), таким образом, получая последний установленный бит n .

Например, 10100 ₂ & -10100 ₂ = 10100 ₂ & 01100 ₂ = 00100 ₂ .

Таким образом, XOR n с n & -n отменяет последний установленный бит n .

И наоборот, чтобы сбросить последний установленный бит n , достаточно применить вышеизложенное к ~ n , откуда мы получаем формулу n ^ (~ n & - ~ n) .

Как это устроено

~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 байт

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

Прямой подход с использованием рекурсии и побитовых трюков. Чтобы выключить (установить на 0 ) крайний правый ( бит 1 ) для значения n , вы можете выполнить его поразрядно и между n и n -1, а также включить (установить на 1 ) самый правый бит off ( 0 ) для значения n можно выполнять поразрядно или между n и n +1.

использование

Входные данные состоят из двух целых чисел, одно из которых применяется к LHS, а другое к RHS, а выходные данные представляют собой список заимствованных битов.

   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

объяснение

,`(($:~(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 байта

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

Спасибо @ jimmy23013 за 4 байта в гольфе! Спасибо @LeakyNun за игру в 2 байта!

Проверьте это на Ideone .

Mathematica, 46 байтов

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

Тот же метод, который использовался в моем решении в J.

Спасибо @ Martin за сохранение 1 байта и напоминание мне о приложении инфикса ~.

использование

Входные данные состоят из двух целочисленных аргументов, а выходные данные представляют собой список с заимствованными битами значениями.

Pyth, 29 27 25 22 21 20 19 18 16 байт

MXG ^ 2x _ + \ 0.BG`HCm.W <FHgVZU2dC 
MXG ^ 2x_ + 0jG2HCm.W <FHgVZU2dC 
Cm.W <FH.bxN ^ 2x_ + 0jN2YZ2dC 
М.М <FH.bxN ^ 2x_ + 0jN2YZ2       <- измененная ввода / вывода формат
 mW <FH.exb ^ 2x_ + 0jb2kZ 
m.W <FH.U,. | bhb. & ZtZZ 
.W <FH.U,. | bhb. & ZtZZ          <- измененный формат ввода / вывода
 .W <FH.U ,. | BHB. & ZTZ
.W <FH.U ,. |. BHB & т

Тестирование.

05AB1E, 16 15 байт

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

Попробуйте онлайн

Лабиринт , 37 34 байта

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

Попробуйте онлайн!

объяснение

Быстрый лабиринтный праймер:

• Лабиринт работает с двумя стопками целых чисел произвольной точности, главной и вспомогательной , которые изначально заполнены (неявным) бесконечным количеством нулей.
• Исходный код напоминает лабиринт, где указатель инструкций (IP) следует за коридорами. Весь интересный поток управления происходит на стыках: когда IP имеет более чем одну ячейку, проверяется вершина основного стека. Если значение отрицательное, IP поворачивается влево, если оно положительное, IP поворачивается вправо, в противном случае он движется прямо вперед. Если выбранное направление заблокировано стеной (т. Е. Пробелом), IP перемещается в противоположном направлении.

Программа использует тот же алгоритм, что и другие ответы: мы заменим (a, b)с (a | a+1, b & b-1)тех пор , как a < b. Я добавлю полное объяснение после того, как попробую еще поиграть в гольф.

IP начинается в верхнем левом углу, идет вправо. ?считывает целое число a. Тогда "не работает, но необходимо предотвратить немедленное снижение IP-адреса. Это также тупик, поэтому IP поворачивается и ?снова выполняет чтение b. }затем переходит bот основного к вспомогательному , так что теперь у нас есть:

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

|Тогда ничего не делает, потому что он принимает побитового ИЛИ от aи 0. Поскольку мы знаем, aчто всегда положительно, IP поворачивает на восток (потому что он не может повернуть на запад). Начинается основной цикл программы. Мы начнем с короткого линейного сечения, чтобы сравнить aи 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.

IP сейчас на другом перекрестке. Сначала рассмотрим случай, когда результат положительный. Это значит, b > aи нам нужно выполнить еще одну итерацию. Эта итерация также полностью линейна. Обратите внимание, что стеки в настоящее время:

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как снова положительный, IP снова поворачивает на восток).

Если в какой-то момент b-aболее не является положительным, IP выберет один из двух других путей. Обратите внимание , что в обоих случаях мы забираем aс {, а затем врезался в угол , где IP следует изгиб , а затем распечатать aс !. Теперь вершина стека снова, b-aчто означает, что в обоих случаях IP будет в конечном итоге двигаться на восток. Все, что осталось, это короткий линейный бит:

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

Java 7, 73 байта

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

Ungolfed и тестовые случаи:

Попробуй это здесь.

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

Выход:

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

Старые правила вызова [ 126 125 123 байта]:

ПРИМЕЧАНИЕ. В старых правилах вызова вместо двух свободных целых чисел использовались два целочисленных массива.

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 байта

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

Простой порт ответов @miles.

Юлия, 27 байт

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

Попробуйте онлайн!

Как это устроено

Мы определяем бинарный оператор <|для наших целей. Он не определен в последних версиях Julia, но все еще распознается синтаксическим анализатором как оператор. Хотя \(не определено явно для целых чисел) на один байт короче, его высокий приоритет потребует замены x|-~x<|y&~-yна (x|-~x)\(y&~-y), увеличивая таким образом число байтов.

<|проверяет, является ли его первый аргумент строго меньше, чем второй. Если это так, он рекурсивно вызывает себя с аргументами x | - ~ x = x | (x + 1) и y & ~ -y = y & (y - 1) .

Поскольку добавление 1 к x переключает все завершающие биты и самый младший неустановленный бит, x | (x + 1) переключает младший неустановленный бит (и никаких других битов). Аналогично, поскольку вычитание 1 из y переключает все завершающие невыбранные биты и самый низкий установленный бит, y & (y + 1) переключает самый низкий установленный бит.

Наконец, когда неравенство x <y больше не выполняется,<| возвращается пара [x, y] .

MATLAB, 67 66 байт

цикл:

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

рекурсивный (67 байт):

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

Такой же подход к изменению битов, как и многие другие ответы.

Clojure, 63 байта

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

Тот же метод, который используется в моем решении в J.

использование

=> (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])