Tantangan ini sederhana, diberi angka desimal, dikonversi ke biner, dan hitung jumlah sub-string dari angka biner, yang panjangnya lebih pendek dari angka aslinya. Berikut ini sebuah contoh:

Input:
  11
Binary:
  11 -> 1011
Substrings:
  101 = 5
  011 = 3
  10  = 2
  01  = 1
  11  = 3
  1   = 1
  0   = 0
  1   = 1
  1   = 1
Sum:
  5+3+2+1+3+1+0+1+1=17
Output:
  17

Program Anda harus mengambil bilangan bulat desimal tunggal sebagai input dan output jumlah dari sub-string biner, seperti yang terlihat di atas. Anda dapat mengasumsikan input akan selalu memiliki lebih dari dua digit dalam representasi binernya dan bahwa input tidak akan menyebabkan kesalahan selama eksekusi program Anda.

Ini adalah kode-golf , kode terpendek dalam byte yang menang!

Kasus uji:

2  => 1
3  => 2
4  => 3
5  => 5
6  => 7
7  => 9
8  => 7
9  => 10
10 => 14
11 => 17

Jelly, 10 7 byte

BṡRḄFS_

Cobalah online!

Bagaimana itu bekerja

BṡRḄFS_  Main link. Input: n

B        Convert n to base 2.
  R      Yield [1, ..., n].
 ṡ       Get all overlapping slices of lengths 1 to n.
         This yields empty arrays if the slice size is longer than the binary list.
   Ḅ     Convert each binary list to integer.
    F    Flatten the resulting, nested list.
     S   Compute the sum of the result.
      _  Subtract n from the sum.

Pyth, 10

sPiR2.:.BQ

Cobalah secara online atau jalankan Test Suite

Penjelasan:

sPiR2.:.BQ    ##   Q = eval(input())
       .BQ    ##   get binary string of Q
     .:       ##   get all substrings of that
  iR2         ##   convert them all to base 10
sP            ##   sum all but the last element, which is the input number

CJam, 27 21 byte

Shoutout to Dennis karena telah membantu saya menghemat 6 byte!

q~:Q{)Q2bew2fb~}%1bQ-

Hanya berfungsi dengan versi terbaru CJam (tersedia di TIO). Cobalah online !

Versi lama:

qi2b_,,0-\f{ew}{{2b}%}%e_:+

Cobalah online .

Python 3, 111 karakter

N=bin(int(input()))[2:];L=len(N);r=range;print(sum(int(n,2)for n in[N[j:j+i]for i in r(1,L)for j in r(L-i+1)]))

EDIT : Penjelasan:

N=bin(int(input()))[2:]

Konversikan string input ke int, lalu int ke string biner dan hapus dua karakter pertamanya, karena binmetode mengembalikan string dalam format0b...

Ambil semua substring dari string biner, ubah menjadi desimal menggunakan int(n, 2)dan jumlahkan.

[N[j:j+i]for i in r(1,L)for j in r(L-i+1)]

adalah daftar semua substring. Versi tidak disatukan:

def all_substrings(N):
    result = []
    for i in range(1, len(N)):
        for j in range(len(N) - i + 1):
            result.append(N[j:j+i])
    return result

Semoga ini membantu.

CJam (22 byte)

Ini satu byte lebih panjang dari jawaban CJam terbaik saat ini, tetapi pendekatannya mungkin dapat disesuaikan dengan beberapa bahasa lain yang cukup menguntungkan.

3,ri_2b_,,:).*\+fbW%:-

Demo online

Analisis

Misalkan pertanyaannya adalah

menghitung jumlah sub-string dari angka biner

tanpa sedikitpun

yang panjangnya lebih pendek dari nomor aslinya

Maka itu tidak terlalu sulit untuk menunjukkan bahwa bit yang paling signifikan terjadi dengan berat total di 1*(2^B-1)mana Bjumlah bit; bit kedua paling signifikan terjadi dengan berat total 2*(2^(B-1)-1); turun ke bit-B paling signifikan, yang terjadi dengan berat total B*(2^1-1).

Mempertimbangkan sekarang pengurangan dari jumlah aslinya x,, kita berakhir dengan jumlah

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Pembedahan

3,        e# Put [0 1 2] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

Konversi ke basis 2 memberikan bagian pertama dari jumlah utama plus x; ke base 1 memberikan bagian kedua plus x; dan untuk basis 0 memberi adil x, jadi kurangi basis-1 dari basis-2 xs batalkan, dan kurangi basis-0 memberikan hasil yang diinginkan.

JavaScript (ES6), 78 byte

n=>[...n.toString(2)].map(c=>[...s+=c].map((_,i)=>n-='0b'+s.slice(i)),s='')|-n

Bagian luar mapmembangun substring terkemuka dari nrepresentasi biner; bagian dalam mengekstraksi substring trailing dari substring terkemuka, sehingga mencakup semua substring yang mungkin, termasuk representasi biner asli.

Setiap substring dikonversi dari biner kembali ke desimal dan dikurangkan dari input asli karena ini sedikit lebih pendek daripada menambahkannya bersama-sama dan mengurangi input asli.

Mathematica, 73 70 byte

Tr[FromDigits[#,2]&/@StringCases[#~IntegerString~2,__,Overlaps->All]]&

Fungsi. Integer-> Integer

Retina , 64

.*
$*
+`(1+)\1
$1a
a1
1
r&!M`.*
&!M`.*
^.*

+`1(a*)\b
a$.1$*1;
;

Cobalah online!

Deskripsi tingkat tinggi tahap demi tahap: konversi desimal ke unary, unary ke binary, dapatkan awalan, dapatkan akhiran awalan, buang angka asli, konversi biner ke unary, kembalikan hitungan. Saya akan menulis deskripsi yang lebih terperinci begitu saya selesai bermain golf, banyak dari tahapan ini tampak mencurigakan ...

C, 71 byte

f(n){int a=0,m=0,i;for(;++m<n;m+=m)for(i=n;i+i>m;i/=2)a+=i&m;return a;}

Kami mempertahankan akumulator adan masker m. Topeng dimulai pada 1 dan mendapat satu sedikit lebih lama setiap kali di sekitar lingkaran luar. Di loop dalam, salinan iinput secara berturut-turut digeser ke kanan sampai lebih pendek dari mask, mengakumulasi nilai masking setiap kali.

Program uji

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
    while (*++argv) {
        int n = atoi(*argv);
        printf("%d -> %d\n", n, f(n));
    }
    return 0;
}

Uji keluaran

./73793 $(seq 0 11)
0 -> 0
1 -> 0
2 -> 1
3 -> 2
4 -> 3
5 -> 5
6 -> 7
7 -> 9
8 -> 7
9 -> 10
10 -> 14
11 -> 17

C #, 148 byte

int x(int i){int s,r=0,j=i,p=System.Convert.ToString(i,2).Length+1,k;for(;--p>-1;){k=j;s=-1;for(;++s<p;)r+=(k>>=1);j=(i&((1<<p-1)-1))<<1;}return r;}

Atau, jika saya menambahkan Impor "menggunakan System.Math statis;" lalu 138 dengan

int x(int i){int s,r=0,j=i,p=(int)Round(Log(i,2)+1.49,0),k;for(;--p>-1;){k=j;s=-1;for(;++s<p;)r+=(k>>=1);j=(i&((1<<p-1)-1))<<1;}return r;}

Bahasa OOP seperti C # tidak akan memenangkan perlombaan seperti itu, tetapi saya tetap ingin mencobanya. Berikut ini adalah versi + tester yang lebih dipercantik.

class Program
{
    // Tester: 50 bytes
    static void Main(string[] args)
    {
        int i=2;
        do System.Console.WriteLine($"{i} -> {x(i++)}"); while (i < 12);
        System.Console.Read();
    }
    // Function: 65 bytes (size according to ILDASM.exe)
    static int x(int iOrg)
    {
        int pos, shift, retVal=0, iPrev=iOrg, iTemp;
        pos = System.Convert.ToString(iOrg, 2).Length;
        do {
            iTemp = iPrev; shift = 0;
            do retVal += (iTemp >>= 1); while (++shift < pos);
            iPrev = (iOrg & ((1 << pos - 1) - 1)) << 1;
        } while (--pos > -1); 
        return retVal;
    }
}

Do-while yang bersarang menambahkan nilai bergeser ke kanan dari iTemp (setelah menugaskannya) selama shift + 1 lebih kecil dari pos. Baris berikutnya menghitung nilai bergeser iPrev berikutnya

x1 = 1 << p -1; // 1 << 4 -1 = 8 [1000]
x2 = x1 - 1;    // 8 -  1 = 7    [0111]
x3 = i & x2;    // 1011 & 0111 = 0011 
x4 = x3 << 1;   // 0011 << 1 = 00110
i2 = x4;

x1 dan x2 menghitung mask, x3 menerapkannya dan kemudian menggesernya, karena digit terakhir selalu turun. Untuk 11, tampilannya seperti ini:

START -> _1011[11]
101
10
1   -->  X0110[6], r=0+5+2+1=8
 011
 01
 0  -->  XX110[6], r=8+4=12
  11
  1 -->  XXX10[2], r=12+4=16
   1 ->  XXXX0[X], r=16+1=17

PowerShell v2 +, 138 Bytes

param($a)$a=[convert]::ToString($a,2);(($b=$a.length-1)..1|%{$l=$_;0..($b-$l+1)|%{[convert]::ToInt32($a.substring($_,$l),2)}})-join'+'|iex

Ooof. Konversi ke / dari biner itu mahal.

Mengambil input $a, lalu menggunakan panggilan .NET[convert]::ToString($a,2) untuk mengubahnya menjadi representasi biner. Dari sana, kita melewati dua loop - yang pertama dihitung mundur dari ujung string ke bawah 1, dan yang kedua dihitung ke atas dari 0. (Yang pertama adalah berapa lama substring untuk menarik keluar, dan yang kedua adalah indeks di mana dalam string untuk memulai substring.) Kami menetapkan helper di $lsepanjang jalan untuk meneruskannya ke loop dalam.

Di dalam lingkaran dalam, kami menggunakan panggilan .NET[convert]::ToInt32() lain untuk mengonversi yang sesuai .substring()dari basis2 menjadi integer. Masing-masing kemudian dibiarkan dalam pipa. Kami merangkum semua itu dengan parens ()dan -joinmereka bersama-sama dengan +, lalu melemparkannya ke iex(kependekan dari Invoke-Expressiondan sejenisnya eval).

_{saya pikir ini secara teknis membutuhkan v2 atau yang lebih baru untuk benar memanggil panggilan NET.}