Opis zadania

Biorąc pod uwagę liczbę całkowitą, zamień jej (2k – 1) -ty i 2k- najmniej znaczący bit dla wszystkich liczb całkowitych k> 0 . Jest to sekwencja A057300 w OEIS.

(Zakłada się, że liczba ma „nieskończenie wiele” zer wiodących. W praktyce oznacza to po prostu wstawienie pojedynczego bitu 0 do liczb nieparzystych).

To jest golf golfowy , więc wygrywa najkrótszy kod (w bajtach).

Przypadki testowe

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

Galaretka , 10 9 7 bajtów

b4d2UFḄ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

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 bajtów

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

Triki!

Say nma formę ...ghfedcbabinarną. Następnie możemy podzielić go na każdy inny kawałek jako

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

Następnie wynik z przełączaniem bitów smożna wyrazić jako s=2*o+e.

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

Wolimy obliczyć tylko jeden ei otak możemy wyrazić o=n-2*ei substytutem

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

Tak więc teraz pozostaje wyrazić ew kategoriach n. Liczba M=4**n/3ma postać ...10101010101binarną, która służy jako maska ​​dla cyfr nieparzystych. Wykładnik nzapewnia, że Mjest wystarczająco długi. Biorąc bit andpo n/2i ta wartość daje ezgodnie z życzeniem.

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

Zamiast tego możemy wyrazić ew kategoriach o e=(n-o)/2, co daje s=(n+o*3)/2, co oszczędza bajt dzięki optymalizacji z xsot.

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

Funkcja C, 38

Kręcenie bitów:

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

Ideone.

Lub dla zabawy:

Funkcja rekurencyjna C, 43

Zgodnie z wzorem 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;}

lub

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

Ideone.

CJam, 16 14 13 bajtów

ri4b4e!2=f=4b

Sprawdź to tutaj.

Wyjaśnienie

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 bajtów

iXjQ4S2)4

Wypróbuj w kompilatorze Pyth .

Jak to działa

  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 bajtów

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

Działa tylko do 1073741823 ze względu na ograniczenia liczb całkowitych JavaScript. 38 36 bajtów działa do 4294967295:

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

Edycja: Zapisano 2 bajty dzięki @ user81655.

51 bajtów działa do 4503599627370495:

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

Funkcja asm x86: 14 bajtów kodu maszynowego

wersja uint64_t: 24 bajty

Konwencja wywoływania SysV x86-64 ( xin edi), ale ten sam kod maszynowy będzie również działał w trybie 32-bitowym. (Gdzie leadekoduje jako lea eax, [edi + eax*2], co daje identyczne wyniki ).

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 bajtów

Jest to wynik kompilatora wynikający z zastosowania doskonałej idei maski xnor - kiedyś w odwrotny sposób. (I przeciwna terminologia: niski bit to bit 0, który jest parzysty, a nie nieparzysty.)

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

Nie znalazłem żadnych ulepszeń w stosunku do kompilatora. Mógłbym napisać to jako mov eax, 0x555.../ and eax, edi, ale to ta sama długość.

Ta sama funkcja dla liczb całkowitych 64-bitowych zajmuje 24 bajty (patrz łącze godbolt). Nie widzę krótszego niż 10 bajtów sposobu movabs rax, 0x55...na wygenerowanie maski w rejestrze. ( divinstrukcja x86 jest nieporęczna, więc niepodpisany podział wszystkich przez 3 nie pomaga).

Wymyśliłem pętlę, aby wygenerować maskę w rax, ale ma ona 10 bajtów (dokładnie takiej samej długości jak 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
   ...

Gdybyśmy wiedzieli, że żaden z istniejących bajtów raxnie ma ustawionego niskiego bitu, moglibyśmy pominąć ten xor, a miałby on długość 8 bajtów.

Poprzednia wersja tej odpowiedzi miała 10-bajtową pętlę używającą loopinsn, ale miała najgorszy czas wykonywania 0xFFFFFFFFFFFFFF08iteracji, ponieważ ja tylko ustawiłem cl.

Oaza , 17 bajtów (niekonkurujące)

n4÷axxn4÷xxe+3120

Wypróbuj online!

Oasis to język zaprojektowany przez Adnana, który specjalizuje się w sekwencjach.

Obecnie ten język może wykonywać rekurencję i formę zamkniętą.

Używamy tej formuły: a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

Określenie podstawowego przypadku jest proste: 3120na końcu oznacza to po prostu 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 bajtów

BP2eP1ePXB

Wypróbuj online!

Zmodyfikowana wersja, aby wygenerować pierwsze warunki sekwencji ( OEIS A057300 ).

Wyjaśnienie

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 bajtów

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

Pobiera dane wejściowe jako argument wiersza poleceń, dane wyjściowe w STDOUT.

Nie jest kompatybilny z Bash, ponieważ wykorzystuje specyficzną dla Zsh podstawową składnię konwersji.

                       $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

Siatkówka, 70 bajtów

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

Zestaw testowy. (Lekko zmieniony.)

Cóż, dla zabawy: 7 bajtów

T`12`21

Pobiera base-4 jako wejście, a wyjścia jako base-4.

Wypróbuj online!

05AB1E, 8 bajtów

4B12‡4ö

Dzięki @Adnan za -5 bajtów!

Wykorzystuje kodowanie CP-1252.

Wypróbuj online!

Wyjaśnienie:

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 bajtów

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 +

Algorytm skopiowany z komentarza xsot do odpowiedzi xnor na Python . Zamiast maskować w obie strony, zamaskuj w jedną stronę i połącz.

Ten gromadzi do tego samego ASM jako ostatniej wersji testowanej ja , i to działa (za x do 0x3FFFFFFFi dla x powyższego, że tak długo, jak bit 30 nie jest ustawiony, patrz poniżej). W kodzie maszynowym ma taką samą długość jak moja istniejąca odpowiedź asm.

Powyższa wersja zawsze usuwa wysoki wynik wyniku . Najlepsza bezpieczna wersja to 32 bajty:

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

Wersja Python nie ma tego problemu, ponieważ python używa w razie potrzeby typów liczb całkowitych o dowolnej precyzji , zamiast obcinania do ustalonego górnego limitu.

JavaScript (ES6), 113 109 bajtów

Zaoszczędź 4 bajty dzięki Upgoat

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

Jak to działa

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 bajtów

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

Stosowanie

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

Gdzie >>jest STDIN i <<STDOUT.

Nie golfił

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

Trzy widelce.

Dygresja

W oficjalnym tłumaczu ^:_1można go zastąpić inv, oszczędzając 1 bajt.

Jednak żaden z tłumaczy internetowych tego nie wdraża.

C #, 44 bajty

Na podstawie implementacji C.

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

Wypróbuj tutaj: C # pad

INTERCAL , 60 bajtów

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

Wypróbuj online!

Działa dla 16-bitowych liczb całkowitych, a operacje we / wy są wykonywane w najbardziej naturalnym formacie dla INTERCAL: dane wejściowe to seria cyfr dziesiętnych wypisanych w jednym z kilku języków naturalnych lub skonstruowanych, a dane wyjściowe są zapisane w „rzeźbionych cyfrach rzymskich”.

Jest to jedno z tych rzadkich wyzwań, w których operatory binarne INTERCAL mogą faktycznie być używane w ogóle intuicyjnie, ponieważ chodzi o repozycjonowanie bitów. Select ( ~) pobiera bity z pierwszego argumentu odpowiadającego jedynkom w drugim argumencie i dopełnia je zerami w prawo, a mingle ( $) przeplata bity z argumentów tak, że bity z pierwszego argumentu są bardziej znaczące. Zatem prostym rozwiązaniem jest wybranie mniej znaczących przemiennych bitów ( .1~#21845), wybranie bardziej znaczących przemiennych bitów (.1~#43690) i przeplataj je z powrotem w odwrotnej kolejności. Na szczęście dla liczby bajtów, chociaż operatory INTERCAL nie mają zdefiniowanego pierwszeństwa (ponieważ celem języka jest brak precedensów), okazuje się, że C-INTERCAL na TIO nie wymaga dużego grupowania dla tego konkretnego wyrażenia, kosztując tylko jeden bajt od tego czasu '.można skrócić !.

Z obsługą 32-bitowych liczb całkowitych:

INTERCAL , 67 bajtów

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

Wypróbuj online!

INTERCAL nie dopuszcza 32-bitowych literałów, co w rzeczywistości sprawia, że ​​jest to trochę łatwiejsze do odczytania, ponieważ oznacza to, że magiczne stałe do wybierania przemiennych bitów muszą być skonstruowane przez zmieszanie dwóch 16-bitowych literałów razem, gdzie wszystkie są zerami i drugimi wszyscy (W rzeczywistości, nawet gdyby były 32-bitowe literały, byłoby to jeszcze krótsze. Ma #0$#65535dwa bajty wyłączone #1431655765, i to samo dotyczy drugiego.) To komunikuje cały proces nienaturalnie dobrze dla INTERCAL.

Alternatywne podejście z niezdarnym użyciem przeciążania operandów :

INTERCAL , 71 bajtów

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

Wypróbuj online!

To eliminuje wybierając zupełnie oświadczając, że :1jest .2zmieszany z .3ustawienie :1do wejścia, a następnie wyprowadzania .3zaprawione .2. Ponieważ :1został przeciążony jako .2$.3, DO :1 <- :2przypisuje wartości .2i .3takie, które :1uzyskują wartość :2, co powoduje, że .2zawierają bardziej znaczące przemienne bity :2i .3zawierają mniej znaczące przemienne bity. Byłby to krótszy z dwóch 32-bitowych rozwiązań o cztery bajty, gdyby PLEASE WRITE IN :1mógł zostać zastąpiony PLEASE WRITE IN :2 DO :1 <- :2przeciążeniem :1, aleCALCULATINGokazuje się konieczne do zastosowania przeciążenia. Wydaje mi się również, że może istnieć krótszy sposób na samodzielne przeładowanie niż uruchomienie programu DO:1<-:1/.2$.3, ale ponieważ jest to INTERCAL, również czuję, że nie może być.

Mathematica, 44 bajty

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

Takie samo podejście jak w mojej odpowiedzi CJam: konwersja do base-4, zamiana 1s i 2s, konwersja z powrotem. Wykorzystuje również trik alephalpha do zastąpienia FromDigitsz Foldpracy, aby zapisać jeden bajt.

Właściwie 16 bajtów

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

Wypróbuj online!

Wyjaśnienie:

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 bajty

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

Alternatywne podejście oparte na manipulacji tablicą zamiast sztuczki bazowej 4.

Stosowanie

   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

Wyjaśnienie

([:,_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 bajtów

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