¿Sabía que un número pequeño puede tomar prestados bits de un número mayor? Aquí hay un ejemplo. Digamos nuestros dos números 5 y 14. Primero, escríbalos en binario:
5 14
000101 001110
En primer lugar tomamos el más pequeño en poco lejos del mayor número, y se lo damos a los más pequeños fuera poco en el otro número. Entonces
This bit turns off
|
v
000101 001110
^
|
This bit turns on
Ahora tenemos
000111 001100
y nuestros números son 7 y 12. El primer número es aún más pequeño, así que continuamos.
000111 001100
001111 001000
Ahora tenemos 15 y 8, para que podamos parar. Llamaremos a este conjunto de operaciones "préstamo de bits" dos números. Hagamos otro ejemplo. 20 y 61.
20 61
010100 111101
010101 111100
010111 111000
111111 100000
63 32
Entonces nuestro resultado final es 32, 63. Hagamos uno más. 31 y 12. 31 ya es más grande que 12, ¡así que no hay nada que hacer! El préstamo de bits 31 y 12 da 31 y 12, sin cambios.
El reto
Su desafío es escribir un programa o función que tome dos números y los tome prestados. Los dos números siempre serán enteros positivos. Su entrada y salida puede estar en cualquier formato razonable.
Prueba 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
Se aplican lagunas estándar, ¡y la respuesta más corta en bytes gana!
Python, 42 bytes
¡Gracias a @ jimmy23013 por jugar golf 4 bytes! ¡Gracias a @LeakyNun por jugar 2 bytes!
Pruébalo en Ideone .
fuente
Mathematica, 46 bytes
El mismo método utilizado en mi solución en J.
Gracias a @ Martin por guardar 1 byte y recordarme la aplicación infix
~
.Uso
La entrada consta de dos argumentos enteros y la salida es una lista con los valores prestados en bits.
fuente
#//.{x_,y_}/;x<y:>{BitOr[x,x+1],BitAnd[y,y-1]}&
(aunque quizás tengas una idea de cómo acortarlo)/.
y la condición/;
. Wish Mathematica podría cambiar entre booleano y bit a bit al inspeccionar los tipos de argumento&&
y tal.Pyth,
292725222120191816 bytesBanco de pruebas.
fuente
05AB1E,
1615 bytesPruébalo en línea
fuente
Laberinto ,
3734 bytesPruébalo en línea!
Explicación
Imprimación de laberinto rápido:
El programa usa el mismo algoritmo que las otras respuestas: reemplazamos
(a, b)
con(a | a+1, b & b-1)
tanto tiempo comoa < b
. Agregaré una explicación completa después de haber intentado jugar al golf un poco más.La IP comienza en la esquina superior izquierda, hacia la derecha.
?
lee un enteroa
. Entonces"
es un no-op, pero es necesario evitar que la IP baje inmediatamente. Esto también es un callejón sin salida, por lo que la IP se da vuelta y se ejecuta?
nuevamente para leerb
.}
luego se mueveb
de main a aux , así que ahora tenemos:La
|
continuación no hace nada, ya que lleva el operador OR dea
y0
. Como sabemosa
que siempre es positivo, la IP gira hacia el este (porque no puede girar hacia el oeste). Esto comienza el ciclo principal del programa. Comenzamos con una sección lineal corta para comparara
yb
:La IP está ahora en otra unión. Primero, consideremos el caso donde el resultado es positivo. Eso significa
b > a
y tenemos que realizar una iteración más. Esa iteración también es completamente lineal. Tenga en cuenta que las pilas son actualmente:Y luego volvemos al inicio del ciclo (dado
a
que nuevamente es positivo, la IP vuelve a girar hacia el este).Si en algún momento
b-a
ya no es positivo, la IP tomará una de las otras dos rutas. Tenga en cuenta que en ambos casos buscamos aa
la{
, después haga clic en una esquina donde la IP sigue la curva y luego imprimira
con!
. Ahora la parte superior de la pila está nuevamente, lob-a
que significa que en ambos casos la IP terminará moviéndose hacia el este. Todo lo que queda es un bit lineal corto ahora:fuente
Java 7, 73 bytes
Sin golf y casos de prueba:
Pruébalo aquí
Salida:
Reglas del desafío de edad [
126125123 bytes]:NOTA: Las antiguas reglas de desafío usaban dos matrices de enteros como entrada, en lugar de dos enteros sueltos.
fuente
while
ciclo de esta manerafor(;x<y;x|=x+1,y&=y-1);
-_-
Desearía haberlo escrito mejor desde el principio. Afortunadamente no es un cambio irrazonable o drástico. Además, sí, no comenté cada respuesta, pero informé a cada usuario. No tenía ganas de informar al mismo usuario varias veces. No hice ningún comentario sobre la publicación de Dennis, pero eso se debe a que fue uno de los usuarios que me animó a cambiarla inicialmente.JavaScript (ES6), 33 bytes
Puerto simple de las respuestas de @miles.
fuente
f=
att al principio: PJulia, 27 bytes
Pruébalo en línea!
Cómo funciona
Definimos el operador binario
<|
para nuestros propósitos. No está definido en las versiones recientes de Julia, pero el analizador aún lo reconoce como operador. Si bien\
(no está definido explícitamente para enteros) es un byte más corto, su alta prioridad requeriría reemplazarsex|-~x<|y&~-y
por(x|-~x)\(y&~-y)
, aumentando así el número de bytes.<|
comprueba si su primer argumento es estrictamente menor que el segundo. Si es así, se llama recursivamente con argumentos x | - ~ x = x | (x + 1) y y & ~ -y = y & (y - 1) .Dado que agregar 1 a x alterna todos los bits del conjunto final y el bit sin establecer más bajo, x | (x + 1) alterna el bit sin establecer más bajo (y ningún otro bit). Del mismo modo, dado que restando 1 de y alterna todos los bits no establecidos finales y el bit establecido más bajo, y & (y + 1) alterna el bit establecido más bajo.
Finalmente, cuando la desigualdad x <y ya no se mantiene,
<|
devuelve el par [x, y] .fuente
MATLAB,
6766 byteslazo:
recursivo (67 bytes):
El mismo enfoque para cambiar los bits que muchas otras respuestas.
fuente
Clojure, 63 bytes
Mismo método que el usado en mi solución en J.
Uso
fuente