Zählen Sie die Anzahl der Einsen in einer 16-Bit-Ganzzahl ohne Vorzeichen

24

Schreiben Sie einige Anweisungen, die die Anzahl der Einsen in einer vorzeichenlosen 16-Bit-Ganzzahl zählen.

Wenn zum Beispiel die Eingabe ist 1337, dann ist das Ergebnis, 6weil es sich 1337um eine 16-Bit-Binärzahl handelt 0000010100111001, die sechs Einsen enthält.

Ayane
quelle
2
Tipp: So wie einige Ziffern einer Zahl mit der Zahl mod 9 übereinstimmen, entsprechen einige Bits der Zahl mod 1.
PyRulez
8
@ PyRulez Jede Zahl ist null Modulo 1.
Thomas
1
Hallo, Sie haben eine falsche Antwort als akzeptierte Antwort gewählt (standardmäßig die Gleichstandslogik des frühesten Beitrags).
Optimierer
4
@Thomas Ich habe nie gesagt, dass es ein hilfreicher Tipp ist.
PyRulez
2
Warum zieht diese Frage enge Abstimmungen an, NACHDEM die meisten Antworten veröffentlicht wurden? Nahe Wähler geben Sie bitte in den Kommentaren Ihren Grund an. Wenn es die Akzeptanz der (sehr cleveren) 4-Byte-Antwort von es1024 ist, die nicht den Standardlücken entspricht (weil sie eine eingebaute Funktion verwendet), geben Sie bitte an, dass dies der Grund ist. Ansonsten, was ist das?
Level River St

Antworten:

37

80386 Maschinencode, 4 Bytes

F3 0F B8 C1

Dies nimmt die ganze Zahl in cxund gibt die Anzahl in aus axund ist äquivalent zu:

popcnt ax, cx     ; F3 0F B8 C1

Und hier ist eine 11 10- Byte-Lösung ohne POPCNT:

31 C0 D1 E9 10 E0 85 C9 75 F8

was äquivalent ist zu:

xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
test cx, cx       ; 85 C9   Check if cx == 0
jnz $-6           ; 75 F8   Jump up to shr cx, 1 if not
es1024
quelle
Befindet sich dies im 32-Bit- oder 16-Bit-Modus (entweder im Real- oder im geschützten Modus)?
FUZxxl
2
@FUZxxl Die bereitgestellte Assembly ist für 16-Bit vorgesehen, ersetzt axund cxmit eaxund ecxändert sie jedoch in 32-Bit. Der Bytecode ist für beide gleich.
es1024
1
@ es1024 Der Bytecode ist der gleiche, wenn dieser im 16-Bit-Modus und die 32-Bit-Version im 32-Bit-Modus kompiliert wurde.
Cole Johnson
2
Ist Popcnt nicht ein eingebauter und damit von Standard-Schlupflöchern befallen? Trotzdem die zweite Lösung.
Alchymist
5
Wenn Sie die Länge des Maschinencodes angeben , sollte der Titel nicht "80386 Machine Code", nicht "80386 Assembler" lauten?
Kevin Reid
14

Python 2, 17 Bytes

bin(s).count('1')

Die binintegrierte Funktion gibt die Ganzzahl zurück, die in eine Binärzeichenfolge konvertiert wurde. Wir zählen dann die 1Ziffern:

>>> s=1337
>>> bin(s)
'0b10100111001'
>>> bin(s).count('1')
6
Logik-Ritter
quelle
11

J (5 Zeichen)

J hat keine expliziten Typen. Dies macht das Richtige für alle ganzen Zahlen.

+/@#:
  • +/ die Summe
  • @ von
  • #: die Basis zwei Darstellung
FUZxxl
quelle
11

C 21

for(n=0;x;n++)x&=x-1;

Sie sagten "Schreiben Sie einige Anweisungen" (nicht "eine Funktion"), also habe ich angenommen, dass die Zahl in geliefert wird xund die Zahl von Einsen in zurückgegeben wird n. Wenn ich nicht initialisieren muss, nkann ich 3 Bytes sparen.

Dies ist eine Adaption des berühmten Ausdrucks x&x-1zum Testen, ob etwas eine Potenz von 2 ist (falsch, wenn es ist, wahr, wenn es nicht ist).

Hier ist es in Aktion auf die Nummer 1337 aus der Frage. Beachten Sie, dass durch Subtrahieren von 1 das niedrigstwertige 1-Bit und alle Nullen nach rechts gekippt werden.

0000010100111001 & 0000010100111000 = 0000010100111000
0000010100111000 & 0000010100110111 = 0000010100110000
0000010100110000 & 0000010100101111 = 0000010100100000
0000010100100000 & 0000010100011111 = 0000010100000000
0000010100000000 & 0000010011111111 = 0000010000000000
0000010000000000 & 0000001111111111 = 0000000000000000

EDIT: Der Vollständigkeit halber hier der naive Algorithmus, der ein Byte länger (und einiges langsamer) ist.

for(n=0;x;x/=2)n+=x&1;
Level River St
quelle
1
@ edc65 Wie sich herausstellt, habe ich das Rad neu erfunden. Zumindest habe ich 2 Bytes gespart, indem ich das weggelassen habe {}. Es ist eine so einfache Aufgabe, dass ich mich nicht wundern sollte, wenn jemand sie schon erfunden hat.
Level River St
"Erstmals 1960 veröffentlicht" , beeindruckend.
mbomb007
Korrektur des naiven Algorithmus:for(n=0;x;x/=2)n+=x&1;
Helios
1
@nmxprime das OP fragt nach vorzeichenlosen int. Für -7 = 11111111 11111111 11111111 11111001 auf meinem 32-Bit-Compiler erhalte ich 30 für den schnellen Algorithmus, was korrekt ist. Für den naiven Algorithmus durchläuft er -7, -7 / 2 = -3, -3 / 2 = -1, -1 / 2 = 0. Das gibt eine falsche Antwort. Wenn Sie x / = 2 in x >> = 1 ändern, erhalten Sie auf einigen Compilern möglicherweise die richtige Antwort, aber C ist nicht definiert, ob bei negativen Zahlen eine 1 oder eine 0 in das leere Bit für >> verschoben wird. Diejenigen Compiler, die eine 1 in verschieben, gehen in eine Endlosschleife. Die Problemumgehung besteht darin, x als vorzeichenlosen int zu definieren. Dann lädt x = -7 (1 << 32) -7 = 4294967289 in x.
Level River St
5

Gelee , nicht konkurrierend

Diese Antwort ist nicht konkurrierend, da die Sprache erstellt wurde, nachdem die Herausforderung veröffentlicht wurde.

2 Bytes:

BS

Jelly ist eine neue Sprache von @Dennis mit J-ähnlicher Syntax.

         implicit: function of command-line arguments
B        Binary digits as list
 S       Sum

Probieren Sie es hier aus .

Lirtosiast
quelle
4

Pyth, 4 Bytes

sjQ2

Das Programm verwendet die Nummer, deren Hamming-Gewicht sich auf STDIN befindet.

isaacg
quelle
4

Julia, 29 27 19 Bytes

n->sum(digits(n,2))

Dadurch wird eine anonyme Funktion erstellt, die ein einzelnes Argument akzeptiert n. Um es zu benutzen, weisen Sie es so etwas wie f=n->...und nennen Sie es so f(1337).

digits()Wenn die Funktion mit 2 Argumenten aufgerufen wird, gibt sie ein Array der Ziffern der Eingabe in der angegebenen Basis zurück. So digits(n, 2)gibt die binären Ziffern n. Nehmen Sie die Summe des Arrays und Sie haben die Anzahl der Einsen in der binären Darstellung von n.

Alex A.
quelle
Dies kann viel kürzer sein: Julia hat eine Funktioncount_ones
Andrew sagt Reinstate Monica
@AndrewPiliser: Danke für den Vorschlag, aber eingebaute Funktionen, die genau die Aufgabe erfüllen, gelten als Standardlücke und werden verpönt, wenn sie nicht ausdrücklich verboten sind.
Alex A.
3

CJam, 6 Bytes

ri2b:+

ri         "Read the input and convert it to integer";
  2b       "Convert the integer into base 2 format";
    :+     "Sum the digits of base 2 form";

Probieren Sie es hier online aus

Optimierer
quelle
3

Joe , 4 Bytes

/+Ba

Dies ist eine anonyme Funktion. Bagibt die binäre Darstellung einer Zahl und /+summiert sie.

   (/+Ba)13
3
   (/+Ba)500
6
seequ
quelle
3

R, 24 Bytes

sum(intToBits(scan())>0)

scan() Liest die Eingabe von stdin.

intToBits()Nimmt eine Ganzzahl und gibt einen Vektor vom Typ zurück raw, der die Nullen und Einsen der Binärdarstellung der Eingabe enthält.

intToBits(scan())>0gibt einen logischen Vektor zurück, wobei jedes Element ist, TRUEwenn das entsprechende binäre Vektorelement eine 1 ist (da alle Elemente 0 oder 1 und 1> 0 sind), andernfalls FALSE.

In R können Sie einen logischen Vektor TRUEaddieren , um die Anzahl der Elemente zu erhalten. Wenn Sie also den Vektor der logischen Elemente wie oben summieren, erhalten Sie das, was wir wollen.

Beachten Sie, dass Eingaben nicht direkt sum()verarbeitet rawwerden können, daher die Problemumgehung mit logischen Elementen.

Alex A.
quelle
Wäre das nicht sum(intToBits(scan()))dasselbe?
Siehe auch
@Sieg: Leider nein, da sum()keine Eingabe des Typs möglich rawist, von dem das zurückgegeben wird intToBits().
Alex A.
Das ist wirklich komisch für mich.
Siehe auch
1
@Sieg: Ja, es ist auch komisch für mich. Naja. Wenn jedes Schweinefleisch perfekt wäre, hätten wir keine Hotdogs.
Alex A.
Und das ist die seltsamste Metapher aller Zeiten.
Siehe auch
3

Ruby, 18 Bytes

n.to_s(2).count'1'

GreyCat
quelle
1
n.to_s(2).count ?1funktioniert auch, ist aber die gleiche Länge
Piccolo
2019 version: n.digits (2) .sum / 15 bytes
GB
3

Viertens 48 49 Bytes

: c ?dup if dup 1- and recurse 1+ then ;
0 1337 c

Wenn eine tatsächliche Funktion benötigt wird, wird die zweite Zeile

: c 0 swap c ;

und Sie nennen es "1337 c". Forths relativ wortreiche Kontrollwörter machen dies schwierig (tatsächlich machen sie eine Menge davon schwierig).

Bearbeiten: Meine vorherige Version hat negative Zahlen nicht richtig verarbeitet.

Nagora
quelle
3

Mathematica, 22 18 Bytes

Vielen Dank an Alephalpha, der mich daran erinnert hat DigitCount.

DigitCount[#,2,1]&
Martin Ender
quelle
@alephalpha danke, aber DigitCount nimmt einen anderen Parameter :)
Martin Ender
3

ES6 (34 22 21 Bytes):

Dies ist eine einfache rekursive Funktion, die noch etwas gekürzt werden kann. Es dauert einfach ein bisschen und läuft selbst wieder:

B=n=>n&&(1&n)+B(n>>1)

Probiere es auf http://www.es6fiddle.net/imt5ilve/ aus (brauchst du das varwegen 'use strict';).

Ich kann nicht glauben, dass ich Fisch geschlagen habe !!!

Das Alte:

n=>n.toString(2).split(1).length-1

ES5 (39 Byte):

Beide Funktionen können problemlos an ES5 angepasst werden:

function B(n){return n?(1&n)+B(n>>1):0}

//ungolfed:

function B(number)
{
    if( number > 0 )
    {
        //arguments.callee points to the function itself
        return (number & 1) + arguments.callee( number >> 1 );
    }
    else
    {
        return 0;
    }
}

Alte:

function(n){return n.toString(2).split(1).length-1}

@ user1455003 hat mir eine wirklich gute Idee gegeben, die die kleinste ausgelöst hat:

function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

Ich habe es an ES6 angepasst und es rekursiv gemacht, um viel zu verkürzen!

Ismael Miguel
quelle
1
Hier ist eine kleinere "Reguar" Javascript-Funktion. Funktion B (n, x) {für (x = 0; n; n >> = 1) x + = n & 1; Rückgabe x}
Wolfhammer
@ user1455003 Vielen Dank oder Ihren Vorschlag! Ich habe es benutzt und an ES6 angepasst und viel gekürzt. Vielen Dank!
Ismael Miguel
Herzlich willkommen! Ich mag, was du damit gemacht hast. Mit der Rekursion ist reguläres Javascript auf 39! Funktion B (n) {return n? (1 & n) + B (n >> 1): 0}
Wolfhammer
@ user1455003 Wenn Sie möchten, können Sie den ES5-Teil bearbeiten und die Byteanzahl zur Golfversion hinzufügen. (Ich denke, Sie gewinnen Ruf mit Änderungen).
Ismael Miguel
@ user81655 WOW! Es klappt!!! Vielen Dank! Ich wusste wirklich, dass dies kürzer gemacht werden könnte
Ismael Miguel
2

> <> (Fisch) , 24 Bytes + 2 = 26

0$11.>~n;
2,:?!^:2%:{+}-

Das Programm wiederholt nur Mod 2, subtrahiert und dividiert, bis die eingegebene Zahl Null wird, und gibt dann die Summe der Mod 2s aus.

Testen Sie mit der -vFlagge, z

py -3 fish.py ones.fish -v 1337
Sp3000
quelle
Für eine 16-Bit-Ganzzahl ist die Codepunkteingabe wahrscheinlich nicht ausreichend. (Die -vFlaggenversion funktioniert immer noch.)
randomra
@randomra Verdammt, du hast recht. Während die Unicode-Eingabe funktioniert, liegt 16-Bit nur um einige Größenordnungen außerhalb des
gültigen
2

PHP (38 Bytes):

Dies verwendet den gleichen Ansatz wie meine ES6-Antwort

<?=count(split(1,decbin($_GET[n])))-1;

Dies ist ein vollständiger Code, Sie müssen ihn nur in eine Datei einfügen und über den Browser mit dem Parameter darauf zugreifen n=<number>.

PHP <4.2 (32 Bytes):

Das ist etwas kürzer:

<?=count(split(1,decbin($n)))-1;

Dies funktioniert nur dann zuverlässig auf PHP <4.2 , da die Richtlinie register_globalsgesetzt wurde Offvon PHP4.2 standardmäßig bis zu PHP5.4 (das durch dann entfernt wurde).

Wenn Sie eine php.iniDatei mit erstellen register_globals=On, funktioniert dies.

Um den Code zu verwenden, greifen Sie über einen Browser mit POST oder GET auf die Datei zu.

@ViniciusMonteiros Vorschlag (38/45 Bytes):

Er gab zwei wirklich gute Vorschläge, die die Funktion sehr interessant nutzen array_sum:

38 Bytes:

<?=array_sum(str_split(decbin(1337)));

45 Bytes:

<?=array_sum(preg_split('//', decbin(1337)));

Dies ist eine wirklich großartige Idee und kann ein wenig gekürzt werden, um 36 Bytes lang zu sein:

<?=array_sum(split(1,decbin(1337)));
Ismael Miguel
quelle
2
Oder Sie können echo array_sum (str_split (decbin (1337))) verwenden. und du kannst auch echo array_sum (preg_split ('//', decbin (1337));
Vinicius Monteiro
1
@ViniciusMonteiro Vielen Dank für Ihren Vorschlag. Ich habe es wirklich geliebt! Ich habe es der Antwort hinzugefügt.
Ismael Miguel
Gewinnen Sie vier Bytes mit <?=substr_count(decbin(1337),"1");(34 Bytes)
Cogicero
1
@Cogicero Und Sie können durch Entfernen der Anführungszeichen noch mehr sparen: <?=substr_count(decbin(1337),1);. Das sind insgesamt 32 Bytes. Wenn Sie bedenken, dass es sich um einen ausreichend unterschiedlichen Code handelt, möchten Sie ihn nicht als Ihre eigene Antwort veröffentlichen? Ich werde es auf jeden Fall unterstützen!
Ismael Miguel
@Cogicero Es ist nur zwei Bytes kürzer, wenn Sie Parametrisierung verwenden: <?=substr_count(decbin($argv[1]),1);(oder $_GET[n]; 36 Bytes)
Titus
2

C #, 45 Bytes

Convert.ToString((ushort)15,2).Sum(b=>b-48);

https://dotnetfiddle.net/kJDgOY

albertjan
quelle
b-48ist noch kürzer, AFAIK
ThreeFx
Richtig! :) Ich werde aktualisieren.
Albertjan
2

Japt, 3 Bytes (nicht konkurrenzfähig)

¢¬x

Probieren Sie es hier aus.

Mama Fun Roll
quelle
Mann, ich sehe diese Daten aus irgendeinem Grund nie.
Mama Fun Roll
1
Haha, Japt ist am kürzesten: D Übrigens, ¢o1 lwürde auch funktionieren. Ein weiterer interessanter Ansatz ist -¢¬r-0; ¢¬Teilt sich in ein Array von Binärziffern, r-0reduziert sich durch Subtraktion ab 0 und -negiert das Ergebnis, wodurch es positiv wird.
ETHproductions
Ab letzter Nacht können Sie jetzt verwenden ¢¬x.
ETHproductions
2

Bienenwachs ,31 27 Bytes

Nicht konkurrierende Antwort. Bienenwachs ist neuer als diese Herausforderung.

Diese Lösung verwendet Brian Kherigans Methode, um gesetzte Bits von der Website „Bit Twiddling Hacks“ zu zählen.

Es wird nur eine Schleife durchlaufen, wobei die Anzahl der Bits erhöht wird, während durch number=number&(number-1)bis iteriert wird number = 0. Die Lösung durchläuft die Schleife nur so oft, wie Bits gesetzt sind.

Ich könnte 4 Bytes weg rasieren, indem ich einige Anweisungen neu anordnete. Sowohl der Quellcode als auch die Erklärung wurden aktualisiert:

pT_
>"p~0+M~p
d~0~@P@&<
{@<

Erläuterung:

pT_            generate IP, input Integer, redirect
>"             if top lstack value > 0 jump next instruction,
               otherwise continue at next instruction
  p            redirect if top lstack value=0 (see below)
   ~           flip top and 2nd lstack values
    0+         set top lstack value to 0, set top=top+2nd
      M        decrement top lstack value
       ~       flip top and 2nd lstack values
        p      redirect to lower left
        <      redirect to left
       &       top=top&2nd
      @        flip top and 3rd lstack values
    @P         increment top lstack value, flip top and 3rd values
 ~0~           flip top and 2nd values, set top=0, flip top and 2nd again
d              redirect to upper left
>"p~0+M.....   loop back

  p            if top lstack = 0 at " instruction (see above), redirect
  0            set lstack top to zero (irrelevant instruction)
  <            redirect to the left
 @             flip top and 3rd lstack values
{              output top lstack value as integer (bitcount)

Klonen Sie mein GitHub-Repository mit dem Bienenwachs-Interpreter, den Sprachspezifikationen und Beispielen.

ML
quelle
1

Java, 17 Bytes

Arbeitet für byte, short, char, und int. Verwenden Sie als Lambda.

Integer::bitCount

Hier testen

Ohne Verwendung von integrierten Funktionen:

42 Bytes

s->{int c=0;for(;s!=0;c++)s&=s-1;return c}

Hier testen

Die Nummer eins
quelle
6
Dies ist eine Standardlücke: Integrierte Funktionen, die genau das tun, was Sie wollen, sind verboten.
FUZxxl
@FUZxxl Die OP verbot nie Standard-Schlupflöcher
Cole Johnson
1
@ColeJohnson Standard-
es1024
6
@FUZxxl Während es1024 richtig ist, dass die Standardlücken standardmäßig geschlossen sind, ist die Verwendung integrierter Funktionen derzeit keine akzeptierte Lücke bei einer Abstimmungsaufschlüsselung von + 43 / -26.
Martin Ender
1

Clip , 6

2 Wege:

cb2nx1

Dies ist eine einfache Übersetzung der Anforderung: die Anzahl der Einsen in der Zahlendarstellung zur Basis 2.

r+`b2n

Eine andere Methode, bei der die Summe der Ziffern der Basis-2-Darstellung verwendet wird.

Ypnypn
quelle
1

Oktave, 18

sum(dec2bin(s)-48)

Beispiel:

octave:1> s=1337
s =  1337
octave:2> sum(dec2bin(s)-48)
ans =  6
Alephalpha
quelle
1

GML (Game Maker Language), 21 Byte

for(n=0;x;n/=2)n+=x&1
Timtech
quelle
1

C # 39 Bytes

Convert.ToString(X,2).Count(C=>C=='1');
sbecker
quelle
1

Perl, 21

$r=grep$v&1<<$_,0..15
nutki
quelle
1

PowerShell (51 Byte)

"$([char[]][convert]::ToString($s,2)|%{"+$_"})"|iex

Erläuterung:
[convert]::ToString($s,2)Erzeugt eine binäre Zeichenfolgendarstellung von $s.
[char[]]Wirft es in ein Zeichen-Array und ermöglicht es uns, jedes Zeichen aufzuzählen.
|%{"+$_"}stellt jedem Zeichen ein + voran und
"$()"ruft implizit .ToString()den resultierenden Unterausdruck auf, der
|iexdie weitergeleitete Zeichenfolge summiert (dh "+1 +0 +1 +1 +0 +1 +0 +0" = 4)

Mathias R. Jessen
quelle
Hiya! Nach der gleichen Logik, die Sie haben, warum nicht den Inline- -joinOperator und ein implizites verwenden .ToString(), um 45 Bytes mit [char[]][convert]::ToString($s,2)-join'+'|iex... OR zu erreichen , als einen anderen Ansatz verwenden Sie den Inline- -replaceOperator, um 43 Bytes mit([convert]::ToString($s,2)-replace0).length
AdmBorkBork
1

Clojure, 42 Bytes

#(count(filter #{\1}(Long/toString % 2)))

Lesen Sie von rechts nach links, konvertieren Sie in eine Binärzeichenfolge, konvertieren Sie in eine Zeichenfolge, filtern Sie nach 1s und zählen Sie, wie viele Sie haben.

BEARBEITET Mit Hilfe von Sieg

Neil Masson
quelle
42:#(count(filter #{\1}(Integer/toString% 2)))
Siehe auch
Sie brauchen noch einen Charakter#(count(filter #{\1}(Integer/toString % 2)))
Neil Masson
Nein, tust du nicht. :)
siehe auch
Das habe ich bekommen, als ich es ausprobiert habe:CompilerException java.lang.IllegalArgumentException: No matching method: toString_PERCENT_
Neil Masson
Ich habe es in Try Clojure getestet. Anscheinend erkennt die Seite plötzlich nicht mehr Integer/toString. Es hat aber vor einer Sekunde funktioniert.
Siehe auch
1

Haskell 42 Zeichen

t 0=[]
t n=t(quot n 2)++[rem n 2]
f=sum.t

deklariert die f :: Integer -> Integer
Verwendung der Funktion vom interaktiven Interpreter als f <number>oder fügt die Zeile main=print$f <number>am Ende der Datei hinzu.

HEGX64
quelle
Sie können eine Menge Bytes sparen, indem Sie das rem n 2s direkt summieren, anstatt eine Liste davon zu erstellen, und indem Sie divanstelle von quot: t 0=0 t n=t(div n 2)+rem n 2- no fmore verwenden.
Nimi
1

Matlab, 13 Bytes

de2biErstellt einen Vektor aus Nullen und Einsen, der die Binärzahl darstellt, und gibt sumnur die Summe aller Einträge zurück.

sum(de2bi(n))
Fehler
quelle
1

𝔼𝕊𝕄𝕚𝕟, 4 Zeichen / 11 Bytes (nicht konkurrierend)

⨭⟦ïⓑ

Try it here (Firefox only).

Erläuterung

Wandelt die Eingabe in eine Binärdatei um, teilt sie entlang der Zeichen und ruft die Summe des resultierenden Arrays ab.

Mama Fun Roll
quelle