Descripción de la tarea

Dado un número entero, intercambie sus bits menos significativos (2k – 1) -th y 2k -th para todos los enteros k> 0 . Esta es la secuencia A057300 en el OEIS.

(Se supone que el número tiene "ceros infinitos infinitos". En la práctica, esto simplemente significa anteponer un solo 0 bit a números de longitud impar).

Este es el código de golf , por lo que gana el código más corto (en bytes).

Casos de prueba

0 -> 0
1 -> 2
9 -> 6
85 -> 170
220 -> 236
1827 -> 2835
47525 -> 30298

Jalea , 10 9 7 bytes

b4d2UFḄ

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

b4d2UFḄ  Main link. Argument: n (integer)

b4       Convert n to base 4.
  d2     Divmod each quaternary digit x by 2, yielding [x : 2, x % 2].
    U    Upend; reverse each pair, yielding [x % 2, x : 2].
     F   Flatten the 2D list of binary digits.
      Ḅ  Convert from binary to integer.

Python 2, 26 bytes

lambda n:2*n-3*(4**n/3&n/2)

¡Trucos de bits!

Say ntiene forma ...ghfedcbaen binario. Entonces, podemos dividirlo en partes iguales como

n   = o + 2*e
n   = ...hgfedcba
o   = ...0g0e0c0a
2*e = ...h0f0d0b0

Entonces, el resultado de cambio de bit sse puede expresar como s=2*o+e.

s   = 2*o + e
s   = ...ghefcdab
2*o = ...g0e0c0a0
e   = ...0h0f0d0b

Preferimos calcular solo uno de ey o, así que expresamos o=n-2*ey sustituimos

s=2*(n-2*e)+e = 2*n-3*e

Entonces, ahora queda por expresar een términos de n. El número M=4**n/3tiene forma ...10101010101en binario, que sirve como una máscara para los dígitos impares. El exponente nasegura que Mes lo suficientemente largo. Tomando el bit a bit andde n/2y este valor da ecomo se desea.

n/2     = ...hgfedcb
M       = ...1010101
n/2 & M = ...h0f0d0b = e

En cambio, podemos expresar een términos de o e=(n-o)/2, que da s=(n+o*3)/2, que ahorra un byte gracias a una optimización de xsot.

lambda n:n+(n&4**n/3)*3>>1

Función C, 38

Bit-twiddling:

f(x){return(x&~0U/3*2)/2+(x&~0U/3)*2;}

Ideona

O por diversión:

C función recursiva, 43

Según la fórmula OEIS ,a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

f(x){return x>3?4*f(x/4)+f(x%4):x%3?3-x:x;}

o

f(x){return x>3?4*f(x/4)+f(x%4):x%2*2+x/2;}

Ideona

CJam, 16 14 13 bytes

ri4b4e!2=f=4b

Pruébalo aquí.

Explicación

ri  e# Read input and convert to integer.
4b  e# Get base-4 digits.
4e! e# Push all permutations of [0 1 2 3].
2=  e# Select the third one which happens to be [0 2 1 3].
f=  e# For each base-4 digit select the value at that position in the previous
    e# list, which swaps 1s and 2s.
4b  e# Convert back from base 4.

Pyth, 9 bytes

iXjQ4S2)4

Pruébalo en el compilador Pyth .

Cómo funciona

  jQ4      Convert the input (Q) to base 4.
 X   S2)   Translate [1, 2] to [2, 1].
i       4  COnvert from base 4 to integer.

JavaScript (ES6), 32 30 bytes

(n,m=0x55555555)=>n*2&~m|n/2&m

Solo funciona hasta 1073741823 debido a las limitaciones de los enteros de JavaScript. 38 36 bytes funciona hasta 4294967295:

(n,m=0x55555555)=>(n*2&~m|n/2&m)>>>0

Editar: Guardado 2 bytes gracias a @ user81655.

51 bytes funciona hasta 4503599627370495:

n=>parseInt(n.toString(4).replace(/1|2/g,n=>3-n),4)

Función ASM x86: 14 bytes de código de máquina

Versión uint64_t: 24 bytes

x86-64 Convención de llamada SysV ( xin edi), pero este mismo código de máquina también funcionará en modo de 32 bits. (Donde lease decodificará como lea eax, [edi + eax*2], lo que da resultados idénticos ).

0000000000000040 <onemask_even>:
  40:   89 f8                   mov    eax,edi
  42:   25 55 55 55 55          and    eax,0x55555555
  47:   29 c7                   sub    edi,eax
  49:   d1 ef                   shr    edi,1
  4b:   8d 04 47                lea    eax,[rdi+rax*2]
  4e:   c3                      ret    
4f: <end>

0x4f - 0x40 = 14 bytes

Este es el resultado del compilador al usar la excelente idea de máscara única de xnor de la manera opuesta. (Y terminología opuesta: el bit bajo es el bit 0, que es par, no impar).

unsigned onemask_even(unsigned x) {
  unsigned emask = ~0U/3;
  unsigned e = (x & emask);
  return e*2 + ((x - e) >> 1);
}

No encontré ninguna mejora sobre lo que hace el compilador. Podría haberlo escrito como mov eax, 0x555.../ and eax, edi, pero esa es la misma longitud.

La misma función para los enteros de 64 bits toma 24 bytes (vea el enlace godbolt). No veo ninguna forma más corta que 10 bytes movabs rax, 0x55...para generar la máscara en un registro. (La divinstrucción de x86 es torpe, por lo que la división sin signo de todos por 3 no ayuda).

Se me ocurrió un bucle para generar la máscara en rax, pero son 10 bytes (exactamente la misma longitud que el mov imm64).

# since 0x55 has its low bit set, shifting it out the top of RAX will set CF
0000000000000000 <swap_bitpairs64>:
   0:   31 c0                   xor    eax,eax      ; old garbage in rax could end the loop early
0000000000000002 <swap_bitpairs64.loop>:
   2:   48 c1 e0 08             shl    rax,0x8
   6:   b0 55                   mov    al,0x55      ; set the low byte
   8:   73 f8                   jnc    2 <swap_bitpairs64.loop>  ; loop until CF is set
000000000000000a <swap_bitpairs64.rest_of_function_as_normal>:
 # 10 bytes, same as   mov  rax, 0x5555555555555555
 # rax = 0x5555...
   a:   48 21 f8                and    rax,rdi
   ...

Si supiéramos que ninguno de los bytes existentes raxtiene un conjunto de bits bajo, podríamos omitir el xor, y esto sería de 8 bytes de longitud.

Una versión anterior de esta respuesta tenía un bucle de 10 bytes usando el loopinsn, pero tenía el peor tiempo de ejecución de 0xFFFFFFFFFFFFFF08iteraciones, porque solo configuré cl.

Oasis , 17 bytes (no competitivos)

n4÷axxn4÷xxe+3120

Pruébalo en línea!

Oasis es un lenguaje diseñado por Adnan especializado en secuencias.

Actualmente, este lenguaje puede hacer recursividad y forma cerrada.

Usamos esta fórmula: a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

Especificar el caso base es simple: 3120al final simplemente significa eso a(0)=0, a(1)=2, a(2)=1, a(3)=3.

n4÷axxn4÷xxe+3120
                0  a(0) = 0
               2   a(1) = 2
              1    a(2) = 1
             3     a(3) = 3

n                  push n (input)
 4÷                integer-divide by 4
   a               a(n/4)
    xx             double twice; multiply by 4
                   now we have 4a(n/4)
      n            push n (input)
       4÷xx        integer-divide by 4 and then multiply by 4
                   since there is no modulo currently, n%4
                   is built as n-(n/4*4)
           e       we should have done a(n-(n/4*4)), but this
                   is a shortcut for a(n-x) where x is the top
                   of stack. Therefore, we now have a(n-n/4*4)
                   which is a(n%4).
            +      add.

MATL , 10 bytes

BP2eP1ePXB

Pruébalo en línea!

Versión modificada para generar los primeros términos de la secuencia ( OEIS A057300 ).

Explicación

B     % Take input implicitly. Convert to binary array
P     % Flip
2e    % Convert to two-row 2D array, padding with a trailing zero if needed. 
      % Because of the previous flip, this really corresponds to a leading zero
P     % Flip each column. This corresponds to swapping the bits
1e    % Reshape into a row
P     % Flip, to undo the initial flipping
XB    % Convert from binary array to number. Display implicitly

zsh, 28 bytes

<<<$[`tr 12 21<<<$[[#4]$1]`]

Toma la entrada como un argumento de línea de comando, sale en STDOUT.

No es compatible con Bash porque usa la sintaxis de conversión de base específica de zsh.

                       $1     input (first command line argument)
                 $[      ]    arithmetic expansion
                   [#4]       output in base 4
              <<<             pass the result of this to...
      tr                      the `tr' command
         12 21                and replace 1s with 2s, 2s with 1s
     `                    `   evaluate the result...
   $[                      ]  in another arithmetic expansion, to convert back
                                to base 10
<<<                           output the result on STDOUT

Retina, 70 bytes

. +
PS
+ `(1 +) \ 1
$ 1x
x1
1
^
X
r` (.) (.)
$ 2 $ 1
1
X@
+ `@ x
X@@
X*(@*)
$ .1
0 $

Banco de pruebas. (Ligeramente modificado.)

Bueno, solo por diversión: 7 bytes

T`12`21

Toma base-4 como entrada y salidas como base-4.

Pruébalo en línea!

05AB1E, 8 bytes

4B12‡4ö

¡Gracias a @Adnan por -5 bytes!

Utiliza la codificación CP-1252.

¡Pruébelo en línea!

Explicación:

4B       - Take input and convert to base 4.
  12Â    - Push 12 bifurcated.
     ‡   - Transliterate [1, 2] to [2, 1].
      4ö - Convert to base 10.

C, 32 30 29 bytes

f(x){return(x&~0U/3)*3+x>>1;}                // 30 bit version, see below

// less golfed:
f(x){return ((x & 0x55555555)*3 + x) >>1;}   //  >> is lower precedence than +

Algoritmo copiado del comentario de xsot sobre la respuesta de Python de xnor . En lugar de enmascarar en ambos sentidos, enmascarar en un sentido y combinar.

Esto se compila al mismo asm que la última versión que probé , y funciona (para x hasta 0x3FFFFFFFy para x por encima de eso, siempre que el bit 30 no esté configurado, ver más abajo). En el código de máquina, tiene la misma longitud que mi respuesta asm existente.

La versión anterior siempre borra la parte alta del resultado . La mejor versión segura es de 32 bytes:

g(x){return 2*x-3*(x/2U&~0U/3);}   // safe 32bit version, works for all x

La versión de Python no tiene este problema, porque python usa tipos enteros de precisión arbitraria cuando es necesario , en lugar de truncar a un límite superior fijo.

Javascript (ES6), 113109 bytes

Guardado 4 bytes gracias a Upgoat

n=>+('0b'+/(..)+$/.exec('0'+n.toString`2`)[0].split``.reduce((p,c)=>p.length-1?[p.join(c)]:[p[0],c],[''])[0],2)

Cómo funciona

n=>+('0b'+                              //parse as binary literal
    /(..)+$/.exec('0'+n.toString`2`)[0] //convert to binary string with an even number of digits
        .split``                        //convert to array
        .reduce((p,c)=>p.length-1?[p.join(c)]:[p[0],c],[''])
                                        //swap all numbers
)

J, 20 bytes

4#.0 2 1 3{~4#.^:_1]

Uso

>> f =: 4#.0 2 1 3{~4#.^:_1]
>> f 85
<< 170

Donde >>es STDIN y <<es STDOUT.

Sin golf

to_base   =: 4 #.^:_1 ]
transpose =: 0 2 1 3 {~ to_base
from_base =: 4 #. transpose

Tres tenedores

Nota al margen

En el intérprete oficial, ^:_1puede ser reemplazado porinv , guardando 1 byte.

Sin embargo, ninguno de los intérpretes en línea implementa esto.

C #, 44 bytes

Basado en la implementación de C

int f(int n)=>n>3?4*f(n/4)+f(n%4):n%2*2+n/2;

Pruébelo aquí: C # pad

INTERCAL , 60 bytes

DOWRITEIN.1PLEASE.1<-!1~#21845'$.1~#43690DOREADOUT.1DOGIVEUP

Pruébalo en línea!

Funciona para enteros de 16 bits, con E / S realizada en el formato más natural para INTERCAL: la entrada es una serie de dígitos decimales enunciados en uno de varios idiomas naturales o construidos, y la salida está en "números romanos descifrados".

Este es uno de esos desafíos raros en los que los operadores binarios de INTERCAL pueden usarse de manera intuitiva, ya que de lo que se trata es de reposicionar bits. Select ( ~) toma los bits de su primer argumento correspondiente a unos en su segundo argumento y los rellena a la derecha con ceros, y mingle ( $) intercala los bits de sus argumentos de modo que los bits del primer argumento sean más significativos. Entonces, la solución directa es seleccionar los bits alternos menos significativos ( .1~#21845), seleccionar los bits alternos más significativos (.1~#43690 ), y los vuelve a unir en el orden opuesto. Afortunadamente para el recuento de bytes, aunque los operadores de INTERCAL no tienen una prioridad definida (ya que el objetivo del lenguaje es no tener precedentes), resulta que C-INTERCAL en TIO no requiere mucha agrupación para esta expresión en particular, ya que solo cuesta un byte desde '.se pueden abreviar !.

Con soporte para enteros de 32 bits:

INTERCAL , 67 bytes

DOWRITEIN:1PLEASE:1<-':1~#0$#65535'$:1~#65535$#0DOREADOUT:1DOGIVEUP

Pruébalo en línea!

INTERCAL no permite literales de 32 bits, lo que en realidad hace que esto sea un poco más fácil de leer, ya que significa que las constantes mágicas para seleccionar bits alternos deben construirse mezclando dos literales de 16 bits, donde uno es todos ceros y el otro todos unos (En realidad, incluso si hubiera literales de 32 bits, esto aún sería más corto. #0$#65535Está a dos bytes de distancia #1431655765, y lo mismo ocurre con el otro.) Esto comunica todo el proceso de forma poco natural para INTERCAL.

Un enfoque alternativo con el uso torpe de la sobrecarga de operandos :

INTERCAL , 71 bytes

DO:1<-:1/.2$.3PLEASEWRITEIN:2DO:1<-:2PLEASE:2<-.3$.2DOREADOUT:2DOGIVEUP

Pruébalo en línea!

Esto elimina la selección por completo declarando que :1se .2mezcla con .3, configurando :1la entrada y luego emitiendo .3con .2. Como :1se sobrecargó como .2$.3, DO :1 <- :2asigna valores a .2y de .3tal forma que :1adquiere el valor de :2, lo que da como resultado que .2contenga los bits alternos más significativos :2y .3los bits alternos menos significativos. Esta sería la más corta de las dos soluciones de 32 bits en cuatro bytes si PLEASE WRITE IN :1pudiera reemplazarse PLEASE WRITE IN :2 DO :1 <- :2por sobrecargada :1, peroCALCULATINGResulta necesario para utilizar la sobrecarga. También siento que podría haber una forma más corta de llevar a cabo la sobrecarga en sí que comenzar el programa DO:1<-:1/.2$.3, pero como esto es INTERCAL, también siento que no puede haberlo.

Mathematica, 44 bytes

Fold[3#+##&,#~IntegerDigits~4/.{1->2,2->1}]&

El mismo enfoque que mi respuesta CJam: convertir a base-4, intercambiar 1s y 2s, convertir de nuevo. También utiliza el truco de alephalpha para reemplazar FromDigitscon una Foldoperación para guardar un byte.

En realidad, 16 bytes

4@¡"21""12"(t4@¿

Pruébalo en línea!

Explicación:

4@¡"21""12"(t4@¿
4@¡               base 4 representation of n
   "21""12"(t     translate (swap 1s and 2s)
             4@¿  base 4 to decimal

J, 22 bytes

([:,_2|.\,&0)&.(|.@#:)

Enfoque alternativo basado en la manipulación de la matriz en lugar del truco base 4.

Uso

   f =: ([:,_2|.\,&0)&.(|.@#:)
   (,.f"0) 0 1 9 85 220 1827 47525
    0     0
    1     2
    9     6
   85   170
  220   236
 1827  2835
47525 30298

Explicación

([:,_2|.\,&0)&.(|.@#:)  Input: n
                   #:   Get the value as a list of base 2 digits
                |.@     Reverse it
(           )&.         Apply to the list of base 2 digits
         ,&0            Append a zero to the end of the list
    _2  \               Split the list into nonoverlapping sublists of size 2
      |.                Reverse each sublist
 [:,                    Flatten the list of sublists into a list
             &.(    )   Apply the inverse of (reversed base 2 digits)
                        to convert back to a number and return it

REXX, 88 bytes

n=x2b(d2x(arg(1)))
o=0
do while n>''
  parse var n a+1 b+1 n
  o=o||b||a
  end
say x2d(b2x(o))