Deskripsi tugas

Mengingat integer, menukar nya (2k-1) -th dan 2k -th setidaknya bit signifikan untuk semua bilangan bulat k> 0 . Ini adalah urutan A057300 dalam OEIS.

(Angka ini diasumsikan memiliki angka nol terkemuka “tak terhingga banyaknya”. Dalam praktiknya, ini berarti hanya menambahkan 0 bit ke angka ganjil.)

Ini adalah kode-golf , jadi kode terpendek (dalam byte) menang.

Uji kasus

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

Jelly , 10 9 7 byte

b4d2UFḄ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

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 byte

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

Trik bit!

Say nmemiliki bentuk ...ghfedcbadalam biner. Kemudian, kita dapat membaginya menjadi setiap bit sebagai

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

Kemudian, hasil bit-switched sdapat dinyatakan sebagai s=2*o+e.

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

Kami lebih suka menghitung hanya satu dari edan o, jadi kami mengekspresikan o=n-2*edan mengganti

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

Jadi, sekarang tetap untuk mengekspresikan edalam hal n. Nomor tersebut M=4**n/3memiliki bentuk ...10101010101dalam biner, yang berfungsi sebagai topeng untuk digit aneh. Eksponen nmemastikan itu Mcukup lama. Mengambil bitwise anddari n/2dan nilai ini memberi eseperti yang diinginkan.

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

Sebagai gantinya, kita dapat mengekspresikan edalam hal o e=(n-o)/2, yang memberi s=(n+o*3)/2, yang menyimpan byte berkat optimasi dari xsot.

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

Fungsi C, 38

Sedikit-twiddling:

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

Ideone.

Atau untuk bersenang-senang:

Fungsi rekursif C, 43

Sesuai formula 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;}

atau

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

Ideone.

CJam, 16 14 13 byte

ri4b4e!2=f=4b

Uji di sini.

Penjelasan

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 byte

iXjQ4S2)4

Cobalah di Pyth Compiler .

Bagaimana itu bekerja

  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 byte

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

Hanya berfungsi hingga 1073741823 karena keterbatasan bilangan bulat JavaScript. 38 36 byte bekerja hingga 4294967295:

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

Sunting: Disimpan 2 byte berkat @ user81655.

51 byte bekerja hingga 4503599627370495:

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

Fungsi as86 x86: 14 byte kode mesin

versi uint64_t: 24 byte

x86-64 SysV calling convention ( xin edi), tetapi kode mesin yang sama ini juga akan berfungsi dalam mode 32bit. (Di mana leaakan memecahkan kode sebagai lea eax, [edi + eax*2], yang memberikan hasil yang identik ).

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 byte

Ini adalah keluaran kompiler dari penggunaan ide topeng-sekali xnor yang sangat baik sebaliknya. (Dan terminologi yang berlawanan: bit rendah adalah bit 0, yang genap, tidak aneh.)

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

Saya tidak menemukan perbaikan apa pun yang dilakukan oleh kompiler. Saya mungkin menulisnya sebagai mov eax, 0x555.../ and eax, edi, tapi itu panjangnya sama.

Fungsi yang sama untuk integer 64bit membutuhkan 24 byte (lihat tautan godbolt). Saya tidak melihat cara yang lebih pendek dari 10-byte movabs rax, 0x55...untuk menghasilkan topeng dalam register. ( divInstruksi x86 adalah kikuk, sehingga pembagian yang tidak ditandatangani oleh semua oleh 3 tidak membantu)

Saya memang datang dengan loop untuk menghasilkan topeng di rax, tapi 10 byte (panjangnya persis sama dengan 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
   ...

Jika kita tahu bahwa tidak ada byte yang ada dalam raxset bit yang rendah, kita bisa melewatkan xor, dan ini akan menjadi 8 byte.

Versi sebelumnya dari jawaban ini memiliki loop 10 byte menggunakan loopinsn, tetapi memiliki 0xFFFFFFFFFFFFFF08iterasi run-time terburuk , karena saya hanya mengatur cl.

Oasis , 17 byte (tidak bersaing)

n4÷axxn4÷xxe+3120

Cobalah online!

Oasis adalah bahasa yang dirancang oleh Adnan yang memiliki spesialisasi dalam urutan.

Saat ini, bahasa ini dapat melakukan rekursi dan formulir tertutup.

Kami menggunakan rumus ini: a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

Untuk menentukan kasus dasar sederhana: 3120pada akhirnya berarti begitu 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 byte

BP2eP1ePXB

Cobalah online!

Versi yang dimodifikasi untuk menghasilkan ketentuan urutan pertama ( OEIS A057300 ).

Penjelasan

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 byte

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

Mengambil input sebagai argumen baris perintah, menghasilkan pada STDOUT.

Ini tidak kompatibel dengan Bash karena menggunakan sintaks konversi basis spesifik 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 byte

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

Suite uji. (Sedikit dimodifikasi.)

Nah, hanya untuk bersenang-senang: 7 byte

T`12`21

Mengambil basis-4 sebagai input, dan output sebagai basis-4.

Cobalah online!

05AB1E, 8 byte

4B12‡4ö

Terima kasih kepada @Adnan untuk -5 byte!

Menggunakan pengodean CP-1252.

Cobalah secara Online!

Penjelasan:

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 byte

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 +

Algoritma disalin dari komentar xsot pada jawaban Python xnor . Alih-alih menutupi kedua cara, tutupi satu cara dan kombinasikan.

Ini mengkompilasi ke asm yang sama dengan versi terakhir yang saya uji , dan itu berfungsi (untuk x hingga 0x3FFFFFFF, dan untuk x di atas selama bit 30 tidak diatur, lihat di bawah). Dalam kode mesin, panjangnya sama dengan jawaban asm saya yang ada.

Versi di atas selalu membersihkan bit tinggi hasilnya . Versi aman terbaik adalah 32 byte:

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

Versi Python tidak memiliki masalah ini, karena python menggunakan tipe integer presisi sewenang-wenang ketika diperlukan , alih-alih memotong ke batas atas tetap.

Javascript (ES6), 113 109 byte

Disimpan 4 byte berkat Upgoat

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

Bagaimana itu bekerja

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 byte

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

Pemakaian

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

Di mana >>STDIN dan <<STDOUT.

Tidak disatukan

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

Tiga garpu.

Sidenote

Dalam juru bahasa resmi, ^:_1bisa diganti dengan inv, menghemat 1 byte.

Namun, tidak ada penerjemah online yang menerapkan ini.

C #, 44 byte

Berdasarkan implementasi C

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

Coba di sini: C # pad

INTERCAL , 60 byte

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

Cobalah online!

Bekerja untuk bilangan bulat 16-bit, dengan I / O dilakukan dalam format paling alami untuk INTERCAL: input adalah serangkaian angka desimal yang dijabarkan dalam salah satu dari beberapa bahasa alami atau bahasa yang dikonstruksi, dan hasilnya dalam "angka Romawi yang dibantai".

Ini adalah salah satu tantangan yang jarang terjadi di mana operator biner INTERCAL benar-benar dapat digunakan sama sekali secara intuitif, karena reposisi bit adalah hal yang sebenarnya. Select ( ~) mengambil bit dari argumen pertama sesuai dengan yang ada di argumen kedua dan membalutnya ke kanan dengan nol, dan bergaul ( $) menyisipkan bit dari argumennya sehingga bit dari argumen pertama lebih signifikan. Jadi solusi langsungnya adalah memilih bit-bit alternating yang kurang signifikan ( .1~#21845), pilih bit-bit alternating yang lebih signifikan ().1~#43690), dan interleave mereka kembali bersama dalam urutan yang berlawanan. Untungnya untuk jumlah byte, meskipun operator INTERCAL tidak memiliki prioritas yang ditentukan (karena tujuan bahasa adalah untuk tidak memiliki preseden), ternyata C-INTERCAL pada TIO tidak memerlukan banyak pengelompokan untuk ekspresi khusus ini, hanya berharga satu byte sejak '.bisa disingkat !.

Dengan dukungan untuk bilangan bulat 32-bit:

INTERCAL , 67 byte

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

Cobalah online!

INTERCAL tidak mengizinkan literal 32-bit, yang sebenarnya membuat ini sedikit lebih mudah dibaca, karena itu berarti konstanta ajaib untuk memilih bit-bit bolak-balik harus dibangun dengan menyatukan dua literal 16-bit secara bersamaan, di mana yang satu nol dan nol semua itu. (Sebenarnya, bahkan jika ada literal 32-bit, ini masih akan lebih pendek.#0$#65535 Adalah dua byte #1431655765, dan yang sama berlaku untuk yang lain.) Ini mengkomunikasikan seluruh proses secara tidak wajar baik untuk INTERCAL.

Pendekatan alternatif dengan penggunaan operand yang canggung :

INTERCAL , 71 byte

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

Cobalah online!

Ini tidak jauh dengan memilih sama sekali dengan menyatakan bahwa :1yang .2bercampur dengan .3, pengaturan :1untuk input, kemudian keluaran .3bercampur dengan .2. Karena :1kelebihan beban sebagai .2$.3, DO :1 <- :2memberikan nilai ke .2dan .3sehingga :1memperoleh nilai :2, yang menghasilkan .2mengandung bit bolak-balik yang lebih signifikan dari :2dan .3mengandung bit bolak -balik yang kurang signifikan. Ini akan menjadi lebih pendek dari dua solusi 32-bit dengan empat byte jika PLEASE WRITE IN :1bisa diganti PLEASE WRITE IN :2 DO :1 <- :2dengan kelebihan beban :1, tetapiCALCULATINGternyata diperlukan untuk menggunakan kelebihan beban. Saya juga merasa mungkin ada cara yang lebih singkat untuk melakukan overload itu sendiri daripada memulai program DO:1<-:1/.2$.3, tetapi karena ini INTERCAL saya juga merasa tidak mungkin ada.

Mathematica, 44 byte

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

Pendekatan yang sama seperti jawaban CJam saya: convert to base-4, swap 1s and 2s, convert back. Ini juga menggunakan trik alephalpha untuk menggantikan FromDigitsdengan Foldoperasi untuk menghemat satu byte.

Sebenarnya, 16 byte

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

Cobalah online!

Penjelasan:

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 byte

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

Pendekatan alternatif didasarkan pada manipulasi array daripada trik basis 4.

Pemakaian

   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

Penjelasan

([:,_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 byte

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