"Bit-borrow" two numbers

Question

Did you know that a small number can borrow bits from a larger number? Here's an example. Let's say our two numbers 5 and 14. First, write them out in binary:

5       14
000101  001110

First we take the smallest on bit away from the larger number, and we give it to the smallest off bit on the other number. So

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

Now we have

000111  001100

and our numbers are 7 and 12. The first number is still smaller, so we continue.

000111  001100
001111  001000

Now we have 15 and 8, so we can stop. We'll call this set of operations "bit-borrowing" two numbers. Let's do another example. 20 and 61.

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

So our end result is 32, 63. Let's do one more. 31, and 12. 31 is already bigger than 12, so there's nothing to do! Bit-borrowing 31 and 12 gives 31 and 12, no change.

The challenge

Your challenge is to write a program or function that takes two numbers and bit-borrows them. The two numbers will always positive integers. Your input and output can be in any reasonable format.

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

Standard loopholes apply, and shortest answer in bytes wins!

Answer 1

Jelly, 11 bytes

~1¦&N$^µ</¿

Try it online! or verify all test cases.

Background

We can extract the last set bit of an integer n as follows.

n + 1 toggles all trailing set bits of n and the adjacent unset bit. For example, 10011₂ + 1 = 10100₂.

Since ~n = -(n + 1) = -n - 1, -n = ~n + 1, so -n applies the above to the bitwise NOT of n (which toggles all bits), thus toggling all bits before the last 1.

For example, -10100₂ = ~10100₂ + 1 = 01011₂ + 1 = 01100₂.

By taking n & -n the bitwise AND of n and -n all bits before the last set bit are nullified (since unequal in n and -n), thus yielding the last set bit of n.

For example, 10100₂ & -10100₂ = 10100₂ & 01100₂ = 00100₂.

Thus XORing n with n & -n unsets the last set bit of n.

Conversely, to unset the last set bit of n, it suffices to apply the above to ~n, from where we derive the formula n ^ (~n & -~n).

How it works

~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].

Answer 2

J, 31 26 bytes

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

Straight-forward approach using recursion and bitwise tricks. In order to turn off (set to 0) the right-most on (1) bit for a value n, you can perform bitwise-and between n and n-1, and to turn on (set to 1) the right-most off (0) bit for a value n, you can perform bitwise-or between n and n+1.

Usage

The input consists of two integers, one applied on the LHS and the other on the RHS, and the output is a list of the bit-borrowed values.

   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

Explanation

,`(($:~(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

Answer 3

Python, 42 bytes

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

Thanks to @jimmy23013 for golfing off 4 bytes! Thanks to @LeakyNun for golfing off 2 bytes!

Test it on Ideone.

Answer 4

Mathematica, 46 bytes

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

Same method as used in my solution in J.

Thanks to @Martin for saving 1 byte and reminding me of infix application ~.

Usage

The input consists of two integer arguments and the output is a list with the bit-borrowed values.

Answer 5

Pyth, 29 27 25 22 21 20 19 18 16 bytes

MxG^2x_+\0.BG`HCm.W<FHgVZU2dC
MxG^2x_+0jG2HCm.W<FHgVZU2dC
Cm.W<FH.bxN^2x_+0jN2YZ2dC
m.W<FH.bxN^2x_+0jN2YZ2      <-- changed input/output format
m.W<FH.exb^2x_+0jb2kZ
m.W<FH.U,.|bhb.&ZtZZ
.W<FH.U,.|bhb.&ZtZZ         <-- changed input/output format
.W<FH.U,.|bhb.&ZtZ
.W<FH.U,.|bhb.&t

Test suite.

Answer 6

05AB1E, 16 15 bytes

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

Try it online

Answer 7

Labyrinth, 37 34 bytes

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

Try it online!

Explanation

Quick Labyrinth primer:

• Labyrinth operates on two stacks of arbitrary-precision integers, main and auxiliary, which are initially filled with an (implicit) infinite amount of zeros.
• The source code resembles a maze, where the instruction pointer (IP) follows corridors. All interesting control flow happens at junctions: when the IP has more than one cell to go to, the top of the main stack is inspected. If the value is negative, the IP turns left, if it's positive, the IP turns right, and otherwise it moves straight ahead. If the chosen direction is blocked by a wall (i.e. a space), the IP moves in the opposite direction instead.

The program uses the same algorithm as the other answers: we replace (a, b) with (a | a+1, b & b-1) as long as a < b. I'll add a full explanation after I've tried golfing it some more.

The IP starts in the top left corner, going right. ? reads an integer a. Then " is a no-op, but it's necessary to prevent the IP from moving down immediately. This is also a dead end, so the IP turns around and executes ? again to read b. } then moves b from main to aux, so now we've got:

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

The | then does nothing, because it takes the bitwise OR of a and 0. Since we know a is always positive, the IP turns east (because it can't turn west). This begins the main loop of the program. We start with a short linear section in order to compare a and 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.

The IP is now at another junction. First, let's consider the case where the result is positive. That means b > a and we need to perform one more iteration. That iteration is also completely linear. Note that the stacks are currently:

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.

And then we're back to the start of the loop (since a is again positive, the IP turns east again).

If at some point b-a is no longer positive, the IP will take one of the other two paths. Note that in both cases we fetch a with {, then hit a corner where the IP follows the bend and then print a with !. Now the top of the stack is again b-a which means that in both cases the IP will end up moving east. All that's left is a short linear bit now:

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

Answer 8

Java 7, 73 bytes

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

Ungolfed & test cases:

Try it here.

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

Output:

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

---

Old challenge rules [126 125 123 bytes]:

NOTE: The old challenge rules used two integer-arrays as input, instead of two loose integers.

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

Answer 9

JavaScript (ES6), 33 bytes

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

Simple port of the answers by @miles.

Answer 10

Julia, 27 bytes

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

Try it online!

How it works

We define the binary operator <| for our purposes. It is undefined in recent versions of Julia, but still recognized as an operator by the parser. While \ (not explicitly defined for integers) is one byte shorter, its high precedence would require replacing x|-~x<|y&~-y with (x|-~x)\(y&~-y), thus increasing the byte count.

<| checks if its first argument is strictly less than the second one. If so, it recursively calls itself with arguments x | -~x = x | (x + 1) and y & ~-y = y & (y - 1).

Since adding 1 to x toggles all trailing set bits and the lowest unset bit, x | (x + 1) toggles the lowest unset bit (and no other bits). Likewise, since subtracting 1 from y toggles all trailing unset bits and the lowest set bit, y & (y + 1) toggles the lowest set bit.

Finally, when the inequality x < y no longer holds, <| returns the pair [x, y].

Answer 11

MATLAB, 67 66 bytes

loop:

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

recursive (67 bytes):

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

Same approach to changing bits as many other anwers.

Answer 12

Clojure, 63 bytes

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

Same method as used in my solution in J.

Usage

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