Jumlah Integer Terdilusi

26

Integer positif dapat diencerkan dengan memasukkan 0antara dua bit dalam ekspansi binernya. Ini berarti bahwa nnomor-bit memiliki n-1pengenceran, yang tidak harus semuanya berbeda.

Misalnya, untuk 12(atau 1100dalam biner), pengencerannya

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

Dalam tantangan ini, kita akan mengambil jumlah semua pengenceran, tidak termasuk nomor aslinya. Untuk 12, dengan mengambil jumlah 24, 24, 20hasil 68, jadi 68harus menjadi output untuk 12.

Tantangan

Dengan bilangan bulat positif n > 1sebagai input, output / kembalikan jumlah yang dilusian seperti dijelaskan di atas.

Contohnya

in    out
---   ---
2       4
3       5
7      24
12     68
333  5128
512  9216

Aturan

  • Input dan output dapat dianggap sesuai dengan tipe integer asli bahasa Anda.
  • Input dan output dapat diberikan dalam format apa pun yang nyaman .
  • Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
AdmBorkBork
sumber
Apakah "ada format yang nyaman" termasuk string biner?
Shaggy
1
@Shaggy "Format praktis apa pun" dimaksudkan untuk mencakup metode input / output, bukan format . Dengan demikian, saya akan mengatakan tidak, Anda harus mengambil input sebagai integer atau string yang mewakili integer itu.
AdmBorkBork
Tantangan yang bagus!
Manish Kundu
1
Urutan ini saat ini (30 Jan 2018) tidak di OEIS
Giuseppe

Jawaban:

12

Python 2 , 43 39 byte

f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

Cobalah online!


Bagaimana?

Setiap panggilan fungsi rekursif menghitung pengenceran tunggal. Posisi yang dimasukkan 0adalah log2(i). Fungsi berulang hingga imenjadi lebih besar dari ndan penyisipan akan berada di sebelah kiri nomor tersebut. Jika i>n, n/imengevaluasi 0, yang merupakan nilai palsu dalam Python.

n*2menggeser seluruh angka satu digit biner ke kiri, n%iatau n % 2**(position of insertion)menghitung nilai bagian yang tidak boleh digeser ke kiri. Nilai ini akan dikurangkan dari angka yang digeser.

Contoh (n = 7)

call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0
ovs
sumber
7

Jelly , 11 byte

BJṖ2*ɓdḅḤ}S

Cobalah online!

Bagaimana itu bekerja

BJṖ2*ɓdḅḤ}S  Main link. Argument: n (integer)

B            Binary; convert n to base 2. This yields a digit array A.
 J           Indices; yield [1, ..., len(A)].
  Ṗ          Pop; remove the last element, yielding [1, 2, ..., len(A)-1].
   2*        Elevate 2 to these powers, yielding [2, 4, ..., 2**(len(A)-1)].
             Let's call the result B.
     ɓ       Begin a new, dyadic chain, with left argument n and right argument B.
      d      Divmod; yield [n/b, n%b], for each b in B.
        Ḥ}   Unhalve right; yield 2b for each b in B, i.e., [4, 8, ..., 2**len(A)].
       ḅ     Unbase; convert each [n/b, n%b] from base 2b to integer, yielding
             (2b)(n/b) + (n%b).
          S  Take the sum.
Dennis
sumber
5

MATL , 13 byte

tZl:W&\5ME*+s

Cobalah di MATL Online! Atau verifikasi semua kasus uji .

Penjelasan

Pertimbangkan input 12sebagai contoh.

t     % Implicit input. Duplicate
      % STACK: 12, 12
Zl    % Binary logarithm
      % STACK: 12, 3.584962500721156
:     % Range (rounds down)
      % STACK: 12, [1 2 3]
W     % Power with base 2, element-wise
      % STACK: 12, [2 4 8]
&\    % 2-output modulus, element-wise: pushes remainders and quotients
      % STACK: [0 0 4], [6 3 1]
5M    % Push array of powers of 2, again
      % STACK: [0 0 4], [6 3 1], [2 4 8]
E     % Multiply by 2
      % STACK: [0 0 4], [6 3 1], [4 8 16]
*     % Multiply, element-wise
      % STACK: [0 0 4], [24 24 16]
+     % Add, element-wise
      % STACK: [24 24 20]
s     % Sum of array. Implicit display
      % STACK: 68
Luis Mendo
sumber
4

C,  58  56 byte

Terima kasih kepada @Dennis karena telah menghemat dua byte!

s,k;f(n){for(s=0,k=2;k<=n;k*=2)s+=n/k*k*2+n%k;return s;}

Cobalah online!

C (gcc) , 50 byte

s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k+=k);k=s;}

Mengembalikan oleh k=s;adalah perilaku yang tidak terdefinisi, tetapi bekerja dengan gcc saat optimisasi dinonaktifkan. Juga, n%k+n/k*(k+=k)memiliki perilaku yang tidak ditentukan , tetapi tampaknya berfungsi baik dengan gcc.

Cobalah online!

Steadybox
sumber
s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k*=2);return s;}(55 byte)
Kevin Cruijssen
1
Tidak ada yang tahu mana yang dievaluasi terlebih dahulu n%katau n/k*(k*=2).
Steadybox
1
@KevinCruijssen Sisi mana yang dievaluasi terlebih dahulu tidak ditentukan. C seperti itu ...
Steadybox
2
Ah, saya tahu Anda sudah menambahkan itu dalam jawaban Anda. Tidak tahu perilaku tidak terdefinisi seperti ini terjadi di C. Saya punya pengalaman tiga jam di C, jadi saya hampir tidak tahu apa-apa tentang itu. TIL :) Di Jawa for(s=0,k=2;k<=n;)s+=n%k+n/k*(k*=2);return s;sepenuhnya baik-baik saja, dan n%kakan selalu dievaluasi sebelum n/k*(k*=2)dan n/kjuga akan dievaluasi sebelumnya k*=2. Terima kasih untuk penjelasannya. (Saya akan menghapus beberapa komentar saya sekarang untuk mengurangi kekacauan.)
Kevin Cruijssen
Saya suka menggunakan UB sebagai fitur. Dan golf kode dalam bahasa kehidupan nyata harus dalam kategori lain pula :)
Regis Portalez
4

Jelly , 9 8 byte

BḊḄÐƤạḤS

Cobalah online!

B                        to binary          42 -> 1 0 1 0 1 0
 Ḋ                       drop first                 0 1 0 1 0
  ḄÐƤ                    each suffix to decimal   10 10 2 2 0
      Ḥ                  double the input                  84
     ạ                   absolute difference   74 74 82 82 84
       S                 add them up                      396

Begitu juga sebaliknya B¹ƤṖ+BḄS,: dapatkan awalan, jatuhkan yang terakhir, tambahkan ke input, dan jumlah.

FrownyFrog
sumber
4

J , 20 15 14 byte

+/@}:@:+[\&.#:

Cobalah online.

15 byte

1#.-,+:-#.\.@#:

Cobalah online!

     +:             Input×2
       -            Subtract
        #.\.@#:     The list of binary suffixes of input (in decimal)
   -,               Append negative input
1#.                 Add them up
FrownyFrog
sumber
mengapa rumus minus ganda bekerja? mengapa itu setara dengan pengenceran?
Jonah
1
@Jonah pengenceran menambahkan awalan biner tertentu (angka "dibulatkan") ke nomor, yang setara dengan menambahkan seluruh nomor ke dirinya sendiri (baik awalan dan sisanya) dan kemudian mengurangi sisanya.
FrownyFrog
4

Japt , 12 11 byte

¢¬£¢iYTÃÅxÍ

Cobalah


Penjelasan

                 :Implicit input of integer U
¢                :Convert to base-2 string
 ¬               :Split to an array of individual characters/digits
  £    Ã         :Map over the elements, with Y being the current 0-based index
   ¢             :  Convert U to a base-2 string
    iYT          :  Insert a 0 in that string at index Y
        Å        :Slice off the first element of the array
          Í      :Convert each element to a base-10 integer
         x       :Reduce by addition
Shaggy
sumber
3

JavaScript (ES6), 41 40 byte

Disimpan 1 byte berkat Mr.Xcoder

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

Uji kasus

Arnauld
sumber
3

Retina , 53 50 47 byte

.+
*
+`(_+)\1
$1O
O_
_
L$`\B
$`O$'
+%`\B
¶$`¶
_

Cobalah online! Tautan termasuk kasus uji. Sunting: Disimpan 3 byte berkat @MartinEnder. Penjelasan:

.+
*
+`(_+)\1
$1O
O_
_

Konversi dari desimal ke biner, tetapi menggunakan O untuk merepresentasikan 0, karena itu bukan digit, dan _ untuk mewakili 1, karena itu adalah karakter pengulangan default di Retina 1.

L$`\B
$`O$'

Masukkan O di antara setiap pasangan digit, dan kumpulkan hasilnya sebagai daftar.

+%`\B
¶$`¶

Konversi dari biner ke unary. (Konversi ini menghasilkan ekstra O, tetapi kami tidak peduli.)

_

Jumlahkan dan konversikan ke desimal.

Neil
sumber
Konversi biner ke desimal dapat dilakukan dalam 12 byte (hemat 3): tio.run / ##K0otycxLNPz/... Lihat jawaban ini untuk cara kerjanya.
Martin Ender
@ MartinEnder Terima kasih, saya selalu lupa tentang itu. (Saya juga sedikit kecewa bahwa versi alternatif hanya bekerja pada satu nomor.)
Neil
Nah, dalam kasus di mana Anda memiliki masing-masing nomor pada jalurnya sendiri, Anda dapat membuatnya bekerja dengan tambahan %. Jika lebih rumit, Anda akan membutuhkan sesuatu seperti /[O_]+/_.
Martin Ender
2

Pyth , 13 byte

smiXd.BQZ2Ssl

Coba di sini!

Penjelasan

smiXd.BQZ2Ssl | Program lengkap.

           sl | Logaritma basis-2 dari input, dihubungkan ke integer.
          S | Buat rentang integer [1 ... logaritma lantai].
 m | Dan memetakan fungsi di atasnya.
------------ + - + ----------------------------------- ------------------
  iXd.BQZ2 | Fungsi yang akan dipetakan (menggunakan variabel d).
     .BQ | Dalam representasi biner dari input ...
   XZ | ... Masukkan nol ...
    d | ... Pada indeks d.
  saya 2 | Dan konversi hasilnya dari basis 2 ke integer.
------------ + - + ----------------------------------- ------------------
s | Jumlahkan daftar yang dihasilkan.
Tuan Xcoder
sumber
2

Jelly , 10 byte

BµLḤ_J’×µḄ

Cobalah online!

Bukan yang terpendek saat ini, tetapi bisa jadi jika ada jalan keluar Bµ µḄ...

Penjelasan

BµLḤ_J’×µḄ    Main link. Argument: n (integer)
B             Binary; convert n to an binary of binary digits. Call this A.
 µ            Start a new monadic link with argument A.
  L           Length; yield len(A). We'll call this l.
   Ḥ          Unhalve; yield l * 2.
     J        Length range; yield [1, 2, ..., l].
    _         Subtract; yield [l*2 - 1, l*2 - 2, ..., l].
      ’       Decrement; subtract one from each item.
       ×      Multiply each item by the corresponding item in A. Call this B.
        µ     Start a new monadic link with argument B.
         Ḅ    Unbinary; convert from a binary array to a decimal.

Pada dasarnya, ini bekerja dengan mengalikan setiap digit biner dengan angka ajaib. Saya tidak bisa menjelaskannya tanpa memvisualisasikannya, jadi inilah angka biner yang akan kami kerjakan:

1111

Seperti yang dijelaskan oleh tantangan, dia menampilkan yang kita inginkan adalah jumlah dari angka-angka biner ini:

10111  = 2^4 + 2^2 + 2^1 + 2^0
11011  = 2^4 + 2^3 + 2^1 + 2^0
11101  = 2^4 + 2^3 + 2^2 + 2^0

Namun, kita tidak benar-benar harus memasukkan angka nol: Atom "tidak biner" Jelly akan menerima nomor selain dari 0dan 1. Ketika kita membiarkan diri kita untuk menggunakan 2, pola ini menjadi lebih sederhana:

2111   = 2*2^3 + 1*2^2 + 1*2^1 + 1*2^0
2211   = 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0
2221   = 2*2^3 + 2*2^2 + 2*2^1 + 1*2^0

Ketika kita meringkas digit di setiap kolom, kita dapatkan

6543   = 6*2^3 + 5*2^2 + 4*2^1 + 3*2^0 = 48 + 20 + 8 + 3 = 79.

Trik yang digunakan jawaban ini adalah untuk menghasilkan pola ini, dan gandakan setiap digit dengan angka yang sesuai dalam aslinya untuk membatalkan kolom yang diperlukan. 12, misalnya, akan direpresentasikan sebagai

 1100
×6543
=6500  = 6*2^3 + 5*2^2 + 0*2^1 + 0*2^0 = 48 + 20 + 0 + 0 = 68.
Produksi ETH
sumber
1

Sekam , 13 12 byte

-1 byte terima kasih kepada @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

Cobalah online!

Penjelasan

ṁḋ§z·+Θḣ(tṫ)ḋ  -- example input: 6
            ḋ  -- convert to binary: [1,1,0]
  §            -- fork argument
        (tṫ)   -- | tail of tails: [[1,0],[0]]
       ḣ       -- | heads: [[1],[1,1],[1,1,0]]
   z           -- and zipWith the following (example with [1,0] [1])
    · Θ        -- | prepend 0 to second argument: [0,1]
     +         -- | concatenate: [1,0,0,1]
               -- : [[1,0,1,0],[1,1,0,0]]
ṁ              -- map the following (example with [1,0,1,0]) and sum
 ḋ             -- | convert from binary: 10
               -- : 22
ბიმო
sumber
1

Pip , 21 18 byte

2*a-a%2**_MS1,#TBa

Cobalah online!

Penjelasan

Hubungi nomor input kami a. Untuk setiap indeks biner idi mana kita ingin memasukkan nol, kita dapat menghitung bit yang tersisa dari titik penyisipan sebagai a // 2**i(di mana //adalah pembagian integer dan **eksponensial), bit kanan dari titik penyisipan sebagai a % 2**i, dan oleh karena itu bilangan bulat yang dilusi sebagai 2 * (a // 2**i) * 2**i + (a % 2**i). Tetapi (a // 2**i) * 2**isama dengan a - (a % 2**i), sehingga kita dapat mengatur ulang ke rumus yang lebih pendek: 2 * (a - a % 2**i) + a % 2**i= 2 * a - a % 2**i.

2*a-a%2**_MS1,#TBa
                       a is 1st command-line argument (implicit)
               TBa     Convert a to binary
              #        Length of the binary expansion
            1,         Range from 1 up to (but not including) that number
          MS           Map this function to the range and sum the results:
2*a-a%2**_              The above formula, where _ is the argument of the function
                       The final result is autoprinted
DLosc
sumber
1

R , 141 48 byte

function(n,l=2^(1:log2(n)))sum(n%%l+(n%/%l*2*l))

Cobalah online!

Entah saya melakukan sesuatu yang benar-benar salah atau R hanya mengerikan pada manipulasi bit. Pendekatan Porting Luis Mendo mudah, benar, dan golf.

Tetapi jika Anda benar-benar hanya ingin muck sekitar dengan operasi bit, MickyT menyarankan byter 105 berikut:

function(i)sum(sapply(1:max(which(b<-intToBits(i)>0)),function(x)packBits(head(append(b,F,x),-1),"i")))-i

Cobalah online!

Giuseppe
sumber
Berikut ini adalah byte 111 yang saya yakin Anda dapat mengambil beberapa lebih dari.
MickyT
@MickyT Cheers! sangat bagus, meskipun porting pendekatan yang sama sekali berbeda lebih baik!
Giuseppe
1

Python 3, 92 80 78 byte

def b(x):x=f'{x:b}';return sum(int(x[:i]+'0'+x[i:],2)for i in range(1,len(x)))

Cobalah secara Online

Terima kasih kepada Mr.XCoder dan ovs untuk masing-masing -12 byte dan -2 byte.

Manish Kundu
sumber
80 byte
Mr. Xcoder
1

Batch, 92 77 byte

@set/an=2,t=0
:l
@if %1 geq %n% set/at+=%1*2-(%1%%n),n*=2&goto l
@echo %t%

Sunting: Beralih ke rumus yang sama dengan yang digunakan orang lain.

Neil
sumber
0

Perl 5 , 36 +1 ( -p) = 37 byte

$\+=$_*2-($_&$.-1)while($.*=2)<=$_}{

Cobalah online!

Xcali
sumber
0

Attache , 57 byte

Sum##UnBin=>{Join[Join=>_,"0"]}=>SplitAt#1&`:@{#_-1}##Bin

Cobalah online!

Saya pikir saya akan mendekati masalah dari pendekatan manipulasi non-bit, karena pendekatan seperti itu tidak praktis di Attache. Saya harus menyelidiki beberapa bagian dari pendekatan ini sebagai alternatif.

Penjelasan

Ini adalah versi yang diperluas:

Define[$joinByZero, {Join[Join=>_,"0"]}]

Define[$insertionPoints,
    SplitAt#1&`:@{#_-1}
]

Define[$f,
Sum##UnBin=>joinByZero=>insertionPoints##Bin
]

Ini hanya mengambil representasi biner dari angka, membaginya pada titik-titik tertentu, memasukkan nol di sana, mengkonversi kembali ke desimal, dan menjumlahkannya bersama-sama.

Conor O'Brien
sumber
0

J , 33 byte

1#.[:}:#.@(<\;@(,0;])"0<@}.\.)@#:

Kemungkinan besar ada banyak ruang untuk bermain golf lebih lanjut.

Bagaimana?

@#: dikonversi ke biner dan

<@}.\. - temukan semua cukup, letakkan digit pertama dari masing-masing dan kotak

<\ - temukan semua awalan dan kotak mereka

(,0;])"0 - untuk setiap awalan, tambahkan 0 lalu tambahkan akhiran pemenggalan yang sesuai

;@ meruntuhkan (unbox)

1#.[:}:#.@ - Konversi ke desimal, kurung dan jumlah

Cobalah online!

Galen Ivanov
sumber