pengantar

Tantangan ini mengharuskan Anda untuk mengatur nol trailing dari representasi biner bilangan bulat 010101…, ini paling baik dijelaskan dengan contoh:

Dengan bilangan bulat 400, langkah pertama adalah mengubahnya menjadi biner:

110010000

Seperti yang dapat kita lihat bit kelima adalah bit yang paling tidak signifikan 1, jadi mulai dari sana kita ganti nol yang lebih rendah dengan 0101:

110010101

Akhirnya kami mengonversi itu kembali ke desimal: 405

Tantangan

Diberikan pengembalian integer positif / output nilai hasil yang sesuai dari proses yang didefinisikan di atas.

Aturan

• Urutan ini hanya didefinisikan untuk bilangan bulat dengan setidaknya satu 1bit, sehingga input akan selalu ≥ 1
• Anda dapat mengambil input sebagai string, daftar digit (desimal) sebagai gantinya
• Anda tidak harus menangani input yang tidak valid

Testcases

Berikut adalah beberapa testcases dengan langkah perantara (Anda tidak harus mencetak / mengembalikannya):

In -> … -> … -> Out
1 -> 1 -> 1 -> 1
2 -> 10 -> 10 -> 2
3 -> 11 -> 11 -> 3
4 -> 100 -> 101 -> 5
24 -> 11000 -> 11010 -> 26
29 -> 11101 -> 11101 -> 29
32 -> 100000 -> 101010 -> 42
192 -> 11000000 -> 11010101 -> 213
400 -> 110010000 -> 110010101 -> 405
298 -> 100101010 -> 100101010 -> 298

Python 3 , 20 byte

lambda n:(n&-n)//3+n

Cobalah online!

Penjelasan

Ambil 192sebagai contoh. Bentuk binernya adalah 11000000, dan kita perlu mengubahnya 11010101.

Kami mencatat bahwa kami perlu menambahkan 10101nomornya. Ini adalah deret geometri ( 4^0 + 4^1 + 4^2), yang memiliki bentuk tertutup sebagai (4^3-1)/(4-1). Ini sama dengan di 4^3//3mana //menunjukkan pembagian integer.

Jika ya 101010, maka masih akan menjadi deret geometri ( 2×4^0 + 2×4^1 + 2×4^2), yang 2×4^3//3karena alasan di atas.

Bagaimanapun, 4^3dan 2×4^3hanya akan menjadi bagian yang paling tidak penting, yang kami peroleh dengan n&-n:

Kami memperhatikan bahwa komplemen dari nis 00111111. Jika kita menambahkan satu, itu menjadi 01000000, dan itu hanya tumpang tindih dengan n=11000000digit paling tidak signifikan. Perhatikan bahwa "melengkapi dan menambahkan satu" hanyalah negasi.

Jelly , 5 byte

&N:3+

Cobalah online!

Kali ini port pendekatan Leaky Nun (setidaknya aku membantunya sedikit menurunkan golf: P)

Jelly , 7 byte

^N+4:6ạ

Cobalah online!

Menggunakan pendekatan Jung Jung Min yang fantastis , dengan bantuan tidak langsung dari Martin Ender .

Bahasa Wolfram (Mathematica) , 36 28 26 24 byte

^{-8 byte terima kasih kepada @MartinEnder dan -2 byte terima kasih kepada @ Mr.Xcoder}

#+⌊(#~BitAnd~-#)/3⌋&

Cobalah online!

Kita hanya perlu menemukan jumlah nol trailing di input, dan menemukan nomor dengan 0s dan 1s dengan panjang satu kurang dari itu, dan menambahkannya ke input.

Begitu, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

Rumus eksplisit untuk nnomor th dengan alternating 1s dan 0s diberikan pada A000975 pada OEIS. Kita dapat menggunakan angka nth karena tidak ada dua angka berbeda yang dapat memiliki panjang yang sama dalam biner dan memiliki digit bergantian.

J , ₁₉ 18 byte

+(2|-.i.@#.-.)&.#:

Cobalah online!

Penjelasan Cepat

Ini adalah jawaban lama, tetapi sifatnya sangat mirip dengan yang saat ini, ia hanya menghitung nol trailing secara berbeda. Lihat komentar untuk tautan yang menjelaskan cara kerjanya.

+(2|i.@i.&1@|.)&.#:
                 #:  Convert to binary list
       i.&1@|.       Index of last 1 from right
            |.         Reverse
       i.&1            Index of first 1
    i.               Range [0, index of last 1 from right)
  2|                 That range mod 2
               &.    Convert back to decimal number
+                    Add to the input

Jawaban Lain:

Jawaban sebelumnya (19 byte).

+(2|i.@i.&1@|.)&.#:

Lebih lama dari seharusnya karena \belok kanan ke kiri.

+(2|#*-.#.-.)\&.(|.@#:)

Julia 0,6 , 12 byte

!n=n|n&-n÷3

Cobalah online!

JavaScript (ES6), 40 39 byte

Mengambil input sebagai integer 32-bit.

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

Uji kasus

let f =

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

console.log(f(1))   // 1 -> 1 -> 1
console.log(f(2))   // 10 -> 10 -> 2
console.log(f(3))   // 11 -> 11 -> 3
console.log(f(4))   // 100 -> 101 -> 5
console.log(f(24))  // 11000 -> 11010 -> 26
console.log(f(29))  // 11101 -> 11101 -> 29
console.log(f(32))  // 100000 -> 101010 -> 42
console.log(f(192)) // 11000000 -> 11010101 -> 213
console.log(f(400)) // 110010000 -> 110010101 -> 405
console.log(f(298)) // 100101010 -> 100101010 -> 298

05AB1E , 13 8 5 byte

Disimpan 5 byte berkat Tn. Xcoder dan formula rapi JungHwan Min.
Menyimpan 3 byte lainnya berkat Tn. Xcoder

(&3÷+

Cobalah online!

Penjelasan

(      # negate input
 &     # AND with input
  3÷   # integer divide by 3
    +  # add to input

R , 71 58 byte

terima kasih kepada NofP untuk -6 byte

function(n){n=n%/%(x=2^(0:31))%%2
n[!cumsum(n)]=1:0
n%*%x}

Cobalah online!

Mengasumsikan input adalah integer 32-bit. R hanya telah menandatangani bilangan bulat 32-bit (tetap ke doublesaat bilangan bulat melimpah) dan tidak ada 64-bit atau int yang tidak ditandatangani.

brainfuck , 120 byte

>+<[[>-]++>[[>]>]<[>+>]<[<]>-]>[-<+>[-<[<]<]>]>[>]<[>+<[->+<]<[->+<]<]>>[<]+>[-[-<[->+<<+>]>[-<+>]]<[->++<]<[->+<]>>>]<<

Cobalah secara Online!

Mulai dengan nilai di sel saat ini dan berakhir di sel dengan nilai output. Jelas tidak akan berfungsi pada angka di atas 255 karena itulah batas sel untuk tipuan otak tipikal, tetapi akan berfungsi jika Anda menganggap ukuran sel tak terbatas.

PowerShell , 168 byte

param($n)$a=($c=[convert])::ToString($n,2);if(($x=[regex]::Match($a,'0+$').index)-gt0){$c::ToInt32(-join($a[0..($x-1)]+($a[$x..$a.length]|%{(0,1)[$i++%2]})),2)}else{$n}

Cobalah online!

Aduh. Konversi ke / dari pemotongan biner dan array tidak benar-benar sesuai dengan PowerShell.

Mengambil input $nsebagai angka. Kami segera melakukan convertitu ke basis biner 2dan menyimpannya ke dalam $a. Selanjutnya kita memiliki konstruksi if / else. Klausa if menguji apakah a regex Matchterhadap 1 atau lebih 0s pada akhir string ( '0+$') memiliki lokasinya indexdi lebih besar dari 0(yaitu, mulai dari string biner). Jika ya, kami memiliki sesuatu untuk dikerjakan, elsekami hanya menampilkan angkanya.

Di dalam if, kami mengiris xdigit pertama, dan merangkai +-angka dengan digit yang tersisa. Namun, untuk digit yang tersisa, kami mengulanginya dan memilih salah satu 0atau 1sebagai keluaran, gunakan $i++%2untuk memilih. Ini memberi kita 010101...pola alih-alih 0di akhir. Kami kemudian -joinkembali bersama menjadi string, dan $cmengubahnya kembali menjadi Int32basis 2.

Dalam situasi apa pun, nomornya dibiarkan dalam pipa dan hasilnya tersirat.

APL + WIN, 43 byte

p←+/^\⌽~n←((⌊1+2⍟n)⍴2)⊤n←⎕⋄2⊥((-p)↓n),p⍴0 1

Meminta input layar

PowerShell , 41 36 byte

param($n)$n+(($x=$n-band-$n)-$x%3)/3

Cobalah online! atau Verifikasi semua kasus uji

Port of Leaky Nun's Python menjawab .

Disimpan 5 byte berkat Leaky Nun

PHP , 47 byte

<?php function b($a){echo(int)(($a&-$a)/3)+$a;}

Cobalah online!

Benar-benar hanya port lain dari solusi @Leaky Nun

Perl 5 , 54 byte

$_=sprintf'%b',<>;1while s/00(0*)$/01$1/;say oct"0b$_"

Cobalah online!

Python 3 , 56 byte

lambda n:eval((bin(n).rstrip("0")+"01"*n)[:len(bin(n))])

Cobalah online!

Belum benar-benar senang dengan ini, tapi saya benar-benar tidak ingin menggunakan formula ... -2 terima kasih kepada Rod . -1 terima kasih kepada Jonathan Frech .

Ruby , 15 byte

Pelabuhan lain dari pendekatan Leaky Nun.

->k{(k&-k)/3+k}

Cobalah online!

Karat , 18 byte

Pelabuhan pendekatan Leaky Nun

|n:i32|(n&-n)/3+n;

Cobalah online!

AWK , 24 byte

Port jawaban Mathmatica JungHwan Min

$0=int(and($0,-$0)/3+$0)

Cobalah online!

JavaScript ES6, 13 byte

n=>(n&-n)/3|n

f = 
n=>(n&-n)/3|n
;
console.log (f(8));
console.log (f(243));
console.log (f(1048576));
console.log (f(33554432));

C, 56 byte

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;return n|k;}

Cobalah online!

C (gcc), 50 byte

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;k|=n;}

Cobalah online!

 51  48 byte menggunakan solusi Arnauld :

Berkat @ l4m2 untuk menghemat tiga byte!

m;f(n){return n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Cobalah online!

43 dengan gcc:

m;f(n){m=n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Cobalah online!

Pari / GP , 19 byte

Pelabuhan pendekatan Leaky Nun.

n->n+bitand(n,-n)\3

Cobalah online!

Jelly , 13 byte

BŒgṪµ2Ḷṁ×CḄ+³

Cobalah online!

Penjelasan

Ambil 24 sebagai input contoh.

BŒgṪµ2Ḷṁ×CḄ+³
B                Binary representation of the input → 11000
 Œg              Group runs of equal length → [[1,1],[0,0,0]]
   Ṫ             Tail → [0,0,0]
    µ            New monadic link
     2Ḷ          [0,1] constant
       ṁ         Mold [0,1] to the shape of [0,0,0] → [0,1,0]
        ×        Multiply [0,1,0] by...
         C       1-[0,0,0]. If last bit(s) of the original input are 1 this will add nothing to the original input
          Ḅ      Convert to decimal from binary → 2
           +³    Add this with the original input → 26