Convertisseur binaire en décimal

32

Convertisseur binaire en décimal

Pour autant que je puisse voir, nous n'avons pas de défi de conversion binaire en décimal simple.


Écrivez un programme ou une fonction qui prend un entier binaire positif et génère sa valeur décimale.

Vous n'êtes pas autorisé à utiliser les fonctions de conversion de base intégrées. Les fonctions de nombre entier à décimal (par exemple, une fonction qui se transforme 101010en [1, 0, 1, 0, 1, 0]ou "101010") sont exemptées de cette règle et donc autorisées.

Règles:

  • Le code doit prendre en charge les nombres binaires jusqu'à la valeur numérique la plus élevée prise en charge par votre langue (par défaut)
  • Vous pouvez choisir d'avoir des zéros non significatifs dans la représentation binaire
  • La sortie décimale peut ne pas avoir de zéros non significatifs.
  • Les formats d'entrée et de sortie sont facultatifs, mais il ne peut pas y avoir de séparateurs entre les chiffres. (1,0,1,0,1,0,1,0)n'est pas un format d'entrée valide, mais les deux 10101010et le (["10101010"])sont.
    • Vous devez prendre l'entrée dans le sens "normal". ne l' 1110est 14pas 7.

Cas de test:

1
1

10
2

101010
42

1101111111010101100101110111001110001000110100110011100000111
2016120520371234567

Ce défi est lié à quelques autres défis, par exemple ceci , ceci et cela .

Stewie Griffin
la source
En relation
mbomb007
La sortie doit-elle être non signée ou peut-elle être signée? De plus, si ma langue passe automatiquement entre des entiers 32 bits et 64 bits en fonction de la longueur de la valeur, la sortie peut-elle être signée dans les deux plages? Par exemple, il y a deux valeurs binaires qui se convertiront en décimal -1( 32 1'set 64 1's)
lait
De plus, la sortie peut-elle être flottante, doit-elle être un entier?
Carcigenicate
@Carcigenicate Il doit s'agir d'un entier, mais il peut être de n'importe quel type de données. Tant que round(x)==xvous allez bien :) 2.000est une sortie acceptée pour 10.
Stewie Griffin
Oh doux. Merci.
Carcigenicate

Réponses:

56

Gelée , 5 octets

DḤ+¥/

Essayez-le en ligne!

Explication

enter image description here

Le casting

  • Dest une monade (fonction unique argument): chiffres, en tournant 1234dans [1, 2, 3, 4].

  • est une monade qui double son argument unique.

  • + est une dyade (fonction à deux arguments) qui ajoute ses arguments gauche et droit.

De là, cela devient un peu délicat.

Voici ce qui se passe au moment de l'analyse

  • D,, et +sont lus. La chaîne ressemble [D, Ḥ, +].

  • Les deux caractères suivants sont des quicks , qui agissent comme des opérateurs de suffixe au moment de l'analyse sur les liens (fonctions) que nous avons lus jusqu'à présent.

  • Quand ¥est lu, les deux derniers liens sont sautés et remplacés par un lien qui agit comme la dyade formée en les composant. Alors maintenant, la chaîne ressemble [D, dyad(Ḥ+)].

  • Quand /est lu, le dernier lien (qui devrait être une dyade) est sauté et remplacé par une monade qui se replie en utilisant cette dyade (intuitivement: f/prend une liste, y remplace les virgules fet évalue le résultat.)

  • La chaîne finale ressemble à [D, fold(dyad(Ḥ+))]deux monades.

Voici ce qui se passe au moment de l'exécution

  • L'entrée (un nombre) est implicitement lue dans la valeur de travail (disons, 101010).

  • Dest exécuté, en remplaçant la valeur de travail par ses chiffres ( [1,0,1,0,1,0]).

  • fold(dyad(Ḥ+))est exécuté, en remplaçant la valeur de travail par 1∗0∗1∗0∗1∗0, où est la dyade Ḥ+.

Alors qu'est-ce que cela x∗yévalue?

  • Dans une définition dyadique, la valeur de travail est d' abord la gauche argument x.

  • , la double monade, double cette valeur. La valeur de travail est maintenant 2x.

  • +, la dyade plus , n'a pas d'argument correct, c'est donc un crochet : un modèle syntaxique spécial dans lequel le bon argument de cette dyade est injecté +. Cela donne 2x + yla valeur de travail finale, qui est retournée.

Donc, l'expression entière s'évalue à:

1∗0∗1∗0∗1∗0 = 2×(2×(2×(2×(2×1+0)+1)+0)+1)+0
            = 32×1 + 16×0 + 8×1 + 4×0 + 2×1 + 1×0
            = 42
Lynn
la source
10
Vos explications vont de mieux en mieux :-)
Luis Mendo
2
Hé, je suppose que tu le fais à partir de maintenant? C'est génial, +1.
Erik the Outgolfer
4
Je pense que c'est le premier morceau de Jelly que j'ai jamais compris. +1!
Blue
Bravo. En fait, je comprends ce que je pensais au départ comme un désordre de personnages apparemment aléatoires. Magnifique explication.
swinefish
1
@Mark Jelly a sa propre page de code pour que les programmes aient l'air, ahem, lisibles, mais les programmes pourraient tout aussi bien être des bytestrings.
Lynn
20

Python 2, 49 37 31 30 octets

Maintenant, cela prendra un nombre binaire dans une représentation décimale, car Python peut gérer des entiers arbitrairement grands.

b=lambda n:n and n%2+2*b(n/10)

merci à xnor pour avoir sauvé un octet :)

La façon la plus simple de voir comment cela fonctionne est de voir une formule de base pour convertir le binaire en décimal:

= 101010 
= 1*(2^5) + 0*(2^4) + 1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)
= 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 0*1
= 42

Il s'agit d'une méthode de conversion «standard». Vous pouvez développer la troisième ligne comme suit:

= ((((1*2 + 0)*2 + 1)*2 + 0)*2 + 1)*2 + 0

Et c'est essentiellement ce que fait la méthode récursive que j'ai faite.

Solutions alternatives que j'avais:

b=lambda n:n and n%10+2*b(n/10)
b=lambda n:n%10+2*(n and b(n/10))
b=lambda n:0if n<1else n%10+2*b(n/10)
b=lambda n:0**(n/10)or n%10+2*b(n/10)
b=lambda n,o=0:o*(n<'0')or b(n[1:],2*o+int(n[0]))
lambda j:sum(int(b)*2**a for a,b in enumerate(j,1))
Kade
la source
6
Vous pouvez faire n%5ou n%2au lieu de n%10.
xnor
@xnor Ah, je ne sais pas comment j'ai raté ça! Merci :)
Kade
12

05AB1E , 6 octets

Code:

$¦v·y+

Pour l'explantion, prenons l'exemple 101010 . Nous commençons par le chiffre 1 (qui est représenté par le premier chiffre). Après cela, nous avons deux cas:

  • Si le chiffre est un 0 , multipliez le nombre par 2.
  • Si le chiffre est un 1 , multipliez le nombre par 2 et ajoutez 1.

Donc, pour le cas 101010 , ce qui suit est calculé:

  • 1 01010, commencez par le chiffre 1 .
  • 1 0 1010, multiplié par deux, résultant en 2 .
  • 10 1 010, multipliez par deux et ajoutez-en un, ce qui donne 5 .
  • 101 0 10, multiplier par deux, ce qui donne 10 .
  • 1010 1 0, multipliez par deux et ajoutez-en un, ce qui donne 21 .
  • 10101 0 , multiplier par deux, résultant en 42 , ce qui est le résultat souhaité.

Explication du code:

$         # Push 1 and input
 ¦        # Remove the first character
  v       # For each character (starting with the first)
   ·      #   Multiply the carry number by two
    y+    #   Add the current character (converted automatically to a number)

Utilise le codage CP-1252 . Essayez-le en ligne!

Adnan
la source
Joli! (ne fonctionne pas pour 0 même si je viens de le remarquer)
Emigna
@Emigna Oui, heureusement, votre code n'a besoin que de fonctionner pour des nombres binaires positifs.
Adnan
Je n'ai même pas vu cette partie. Très bien alors :)
Emigna
9

Haskell, 16 111 + 57 = 168 octets

import Data.String
instance IsString[Int]where fromString=map((-48+).fromEnum)
f::[Int]->Int
f=foldl1((+).(2*))

+57 octets pour les drapeaux de compilation -XOverloadedStrings, -XOverlappingInstanceset -XFlexibleInstances.

Le défi a un format d'E / S lourd , car il dépend fortement de la façon dont les types de données sont exprimés dans le code source. Ma première version (16 octets), à savoir

foldl1((+).(2*))

prend une liste d'entiers, par exemple [1,0,1,0,1,0]et a été déclaré invalide parce que des listes Haskell littérales se trouvent ,entre les éléments. Les listes en soi ne sont pas interdites. Dans ma nouvelle version, j'utilise la même fonction, désormais nommée f, mais je surcharge "Citer les séquences de caractères fermées". La fonction prend toujours une liste d'entiers comme vous pouvez le voir dans l'annotation de type [Int] -> Int, mais les listes avec des entiers à un chiffre peuvent maintenant être écrites comme "1234", par exemple

f "101010"

qui évalue à 42. Malchanceux Haskell, car le format de liste natif ne correspond pas aux règles du défi. Btw, f [1,0,1,0,1,0]fonctionne toujours.

nimi
la source
2
Malheureusement, une liste n'est pas une entrée valide.
Jonathan Allan
@JonathanAllan: Pourquoi? Et si c'est le cas, comment devrait-il prendre des informations? Dans Haskell, une chaîne n'est qu'une liste de caractères.
nimi
Je ne sais pas pourquoi ... mais je me suis renseigné à ce sujet dès le début et une modification a été effectuée pour ajouter " (1,0,1,0,1,0,1,0)n'est pas un format d'entrée valide, mais les deux 10101010et le (["10101010"])sont." en outre, un commentaire suggère que le tableau de caractères est acceptable si c'est ainsi qu'une entrée de chaîne est interprétée.
Jonathan Allan
1
@JonathanAllan: tout "entier binaire" (l'entrée que nous devons prendre) est intrinsèquement séparé, c'est une séquence de puissances de 2. La restriction concerne les séparateurs explicites (entre les chiffres) et non la séparation. D'une manière ou d'une autre, je dois prendre des chiffres séparés.
nimi
2
Op ici: s'il est possible de saisir 10101010, "10101010"ou quelque chose de similaire et de le faire fonctionner, la soumission est valide. Vous pouvez l'appeler une chaîne, une liste, un entier ou autre. La saisie [1][0][1][0]ou [1,0,1,0]n'est pas correcte. Fondamentalement, il devrait être possible de frapper un tas de uns et de zéros dans une rangée quelque part. Est-ce clair?
Stewie Griffin
7

Rétine, 15 octets

Convertit du binaire en unaire, puis unaire en décimal.

1
01
+`10
011
1

Essayez-le en ligne

mbomb007
la source
Vous n'êtes pas autorisé à utiliser les fonctions de conversion de base intégrées. ~ OP
Roman Gräf
10
@ RomanGräf Il n'y en a pas. Je décrivais simplement le processus de ma solution.
mbomb007
7

PHP, 44 octets

for(;""<$c=$argv[1][$i++];)$n+=$n+$c;echo$n;

J'aurais juré avoir déjà vu cette question. Enfin bon.

Lit le nombre de gauche à droite, décale vers la gauche et ajoute le bit actuel.

Titus
la source
7

JavaScript (ES6), 33 31 octets

s=>[...s].map(c=>r+=+c+r,r=0)|r

Edit: plus court mais moins doux: 2 octets économisés grâce à @ETHproductions.

Neil
la source
Comme c'est souvent le cas, .mapest plus court:s=>[...s].map(c=>+c+r+r,r=0)|r
ETHproductions
@ETHproductions Comment votre fonction renvoie-t-elle autre chose que 0?
Neil
Désolé, cela devrait êtres=>[...s].map(c=>r+=+c+r,r=0)|r
ETHproductions
7

Labyrinthe , 17 15 octets

-+:
8 +
4_,`)/!

Essayez-le en ligne!

Image du code

Labyrinth est un langage bidimensionnel basé sur la pile. Dans le labyrinthe, l'exécution du code suit le chemin du code comme un labyrinthe avec des espaces agissant comme des murs et commençant par le caractère non spatial le plus à gauche. Le flux de code est déterminé par le signe du haut de la pile. Puisque la pile a des zéros implicites en bas, les quatre premières instructions ( -+:+) n'ont aucun effet.

Boucle commençant au ,

  • , Poussez la valeur de code ascii du caractère d'entrée suivant à la fin de la pile, ou appuyez sur -1 si EOF.
  • _48 pousse 48 en haut de la pile
  • -Pop y, pop x, poussez x-y. Les instructions précédentes ont pour effet de soustraire 48 de l'entrée donnant 0 pour "0" et 1 pour "1".
  • +Pop y, pop x, poussez x+y.
  • : Dupliquez le haut de la pile
  • + Ceci et l'instruction précédente ont pour effet de multiplier la valeur actuelle par 2

Ainsi, la partie circulaire du code, en effet, multiplie le nombre actuel par 2 et ajoute un 1 ou un 0 selon que le caractère 1 ou 0 a été entré.

Queue

Si le haut de la pile est négatif (ce qui signifie que EOF a été trouvé), le code tournera à gauche à la jonction (en direction du point-virgule).

  • `` Niez le haut de la pile pour obtenir 1
  • ) Incrémenter le haut de la pile pour obtenir 2
  • /Pop y, pop x, appuyez sur x / y (division entière). Cela a pour effet d'annuler le dernier *2de la boucle.
  • !Affiche la représentation entière du haut de la pile. À ce stade, le programme se retourne car il a atteint une impasse, puis se termine avec une erreur car il essaie de diviser par zéro.

Merci à @Martin Ender de m'avoir sauvé 2 octets (et de m'avoir appris à mieux penser dans Labyrinth).

Robert Hickman
la source
Au lieu de _48-vous, vous pouvez simplement le faire, #%mais malheureusement je ne vois pas comment cela pourrait aider avec le nombre d'octets.
Martin Ender
Vous pouvez enregistrer un octet avec `)au lieu de ;_2bien.
Martin Ender
@MartinEnder, je ne comprends pas votre commentaire #%. Pouvez-vous expliquer comment cela fonctionne en remplacement _48-de la conversion de ascii en int. Merci pour l' )astuce. Je vais faire ce changement.
Robert Hickman
À ce stade de votre programme, il y a toujours deux valeurs sur la pile, donc #c'est juste court pour _2. Bien qu'il _2%ne s'agisse pas d'une méthode de conversion générale pour ASCII en entier, cela fonctionne ici car vous n'êtes intéressé que par les deux premiers chiffres comme entrée possible. Une alternative serait _1&(puisque modulo 2 extrait simplement le bit le moins significatif).
Martin Ender
Oh. C'est brillant. Mais oui, je ne sais pas comment utiliser cette substitution ( #%) pour raccourcir le code dans son ensemble.
Robert Hickman
6

Brain-Flak , 46 , 28 octets

([]){{}({}<>({}){})<>([])}<>

Essayez-le en ligne!

Beaucoup d'octets enregistrés grâce à @Riley!

Étant donné que brain-flak ne peut pas prendre d'entrée binaire, l'entrée est une liste de «0 et de 1».

Explication:

#Push the height of the stack
([])

#While true:
{

 #Pop the height of the stack
 {}

 #Push this top number to (the other stack * 2)
 ({}<>({}){})

 #Toggle back on to the main stack
 <>

 #Push the new height of the stack
 ([])

#endwhile
}

#Toggle back to the other stack, implicitly display.
<>
DJMcMayhem
la source
J'adore l'explication! Difficile de lire brain-flak sans ça :)
Emigna
2
^. Je ne peux même pas lire mes propres programmes si je ne me laisse pas quelques commentaires.
Riley
Vous pouvez le réduire à 32 octets en vous débarrassant du tout si une partie, et pour l'étape "ajouter un numéro à une autre pile", ajoutez-le simplement à la (autre pile) * 2. ([]){({}[()]<({}<>({}){})><>)}<>
Riley
Et vous pouvez enregistrer 4 autres en sautant juste au début et en poussant à nouveau la hauteur à la fin. ([]){{}({}<>({}){})<>([])}<>
Riley
@Riley Oh mon Dieu, c'est du génie. Merci beaucoup!
DJMcMayhem
6

Java, 84 79 46 48 octets

  • Version 3.1

Modifié en long/ 48 octets:

s->{long x=0;for(char c:s)x=c-48l+x*2;return x;}
  • Version 3.0

A fait du golf / 46 octets:

s->{int x=0;for(char c:s)x=c-48+x*2;return x;}
  • Version 2.0

Merci à @Geobits! / 79 octets:

s->{int i=Math.pow(2,s.length-1),j=0;for(char c:s){j+=c>48?i:0;i/=2;}return j;}
  • Version 1.0

84 octets:

s->{for(int i=-1,j=0;++i<s.length;)if(s[i]>48)j+=Math.pow(2,s.length-i+1);return j;}
Roman Gräf
la source
1
suppose que j'aurais dû faire une solution itérative. lulz. bon travail
Poke
Votre type d'entrée est-il List <Character> ou String? Si c'est le dernier, je ne savais pas que Java8 pouvait le faire! Si c'est le premier, est-ce permis par le défi?
Poke
sdevrait être char[]. J'espère que c'est permis ...
Roman Gräf
Quel est le type de retour ici? Je pense que cela devrait être long car "Le code doit prendre en charge les nombres binaires jusqu'à la valeur numérique la plus élevée prise en charge par votre langue" par l'OP, mais pour les valeurs plus petites, je pense qu'il renvoie un entier
Poke
1
Probablement bien sur le type d'entrée par cela . Pourrait vouloir prendre le hit de 2 octets pour la sortie imo
Poke
4

Befunge-98, 12 octets

2j@.~2%\2*+

Essayez-le en ligne!

Lit un caractère à la fois depuis l'entrée, le convertit en 0 ou 1 en prenant sa valeur modulo 2 (0 est char (48), 1 est char (49)), puis utilise l'algorithme habituel de doubler la valeur actuelle et d'ajouter le nouveau chiffre à chaque fois.

Bonus: Cela fonctionne avec n'importe quel type de chaîne d'entrée, j'essaie depuis un certain temps maintenant de trouver une combinaison amusante d'entrée-> sortie, mais je n'ai pas pu produire quoi que ce soit (malheureusement, "réponse" = 46). Peut tu?

Leo
la source
LOL. Je jouais le même jeu avec ma réponse. Le nombre le plus intéressant que j'ai pu générer était 666 .
James Holderness
Joli! Je n'avais pas réussi à trouver quoi que ce soit convenable pour 666: D Ce serait beaucoup plus facile si la capitalisation avait un effet sur les valeurs ...
Leo
@James Holderness - J'ai fait la même chose et je n'ai trouvé que «l'année» pour ramener 366, la vôtre est vraiment bonne.
Pélican bleu canard
4

Javascript (ES7) 41 40 36 octets

f=([c,...b])=>c?c*2**b.length+f(b):0

prend une chaîne en entrée

Rasé d'un octet grâce à ETHproductions

f=([c,...b])=>c?c*2**b.length+f(b):0
document.write([
    f('101010'),
    f('11010'),
    f('10111111110'),
    f('1011110010110'),
].join("<br>"))

Shaun H
la source
1
L'associativité de droite à gauche de **est bizarre, mais agréable de l'utiliser ici. 1<<b.lengthferait la même chose, mais il faudrait des parenthèses pour éviter d'être analysé comme (c*1)<<(b.length+...). Je pense que vous pouvez enregistrer un octet en le remplaçant b[0]par b+b( voir ici ).
ETHproductions
4

C # 6, 85 37 36 octets

long b(long n)=>n>0?n%2+2*b(n/10):0;
  • Merci à Kade d' avoir économisé 41 octets!
  • Le passage à C # 6 a enregistré 7 autres octets.
Yytsi
la source
Peut - être que cela pourrait vous inspirer? ;)
Kade
@Kade Oui, merci! Je regardais la réponse Python qui utilise la même technique au même moment que vous avez lié cela: DI peut devenir encore plus court avec C # 6.
Yytsi
3

05AB1E , 7 octets

RvNoy*O

Essayez-le en ligne!

Explication

R         # reverse input
 v     O  # sum of
  No      # 2^index
     *    # times
    y     # digit
Emigna
la source
3

C, 53

v(char*s){int v=0,c;while(c=*s++)v+=v+c-48;return v;}

Identique à ma réponse javascript

Test Ideone

edc65
la source
Vous pouvez enregistrer 4 octets en déclarant vet en ctant que variables globales (bien que vous deviez changer le nom de v, car c'est déjà le nom de la fonction) comme ceci:w=0;c;v(char*s){while(c=*s++)w+=w+c-48;return w;}
Steadybox
@Steadybox ça pourrait l'être w,c;mais je ne veux pas utiliser de globaux quand la réponse est une fonction (même dans code-golf)
edc65
La valeur par défaut de @Steadybox Globals est également 0, vous pouvez donc supprimer le =0.
algmyr
3

Perl, 25 octets

-3 octets grâce à @Dom Hastings.

24 octets de code + 1 octet pour l' -pindicateur.

$\|=$&<<$v++while s/.$//

Pour l'exécuter:

perl -pe '$\|=$&<<$v++while s/.$//' <<< 101010

Explications:

$\|=$&<<$v++  # Note that: we use $\ to store the result
              # at first $v=0, and each time it's incremented by one
              # $& contains the current bit (matched with the regex, see bellow)
              # So this operation sets a $v-th bit of $\ to the value of the $v-th bit of the input
while         # keep doing this while...
s/.$//        #  ... there is a character at the end of the string, which we remove.
         # $\ is implicitly printed thanks to -p flag
Dada
la source
3

Pushy , 10 octets

Prend entrée comme une liste de 0/1 sur la ligne de commande: $ pushy binary.pshy 1,0,1,0,1,0.

L:vK2*;OS#

L'algorithme montre vraiment la beauté d'avoir une deuxième pile:

            \ Implicit: Input on stack
L:    ;     \ len(input) times do:
  v         \   Push last number to auxiliary stack
   K2*      \   Double all items
       OS#  \ Output sum of auxiliary stack

Cette méthode fonctionne car la pile sera doublée stack length - nfois avant d'atteindre le nombre n, qui est ensuite vidé dans la deuxième pile pour plus tard. Voici à quoi ressemble le processus d'entrée 101010:

1: [1,0,1,0,1,0]
2: []

1: [2,0,2,0,2]
2: [0]

1: [4,0,4,0]
2: [2]

1: [8,0,8]
2: [2,0]

1: [16,0]
2: [2,0,8]

1: [32]
2: [2,0,8,0]

1: []
2: [2,0,8,0,32]

2 + 8 + 32 -> 42
FlipTack
la source
3

Matlab, 30 octets

@(x)sum(2.^find(flip(x)-48)/2)

Le dernier cas de test a des erreurs d'arrondi (à cause de double), donc si vous avez besoin d'une précision totale:

@(x)sum(2.^uint64(find(flip(x)-48))/2,'native')

avec 47 octets.

Jonas
la source
Je ne peux pas tester cela, mais je pense @(x)sum(2.^(find(flip(x)-48)-1))qu'il donnera le résultat correct pour tous les cas pour 32 octets. flipfonctionne comme fliplrsi xest unidimensionnel.
Stewie Griffin
Belle solution! J'ai également rencontré l'erreur d'arrondi, merci pour le correctif. Quel est le format de x? Appeler flip ou fliplr sur un numéro ne fait que renvoyer ce numéro.
MattWH
x est la chaîne binaire, alors appelez-la avec f=@(x)..; f('1111001010').
Jonas
3

Rétine , 12 octets

Le nombre d'octets suppose un codage ISO 8859-1.

+%`\B
¶$`:
1

Essayez-le en ligne!

Solution alternative:

+1`\B
:$`:
1

Explication

Cela sera probablement plus facile à expliquer sur la base de mon ancienne version, moins golfée, puis en montrant comment je l'ai raccourcie. J'ai utilisé pour convertir le binaire en décimal comme ceci:

^
,
+`,(.)
$`$1,
1

La seule façon raisonnable de construire un nombre décimal dans Retina est de compter les choses (car Retina a quelques fonctionnalités qui lui permettent d'imprimer un nombre décimal représentant un montant). La seule approche possible est donc de convertir le binaire en unaire, puis de compter le nombre de chiffres unaires. La dernière ligne fait le comptage, donc les quatre premiers convertissent le binaire en unaire.

Comment fait-on cela? En général, pour convertir d'une liste de bits en un entier, nous initialisons le résultat en 0puis parcourons les bits du plus grand au moins significatif, doublons la valeur que nous avons déjà et ajoutons le bit actuel. Par exemple, si le nombre binaire est 1011, nous calculerions vraiment:

(((0 * 2 + 1) * 2 + 0) * 2 + 1) * 2 + 1 = 11
           ^        ^        ^        ^

Où j'ai marqué les bits individuels pour plus de clarté.

L'astuce pour le faire en unaire est a) que doubler signifie simplement répéter le nombre et b) puisque nous comptons les 1s à la fin, nous n'avons même pas besoin de distinguer 0s et 1s dans le processus. Cela deviendra plus clair dans une seconde.

Ce que fait le programme, c'est qu'il ajoute d'abord une virgule au début comme marqueur de la quantité d'entrée que nous avons déjà traitée:

^
,

À gauche du marqueur, nous aurons la valeur que nous accumulons (qui est correctement initialisée à la représentation unaire de zéro), et à droite de la valeur sera le bit suivant à traiter. Maintenant, nous appliquons la substitution suivante dans une boucle:

,(.)
$`$1,

Il suffit de regarder ,(.)et $1,cela déplace le marqueur d'un bit vers la droite à chaque fois. Mais nous insérons également $`, qui est tout ce qui se trouve devant le marqueur, c'est-à-dire la valeur actuelle, que nous doublons. Voici les étapes individuelles lors du traitement de l'entrée 1011, où j'ai marqué le résultat de l'insertion $`au-dessus de chaque ligne (il est vide pour la première étape):

,1011

1,011
 _
110,11
   ___
1101101,1
       _______
110110111011011,

Vous verrez que nous avons conservé et doublé le zéro avec tout le reste, mais comme nous les ignorons à la fin, peu importe la fréquence à laquelle nous les avons doublés, tant que le nombre de 1s est correct. Si vous les comptez, il y a11 en a, exactement ce dont nous avons besoin.

Cela laisse donc la question de savoir comment jouer au golf à 12 octets. La partie la plus chère de la version 18 octets doit utiliser le marqueur. Le but est de s'en débarrasser. Nous voulons vraiment doubler le préfixe de chaque bit, donc une première idée pourrait être la suivante:

.
$`$&

Le problème est que ces substitutions se produisent simultanément, donc le premier bit n'est pas doublé pour chaque bit, mais il est copié une seule fois à chaque fois. Pour l'entrée, 1011nous obtiendrions (marquant l'inséré $`):

 _ __ ___
1101011011

Nous devons toujours traiter l'entrée de manière récursive afin que le premier préfixe doublé soit à nouveau doublé par le second et ainsi de suite. Une idée est d'insérer des marqueurs partout et de les remplacer à plusieurs reprises par le préfixe:

\B
,
+%`,
¶$`

Après avoir remplacé chaque marqueur par le préfixe pour la première fois, nous devons nous rappeler où se trouvait le début de l'entrée.Nous insérons donc également les sauts de ligne et utilisons l' %option pour nous assurer que le prochain $`ne récupère que le saut de ligne le plus proche.

Cela fonctionne, mais c'est encore trop long (16 octets lors du comptage de 1s à la fin). Et si on retournait les choses? Les endroits où nous voulons insérer des marqueurs sont identifiés par \B(une position entre deux chiffres). Pourquoi ne pas simplement insérer des préfixes dans ces positions? Cela fonctionne presque, mais la différence est que dans la solution précédente, nous avons en fait supprimé un marqueur dans chaque substitution, et c'est important pour mettre fin au processus. Cependant, ce \Bne sont pas des personnages mais seulement des positions, donc rien n'est supprimé. On peut cependant arrêter le\Bde la correspondance en insérant à la place un caractère non numérique à cet endroit. Cela transforme la frontière non mot en une frontière de mot, ce qui équivaut à supprimer le caractère marqueur plus tôt. Et c'est ce que fait la solution à 12 octets:

+%`\B
¶$`:

Juste pour être complet, voici les différentes étapes du traitement 1011, avec une ligne vide après chaque étape:

1
1:0
10:1
101:1

1
1:0
1
1:0:1
1
1:0
10:1:1

1
1:0
1
1:0:1
1
1:0
1
1:0:1:1

Encore une fois, vous constaterez que le dernier résultat contient exactement 11 1s.

Comme exercice pour le lecteur, pouvez-vous voir comment cela se généralise assez facilement à d'autres bases (pour quelques octets supplémentaires par incrément dans la base)?

Martin Ender
la source
2

T-SQL, 202 octets

DECLARE @b varchar(max)='1',@ int=1 declare @l int=LEN(@b)declare @o bigint=CAST(SUBSTRING(@b,@l,1)AS bigint)WHILE @<@l BEGIN SET @o=@o+POWER(CAST(SUBSTRING(@b,@l-@,1)*2AS bigint),@)SET @=@+1 END PRINT @o
Nelz
la source
2

PHP, 64 octets

foreach(str_split(strrev($argv[1]))as$k=>$v)$t+=$v*2**$k;echo$t;

Nous inversons notre nombre binaire, le divisons en ses chiffres composants et les additionnons en fonction de la position.

Xanderhall
la source
2

Utilitaires Bash + GNU, 29 octets

sed 's/./2*&+/g;s/.*/K&p/'|dc

E / S via stdin / stdout.

L' sedexpression divise le binaire en chaque chiffre et construit une expression RPN pour dcévaluer.

Trauma numérique
la source
2

PowerShell v2 +, 55 octets

param($n)$j=1;$n[$n.length..0]|%{$i+=+"$_"*$j;$j*=2};$i

Cela semble trop long ... Je n'arrive pas à jouer au golf - des conseils appréciés.

Explication

param($n)$j=1;$n[$n.length..0]|%{$i+=+"$_"*$j;$j*=2};$i
param($n)$j=1;                                          # Take input $n as string, set $j=1
              $n[$n.length..0]                          # Reverses, also converts to char-array
                              |%{                  };   # Loop over that array
                                 $i+=+"$_"*$j;          # Increment by current value of $j times current digit
                                              $j*=2     # Increase $j for next loop iteration
                                                     $i # Leave $i on pipeline
                                                        # Implicit output
AdmBorkBork
la source
2

JavaScript (ES6), 32 octets

f=([...n])=>n+n&&+n.pop()+2*f(n)

La récursion sauve à nouveau le jour! Bien que le paramétrage semble un peu long ...

ETHproductions
la source
Puisqu'il s'agit d'un seul "argument", doit- [...n]il être entouré de parenthèses?
Cyoce
@Cyoce Malheureusement, oui, ou JS lance une SyntaxError.
ETHproductions
2

Mathematica, 27 13 11 octets

Fold[#+##&]

Accepte un Listde bits comme entrée (par exemple {1, 0, 1, 1, 0}- représentation binaire de Mathematica du nombre 22)

JungHwan Min
la source
Dans le prolongement du commentaire sur la réponse de Greg, en quoi le «fractionnement de tous les chiffres dans l'entrée» n'est-il pas une fonction de conversion de base?
Martin Ender
@MartinEnder Je l'utilise comme la Charactersfonction.
JungHwan Min
@MartinEnder En fait, comme on le voit dans la réponse de @ nimi , je pourrais simplement accepter une liste de 1 et de 0 parce que c'est la seule façon de représenter un nombre binaire dans Mathematica , ce qui signifie que je n'ai pas besoin IntegerDigitsen premier lieu.
JungHwan Min
Cela suppose que la base 10 est la représentation "naturelle" d'un entier. Une valeur entière réelle n'a pas de base préférée attachée (je suppose que vous pourriez dire que la façon dont elle est stockée est probablement la base 256 ou peut-être même la base 2, mais c'est un détail d'implémentation). Ce n'est pas parce que nous utilisons (normalement) la base 10 pour écrire des littéraux entiers que les valeurs entières sont déjà en base 10.
Martin Ender
@MartinEnder @ Lynn utilise le code JellyD , qui fait la même chose queIntegerDigits
JungHwan Min
2

Clojure, 114 105 63 41 octets

V4: 41 octets

-22 octets grâce à @cliffroot. Puisqu'il digits'agit d'un caractère, il peut être converti en son code via int, puis en soustraire 48 pour obtenir le nombre réel. La carte a également été prise en compte. Je ne sais pas pourquoi cela semblait nécessaire.

#(reduce(fn[a d](+(* a 2)(-(int d)48)))%)

V3: 63 octets

(fn[s](reduce #(+(* %1 2)%2)(map #(Integer/parseInt(str %))s)))

-42 octets (!) En jetant un œil à d'autres réponses. Ma "fermeture éclair" était évidemment très naïve. Au lieu d'élever 2 à la puissance de l'endroit actuel, puis de le multiplier par le chiffre actuel et d'ajouter le résultat à l'accumulateur, il multiplie simplement l'accumulateur par 2, ajoute le chiffre actuel, puis l'ajoute à l'accumulateur. Converti également la fonction de réduction en macro pour raser un peu.

Merci à @nimi et @Adnan!

Ungolfed:

(defn to-dec [binary-str]
  (reduce (fn [acc digit]
            (+ (* acc 2) digit))
          (map #(Integer/parseInt (str %)) binary-str)))

V2: 105 octets

#(reduce(fn[a[p d]](+ a(*(Integer/parseInt(str d))(long(Math/pow 2 p)))))0(map vector(range)(reverse %)))

-9 octets en inversant la chaîne, donc je n'ai pas besoin de créer une plage décroissante maladroite.

V1: 114 octets

Eh bien, je ne gagne certainement pas! Pour ma défense, c'est le premier programme que j'ai jamais écrit qui convertit entre les bases, j'ai donc dû apprendre à le faire. Cela n'aide pas non plus à Math/powrenvoyer un double qui nécessite une conversion à partir de, et Integer/parseIntn'accepte pas de caractère, donc le chiffre doit être encapsulé avant de passer.

#(reduce(fn[a[p d]](+ a(*(Integer/parseInt(str d))(long(Math/pow 2 p)))))0(map vector(range(dec(count %))-1 -1)%))

Zippe la chaîne avec un index décroissant représentant le numéro de lieu. Réduit la liste résultante.

Ungolfed:

(defn to-dec [binary-str]
  (reduce (fn [acc [place digit]]
            (let [parsed-digit (Integer/parseInt (str digit))
                  place-value (long (Math/pow 2 place))]
              (+ acc (* parsed-digit place-value))))
          0
          (map vector (range (dec (count binary-str)) -1 -1) binary-str)))
Carcigenicate
la source
#(reduce(fn[a b](+(* a 2)(-(int b)48)))0 %)version améliorée. Déplacement d'une mappartie du code directement dans reduce, modification de la méthode d'analyse des entiers, création d'une fonction externe avec une syntaxe lambda abrégée.
cliffroot
@cliffroot intpeut être utilisé pour analyser !? Cela va tomber comme 10 octets dans chaque défi que j'ai fait ici lol.
Carcigenicate
Oh, je vois ce que tu fais. Prendre le code ascii, puis soustraire pour obtenir la valeur. Je suppose que cela ne fonctionnerait que dans certaines circonstances. Eh bien, merci pour l'astuce.
Carcigenicate
2

Perl, 21 19 16 + 4 = 20 octets

-4 octets grâce à @Dada

Courez avec -F -p(y compris l'espace supplémentaire après le F). Canaliser les valeurs vers la fonction à l'aide deecho -n

$\+=$_+$\for@F}{

Courir comme echo -n "101010" | perl -F -pE '$\+=$_+$\for@F}{'

Je pense que cela est suffisamment différent de la réponse de @ Dada pour mériter sa propre entrée.

Explication:

-F                              #Splits the input character by character into the @F array
-p                              #Wraps the entire program in while(<>){ ... print} turning it into
while(<>){$\+=$_+$\for@F}{print}
                   for@F        #Loops through the @F array in order ($_ as alias), and...
          $\+=$_+$\             #...doubles $\, and then adds $_ to it (0 or 1)...
while(<>){              }       #...as long as there is input.
                         {print}#Prints the contents of $_ (empty outside of its scope), followed by the output record separator $\

Cela utilise mon algorithme personnel de choix pour la conversion binaire en décimal. Étant donné un nombre binaire, démarrez votre accumulateur à 0 et parcourez ses bits un par un. Doublez l'accumulateur à chaque bit, puis ajoutez le bit lui-même à votre accumulateur, et vous vous retrouvez avec la valeur décimale. Cela fonctionne parce que chaque bit finit par être doublé le nombre approprié de fois pour sa position en fonction du nombre de bits restants dans le nombre binaire d'origine.

Gabriel Benamy
la source
Encore plus court:perl -F -pE '$\+=$_+$\for@F}{'
Dada
Honnêtement, j'ai ri à quel point c'est court maintenant. Merci.
Gabriel Benamy
Oui, c'est assez soigné, bravo!
Dada
2

R (32 bits), 64 octets

L'entrée de la fonction doit être donnée sous forme de caractère. Les fonctions de base de R prennent en charge les entiers 32 bits.

Contribution:

# 32-bit version (base)
f=function(x)sum(as.double(el(strsplit(x,"")))*2^(nchar(x):1-1))
f("1")
f("10")
f("101010")
f("1101111111010101100101110111001110001000110100110011100000111")

Sortie:

> f("1")
[1] 1
> f("10")
[1] 2
> f("101010")
[1] 42
> f("1101111111010101100101110111001110001000110100110011100000111")
[1] 2.016121e+18

R (64 bits), 74 octets

L'entrée de la fonction doit être donnée sous forme de caractère. Le package bit64doit être utilisé pour les entiers 64 bits.

Contribution:

# 64-bit version (bit64)
g=function(x)sum(bit64::as.integer64(el(strsplit(x,"")))*2^(nchar(x):1-1))
g("1")
g("10")
g("101010")
g("1101111111010101100101110111001110001000110100110011100000111")

Sortie:

> g("1")
integer64
[1] 1
> g("10")
integer64
[1] 2
> g("101010")
integer64
[1] 42
> g("1101111111010101100101110111001110001000110100110011100000111")
integer64
[1] 2016120520371234567
Djhurio
la source
2
Vous pouvez faire: el(strsplit(x,""))au lieu de strsplit(x,split="")[[1]]sauvegarder quelques octets.
Billywob
Merci beaucoup! Surtout pour la elfonction - je n'étais pas au courant.
djhurio
2

Dyalog APL , 12 octets

(++⊢)/⌽⍎¨⍞

obtenir une entrée de chaîne

⍎¨ convertir chaque caractère en nombre

sens inverse

(... )/insérer la fonction suivante entre les chiffres

++⊢ la somme des arguments plus le bon argument


ngn rasé 2 octets.

Adam
la source
1

k, 8 octets

Même méthode que la réponse Haskell ci-dessus.

{y+2*x}/

Exemple:

{y+2*x}/1101111111010101100101110111001110001000110100110011100000111b
2016120520371234567
Skeevey
la source