Saviez-vous qu'un petit nombre peut emprunter des bits à un plus grand nombre? Voici un exemple. Disons nos deux nombres 5 et 14. Tout d'abord, écrivez-les en binaire:

5       14
000101  001110

D' abord , nous prenons le plus petit sur peu loin du plus grand nombre, et nous donnons au plus petit de peu sur l'autre numéro. Donc

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

Maintenant nous avons

000111  001100

et nos nombres sont 7 et 12. Le premier nombre est encore plus petit, alors nous continuons.

000111  001100
001111  001000

Nous avons maintenant 15 et 8, donc nous pouvons arrêter. Nous appellerons cet ensemble d'opérations "emprunt de bits" deux nombres. Faisons un autre exemple. 20 et 61.

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

Donc, notre résultat final est 32, 63. Faisons-en un de plus. 31 et 12. 31 est déjà plus grand que 12, donc il n'y a rien à faire! L'emprunt de bits 31 et 12 donne 31 et 12, aucun changement.

Le défi

Votre défi est d'écrire un programme ou une fonction qui prend deux nombres et les emprunte en bits. Les deux nombres seront toujours des entiers positifs. Vos entrées et sorties peuvent être dans n'importe quel format raisonnable.

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

Les failles standard s'appliquent et la réponse la plus courte en octets gagne!

Gelée , 11 octets

~1¦&N$^µ</¿

Essayez-le en ligne! ou vérifiez tous les cas de test .

Contexte

Nous pouvons extraire le dernier bit défini d'un entier n comme suit.

n + 1 bascule tous les bits de fin de jeu de n et le bit non défini adjacent. Par exemple, 10011 ₂ + 1 = 10100 ₂ .

Puisque ~ n = - (n + 1) = -n - 1 , -n = ~ n + 1 , donc -n applique ce qui précède au NOT binaire de n (qui bascule tous les bits), basculant ainsi tous les bits avant le dernier 1 .

Par exemple, -10100 ₂ = ~ 10100 ₂ + 1 = 01011 ₂ + 1 = 01100 ₂ .

En prenant n & -n le AND au niveau du bit de n et -n, tous les bits avant le dernier bit défini sont annulés (car inégaux en n et -n ), donnant ainsi le dernier bit défini de n .

Par exemple, 10100 ₂ & -10100 ₂ = 10100 ₂ & 01100 ₂ = 00100 ₂ .

Ainsi, XORing n avec n & -n désactive le dernier bit défini de n .

Inversement, pour supprimer le dernier bit défini de n , il suffit d'appliquer ce qui précède à ~ n , d'où nous dérivons la formule n ^ (~ n & - ~ n) .

Comment ça fonctionne

~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 octets

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

Approche directe utilisant la récursivité et les astuces au niveau du bit. Pour désactiver (défini sur 0 ) le bit le plus à droite ( 1 ) pour une valeur n , vous pouvez effectuer au niveau du bit et entre n et n -1, et activer (défini sur 1 ) le bit le plus à droite off ( 0 ) bit pour une valeur n , vous pouvez effectuer au niveau du bit ou entre n et n +1.

Usage

L'entrée se compose de deux entiers, l'un appliqué sur le LHS et l'autre sur le RHS, et la sortie est une liste des valeurs empruntées en bits.

   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

Explication

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

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

Merci à @ jimmy23013 pour avoir joué au golf sur 4 octets! Merci à @LeakyNun d'avoir joué au golf sur 2 octets!

Testez-le sur Ideone .

Mathematica, 46 octets

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

Même méthode que celle utilisée dans ma solution dans J.

Merci à @ Martin d' avoir sauvé 1 octet et de me rappeler l'application infixe ~.

Usage

L'entrée se compose de deux arguments entiers et la sortie est une liste avec les valeurs empruntées en bits.

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

MxG ^ _ 2x + \ 0.BG`HCm.W <FHgVZU2dC 
MxG ^ 2x_ + 0jG2HCm.W <FHgVZU2dC 
Cm.W <^ FH.bxN 2x_ + 0jN2YZ2dC 
m.W <^ FH.bxN 2x_ + 0jN2YZ2       <- entrée / sortie modifiée format
 mW <FH.exb ^ 2x_ + 0jb2kZ 
m.W <FH.U ,. | bhb. & ZtZZ 
.W <FH.U ,. | bhb. & ZtZZ          <- format d'entrée / sortie modifié
 .W <FH.U ,. | | bhb. & ZtZ
.W <FH.U ,. | bhb. & T

Suite de tests.

05AB1E, 16 15 octets

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

Essayez-le en ligne

Labyrinthe , 37 34 octets

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

Essayez-le en ligne!

Explication

Primaire Quick Labyrinth:

• Labyrinth fonctionne sur deux piles d'entiers de précision arbitraire, principale et auxiliaire , qui sont initialement remplis d'une quantité infinie (implicite) de zéros.
• Le code source ressemble à un labyrinthe, où le pointeur d'instruction (IP) suit les couloirs. Tous les flux de contrôle intéressants se produisent aux jonctions: lorsque l'IP a plus d'une cellule vers laquelle aller, le haut de la pile principale est inspecté. Si la valeur est négative, l'IP tourne à gauche, s'il est positif, l'IP tourne à droite, et sinon il se déplace tout droit. Si la direction choisie est bloquée par un mur (c'est-à-dire un espace), l'IP se déplace dans la direction opposée à la place.

Le programme utilise le même algorithme que les autres réponses: nous remplaçons (a, b)par (a | a+1, b & b-1)aussi longtemps quea < b . J'ajouterai une explication complète après avoir essayé de jouer au golf un peu plus.

L'IP commence dans le coin supérieur gauche, va à droite. ?lit un entier a. Ensuite, il "n'y a pas d'opération, mais il est nécessaire d'empêcher l'IP de descendre immédiatement. C'est aussi une impasse, donc l'IP se retourne et s'exécute à ?nouveau pour lire b. }passe ensuite bde main à Aux , alors maintenant nous avons:

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

Le |ne fait alors rien, car il prend le OU au niveau du bit de aet 0. Puisque nous savons que ac'est toujours positif, l'IP tourne vers l'est (parce qu'il ne peut pas tourner vers l'ouest). Cela commence la boucle principale du programme. Nous commençons par une courte section linéaire afin de comparer aet 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.

L'IP est maintenant à une autre jonction. Considérons d'abord le cas où le résultat est positif. Cela signifie b > aet nous devons effectuer une autre itération. Cette itération est également complètement linéaire. Notez que les piles sont actuellement:

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.

Et puis nous revenons au début de la boucle (depuis a étant à nouveau positif, l'IP tourne à nouveau vers l'est).

Si, à un moment donné, il b-an'est plus positif, l'IP prendra l'un des deux autres chemins. Notez que dans les deux cas, nous allons chercher aavec {, puis frappons un coin où l'IP suit le virage, puis imprimons aavec !. Maintenant, le haut de la pile est à nouveau, b-ace qui signifie que dans les deux cas, l'IP finira par se déplacer vers l'est. Il ne reste plus qu'un petit morceau linéaire:

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

Java 7, 73 octets

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

Cas non testés et testés:

Essayez-le ici.

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

Production:

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

Anciennes règles de contestation [ 126 125 123 octets]:

REMARQUE: les anciennes règles de défi utilisaient deux tableaux entiers en entrée, au lieu de deux entiers lâches.

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 octets

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

Port simple des réponses par @miles.

Julia, 27 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Nous définissons l'opérateur binaire <|pour nos besoins. Il n'est pas défini dans les versions récentes de Julia, mais est toujours reconnu comme opérateur par l'analyseur. Bien que \(non explicitement défini pour les entiers) soit un octet plus court, sa priorité élevée nécessiterait de remplacerx|-~x<|y&~-y par(x|-~x)\(y&~-y) , augmentant ainsi le nombre d'octets.

<|vérifie si son premier argument est strictement inférieur au second. Si c'est le cas, il s'appelle récursivement avec des arguments x | - ~ x = x | (x + 1) et y & ~ -y = y & (y - 1) .

Depuis l'ajout de 1 à x, tous les bits de fin et le bit non défini le plus bas basculent, x | (x + 1) bascule le bit non défini le plus bas (et aucun autre bit). De même, puisque la soustraction de 1 à y bascule tous les bits non définis de fin et le bit le plus bas défini, y & (y + 1) bascule le bit le plus bas défini.

Enfin, lorsque l'inégalité x <y ne tient plus, <|retourne la paire [x, y] .

MATLAB, 67 66 octets

boucle:

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

récursif (67 octets):

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

Même approche pour changer les bits que beaucoup d'autres réponses.

Clojure, 63 octets

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

Même méthode que celle utilisée dans ma solution dans 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])