Сумма двоичных подстрок

16

Эта задача проста, учитывая десятичное число, преобразовать в двоичное и вычислить сумму подстрок двоичного числа, длина которых короче исходного числа. Вот пример:

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

Ваша программа должна взять одно десятичное целое число в качестве входных данных и вывести сумму двоичных подстрок, как показано выше. Вы можете предположить, что входные данные всегда будут иметь более двух цифр в двоичном представлении, и что входные данные не вызовут никаких ошибок во время выполнения вашей программы.

Это , выигрывает самый короткий код в байтах!

Тестовые случаи:

2  => 1
3  => 2
4  => 3
5  => 5
6  => 7
7  => 9
8  => 7
9  => 10
10 => 14
11 => 17
GamrCorps
источник
4
Любопытно, что исключение полноразмерной подстроки является существенной дополнительной проблемой.
Питер Тейлор

Ответы:

12

Желе, 10 7 байт

BṡRḄFS_

Попробуйте онлайн!

Как это устроено

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.
Деннис
источник
Какая кодировка дает вам 1 байт / символ для этой программы?
Тоби Спейт
1
@TobySpeight Jelly использует собственную кодовую страницу.
спагетто
8

Пиф, 10

sPiR2.:.BQ

Попробуйте онлайн или запустите Test Suite

Объяснение:

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
FryAmTheEggman
источник
5

Python 3, 111 символов

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

РЕДАКТИРОВАТЬ : Объяснение:

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

Преобразуйте входную строку в int, затем int в двоичную строку и удалите первые два символа, поскольку binметод возвращает строку в формате0b...

Возьмите все подстроки двоичной строки, преобразуйте их в десятичные, используя int(n, 2)и суммируйте их.

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

список всех подстрок Безголовая версия:

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

Надеюсь это поможет.

shooqie
источник
4

CJam (22 байта)

Это на один байт длиннее, чем текущий лучший ответ CJam, но этот подход, вероятно, может быть выгодно адаптирован к некоторым другим языкам.

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

Онлайн демо

Анализ

Предположим, что вопрос

вычислить сумму подстрок двоичного числа

без долота

длина которого короче исходного числа

Тогда нетрудно показать, что самый старший бит встречается с общим весом, 1*(2^B-1)где Bесть количество бит; второй по значимости бит происходит с общим весом 2*(2^(B-1)-1); вплоть до Bth-самого значимого бита, который происходит с общим весом B*(2^1-1).

Принимая во внимание вычитание исходного числа x, мы получаем сумму

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

рассечение

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

Преобразование в базу 2 дает первую часть основной суммы плюс x; к базе 1 дает вторую часть плюс x; и для базы 0 дается просто x, поэтому вычитание базы-1 из базы-2 xотменяется, а вычитание базы-0 дает желаемый результат.

Питер Тейлор
источник
3

JavaScript (ES6), 78 байт

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

Внешнее mapстроит ведущие подстрокиn двоичного представления России; внутренняя извлекает конечные подстроки из ведущих подстрок, таким образом покрывая все возможные подстроки, включая исходное двоичное представление.

Каждая подстрока преобразуется из двоичной обратно в десятичную и вычитается из исходного ввода, поскольку это немного короче, чем сложение их вместе и вычитание исходного ввода.

Нил
источник
2

Mathematica, 73 70 байт

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

Функция. Integer-> Integer

CalculatorFeline
источник
1
Жаль, математика не имеет хороших инструментов для работы с подсписками.
Симмонс
1

Сетчатка , 64

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

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

Попробуйте онлайн!

Высокоуровневое поэтапное описание: преобразование десятичного числа в унарное, унарное в двоичное, получение префиксов, получение суффиксов префиксов, сброс исходного числа, преобразование двоичного числа в унарное, возвращаемое количество. Я напишу более подробное описание, как только я закончу играть в гольф, многие из этих этапов кажутся подозрительными ...

FryAmTheEggman
источник
1

C 71 байт

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

Мы поддерживаем аккумулятор aи маску m. Маска начинается с 1 и каждый раз увеличивается на один цикл во внешнем цикле. Во внутреннем цикле копия iвходных данных последовательно смещается вправо до тех пор, пока она не станет короче маски, накапливая маскированное значение каждый раз.

Тестовая программа

#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;
}

Тестовый вывод

./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
Тоби Спейт
источник
1

C #, 148 байт

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

Или, если я добавлю Import "using static System.Math;" затем 138 с

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

ООП языки, такие как C #, не выиграют такую ​​гонку, но я все равно хотел попробовать. Вот более качественная версия + тестер.

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 добавляет смещенное вправо значение iTemp (после его присвоения), если shift + 1 меньше, чем pos. Следующая строка вычисляет следующее смещенное значение iPrev

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 и x2 вычисляют маску, x3 применяет ее, а затем сдвигает влево, поскольку последняя цифра всегда удаляется. Для 11 это выглядит так:

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
DW.com
источник
Я знаю, что большинство ответов в C работают безупречно и в C # (@ Tony-Speight работал без проблем), но я бы не стал понимать цель. Кроме того, я не смотрел на комментарии (ну, кроме заголовков Bold) до тех пор, пока сам не закончил, поэтому не было никакой опасности сделать это «как С».
DW.com
0

PowerShell v2 +, 138 байт

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. Это преобразование в / из двоичного кода стоит дорого.

Принимает ввод $a, затем использует вызов .NET,[convert]::ToString($a,2) чтобы превратить его в двоичное представление. Оттуда мы проходим две петли - первая отсчитывает назад от конца строки до 1, а вторая отсчитывает вверх от 0. (Первая - это длина вытянутой подстроки, а вторая - индекс места в строке, с которого начинается подстрока.) Мы устанавливаем помощник$l по пути, чтобы передать его во внутренний цикл.

Во внутреннем цикле мы используем другой вызов .NET,[convert]::ToInt32() чтобы преобразовать соответствующий .substring()из базы 2в целое число. Каждый из них затем остается на конвейере. Мы инкапсулируем все это с помощью паренов ()и -joinих вместе с символом a +, затем отбрасываем это в iex(сокращенно Invoke-Expressionи аналогично eval).

Я думаю, что технически это требует v2 или новее, чтобы правильно вызывать вызовы .NET.

AdmBorkBork
источник