Ce défi est simple, étant donné un nombre décimal, convertissez en binaire et calculez la somme des sous-chaînes du nombre binaire, dont la longueur est plus courte que le nombre d'origine. Voici un exemple:

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

Votre programme doit prendre un seul entier décimal en entrée et sortir la somme des sous-chaînes binaires, comme vu ci-dessus. Vous pouvez supposer que l'entrée aura toujours plus de deux chiffres dans sa représentation binaire et que l'entrée ne provoquera aucune erreur lors de l'exécution de votre programme.

C'est le code-golf , le code le plus court en octets gagne!

Cas de test:

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

Gelée, 10 7 octets

BṡRḄFS_

Essayez-le en ligne!

Comment ça fonctionne

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

Essayez-le en ligne ou exécutez la suite de tests

Explication:

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 octets

Merci à Dennis de m'avoir aidé à économiser 6 octets!

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

Fonctionne uniquement avec la dernière version de CJam (disponible sur TIO). Essayez-le en ligne !

Ancienne version:

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

Essayez-le en ligne .

Python 3, 111 caractères

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

ÉDITER : Explication:

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

Convertissez la chaîne d'entrée en int, puis l'int en chaîne binaire et supprimez ses deux premiers caractères, car la binméthode renvoie une chaîne au format0b...

Prenez toutes les sous-chaînes de la chaîne binaire, convertissez-les en décimal en utilisant int(n, 2) et additionnez-les.

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

est une liste de toutes les sous-chaînes. Version non golfée:

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

J'espère que cela t'aides.

CJam (22 octets)

C'est un octet de plus que la meilleure réponse CJam actuelle, mais l'approche peut probablement être adaptée à d'autres langues de manière très rentable.

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

Démo en ligne

Une analyse

Supposons que la question soit

calculer la somme des sous-chaînes du nombre binaire

sans le bit

dont la longueur est plus courte que le numéro d'origine

Ensuite, il n'est pas trop difficile de montrer que le bit le plus significatif se produit avec un poids total 1*(2^B-1)où Best le nombre de bits; le deuxième bit le plus significatif se produit avec le poids total 2*(2^(B-1)-1); jusqu'au bit le plus significatif Bth, qui se produit avec le poids total B*(2^1-1).

En tenant compte maintenant de la soustraction du nombre original x, on se retrouve avec la somme

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

Dissection

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

La conversion en base 2 donne la première partie de la somme principale plus x; à la base 1 donne la deuxième partie plus x; et à la base 0 donne juste x, donc la soustraction de la base-1 de la base-2 l' xannule, et la soustraction de la base-0 donne le résultat souhaité.

JavaScript (ES6), 78 octets

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

L'extérieur mapconstruit des sous-chaînes de tête de nla représentation binaire de; celui interne extrait les sous-chaînes de fin des sous-chaînes de tête, couvrant ainsi toutes les sous-chaînes possibles, y compris la représentation binaire d'origine.

Chaque sous-chaîne est convertie de binaire en décimal et soustraite de l'entrée d'origine car cela est légèrement plus court que de les additionner et de soustraire l'entrée d'origine.

Mathematica, 73 70 octets

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

Une fonction. Entier-> Entier

Rétine , 64

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

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

Essayez-le en ligne!

Une description de haut niveau étape par étape: convertir décimal en unaire, unaire en binaire, obtenir des préfixes, obtenir des suffixes de préfixes, vider le nombre d'origine, convertir un binaire en unaire, retourner le nombre. J'écrirai une description plus détaillée une fois que j'aurai fini de jouer au golf, beaucoup de ces étapes semblent suspectes ...

C, 71 octets

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

Nous maintenons un accumulateur aet un masque m. Le masque commence à 1 et devient un peu plus long à chaque fois autour de la boucle extérieure. Dans la boucle intérieure, une copiei de l'entrée est successivement décalée vers la droite jusqu'à ce qu'elle soit plus courte que le masque, accumulant à chaque fois la valeur masquée.

Programme de test

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

Sortie test

./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 octets

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

Ou, si j'ajoute Import "using static System.Math;" puis 138 avec

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

Les langages OOP comme C # ne gagneront pas une telle course, mais je voulais quand même l'essayer. Voici une version + testeur plus embellie.

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

Le do-while imbriqué ajoute la valeur décalée vers la droite d'iTemp (après l'avoir affectée) tant que shift + 1 est plus petit que pos. La ligne suivante calcule la prochaine valeur décalée d'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 et x2 calculent le masque, x3 l'applique puis le décale vers la gauche, car le dernier chiffre est toujours supprimé. Pour 11, cela ressemble à ceci:

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 octets

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. Cette conversion de / vers binaire coûte cher.

Prend l'entrée $a, puis utilise l' appel .NET[convert]::ToString($a,2) pour le transformer en représentation binaire. De là, nous parcourons deux boucles - la première compte à rebours de la fin de la chaîne vers le bas 1et la seconde compte vers le haut à partir de 0. (Le premier est la longueur d'une sous-chaîne à extraire, et le second est l'index de l'endroit dans la chaîne pour démarrer la sous-chaîne.) Nous avons défini une aide en $lcours de route pour la transmettre à la boucle intérieure.

À l'intérieur de la boucle interne, nous utilisons un autre appel .NET[convert]::ToInt32() pour convertir la .substring()base appropriée 2en un entier. Chacun d'eux est ensuite laissé sur le pipeline. Nous encapsulons tout cela avec des parenthèses ()et -joinles ensemble avec un +, puis jetons cela à iex(court pour Invoke-Expressionet similaire à eval).

_{Je pense que cela nécessite techniquement v2 ou plus récent pour appeler correctement les appels .NET.}