Eine Ganzzahl ist binärlastig, wenn ihre Binärdarstellung mehr 1
s als 0
s enthält und führende Nullen ignoriert werden. Zum Beispiel ist 1 binärlastig, da seine binäre Darstellung einfach ist 1
, 4 ist jedoch nicht binärlastig, wie seine binäre Darstellung ist 100
. Im Falle eines Unentschiedens (zum Beispiel 2 mit einer binären Darstellung von 10
) wird die Zahl nicht als binärlastig betrachtet.
Bei einer positiven Ganzzahl als Eingabe wird ein wahrer Wert ausgegeben, wenn er binär ist, und ein falscher Wert, wenn er nicht ist.
Testfälle
Format: input -> binary -> output
1 -> 1 -> True
2 -> 10 -> False
4 -> 100 -> False
5 -> 101 -> True
60 -> 111100 -> True
316 -> 100111100 -> True
632 -> 1001111000 -> False
2147483647 -> 1111111111111111111111111111111 -> True
2147483648 -> 10000000000000000000000000000000 -> False
Wertung
Dies ist Code-Golf, so dass die wenigsten Bytes in jeder Sprache gewinnen
code-golf
number
decision-problem
binary
Skidsdev
quelle
quelle
Antworten:
x86-Maschinencode,
15 bis14 ByteDies ist eine Funktion, die die __fastcall-Aufrufkonvention von Microsoft verwendet (erster und einziger Parameter in ecx, Rückgabewert in eax, callee darf edx blockieren), obwohl sie trivial für andere Aufrufkonventionen geändert werden kann, die Argumente in Registern übergeben.
Es gibt 255 als wahr und 0 als falsch zurück.
Es verwendet den undokumentierten (aber weitgehend unterstützten) Opcode
salc
.Demontage unten:
Probieren Sie es online!
Dank Peter Cordes für die Annahme , ersetzt
lzcnt
mitbsr
.quelle
popcnt
vorgerückt, um nach Antworten zu suchen, hatte aber nicht daran gedacht, michlzcnt
nur mit den für die Frage erforderlichen signifikanten Ziffern zu befassen.bsr
vonlzcnt
(akarep bsr
) Nettoeinsparungen zu erzielen ? Sie müsstensub
statt verwenden,lea
da es Ihnen 32-lzcnt gibt. (Oder lässt das dst unverändert für src = 0 auf der gesamten vorhandenen Intel- und AMD-Hardware. AMD dokumentiert dieses Verhalten sogar, aber Intel sagt undefiniert ... Wie auch immer, OP sagte positiv , was ausschließt0
.)popcnt
und entworfenbsr
, aber es war 17 Bytes. Ich dachte, das wäre ziemlich gut im Vergleich zu der ersten Antwort, die ich gesehen habe , aber dieser cleverelea
Trick schlägt die Hose aus. Ich habe mir auch Vergleichenbsf
und angeschautpopcnt
. Aber ich sehe keine Möglichkeit, diese Lösung zu übertreffen, selbst wenn man das 1-Byte-Byte berücksichtigt, das Sie durch das Löschen desrep
Präfixes sparen könnten .salc
ist nicht gleichbedeutend mitsetc al
: Letzteres setztal
auf 1, wenn CF gesetzt ist, nicht auf 255.salc
istsbb al, al
, aber Sie erhalten eine Ersparnis von 1 Byte, um es zu codieren. By the way, es wird von AMD dokumentiert, und es ist weit von Intel unterstützt, mit dem mnemonic selbst kommt aus Intels P6 Opcodezuordnung. Dieser ist also ziemlich sicher zu bedienen. Auch schöne Verbesserung hier zu denken, um diese Anweisung zu verwenden! Dies ist im Grunde das, was mein ursprünglicher Entwurf getan hat, mit der Ausnahme, dass (1) ich x86-64-Code verwendet hatte, alsoinc
doppelt so lang für die Codierung war, und (2) ich nicht daran gedacht hattesalc
, also die gleiche Arbeit in a zu tun längerer Weg. Schade, dass ich nur einmal upvoten kann.Gelee , 5 Bytes
Ergibt eine nicht leere Ausgabe (wahr) oder eine leere Ausgabe (falsch).
Probieren Sie es online!
Wie es funktioniert
quelle
Bo-S
, aber ich konnte kein 1-Byte-Atom finden, das positiv / nicht positiv in wahr / falsch konvertieren würde ...Æṃ
damals nicht.Python 2 , 35 Bytes
Probieren Sie es online!
Alte Antwort, 38 Bytes
Ausgaben
0
als falsch und /-2
oder-1
als wahrProbieren Sie es online!
quelle
bin
Verursacht die führende 0 in der Rückkehr dieser Lösung Probleme?max
funktioniert. Im Falle eines Gleichstands gibt max den ersten Wert im Iterable zurück, der den Maximalwert hat. Dieser Code verwendet diese Tatsache, um sicherzustellen, dass im Falle eines Unentschieden 1 zurückgegeben wird, was tatsächlich bedeutet, dass es mehr Einsen als Nullen gibt, da eine zusätzliche Null durch hinzugefügt wurdebin
. Es wäre tatsächlich falsch, wenn es auf diese Weise geschrieben würde, wenn es nicht die zusätzliche Null gäbe.cmp
Renditen,0
wenn beide gleich sindOktave , 18 Bytes
TIO funktioniert nicht, da die Kommunikations-Toolbox nicht enthalten ist. Es kann auf Octave-Online getestet werden .
Wie das funktioniert:
de2bi
konvertiert eine Dezimalzahl in einen binären numerischen Vektor und nicht wiedec2bin
gewohnt in eine Zeichenfolge .mode
Gibt die häufigste Ziffer im Vektor zurück. Bei einem Unentschieden ist die Standardeinstellung die niedrigste.quelle
JavaScript (ES6),
3634 Bytesquelle
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0
für 35 Bytes.n>>1
stattn>>>1
, um ein Byte zu speichern, da die Eingabe niemals negativ ist.n/2|0
ist nicht besser: /MATL , 3 Bytes
Probieren Sie es online!
Ich kenne MATL nicht wirklich, habe nur gemerkt, dass
mode
es in der Octave-Antwort von alephalpha funktionieren könnte, und dachte, dass es in MATL eine Entsprechung gibt.quelle
Mathematica, 22 Bytes
Dank @MartinEnder und @JungHwanMin ein Byte gespart .
quelle
@@
.#>#2&@@#~DigitCount~2&
Brachylog , 6 Bytes
Probieren Sie es online!
Erläuterung
Da
ḃ
die Ausgabe niemals mit einer Liste von Ziffern mit führenden Nullen vereinheitlicht wird, wissen wir, dass die Vorkommen von1
immer an erster Stelle stehen und die Vorkommen von0
immer an zweiter Stelle stehenọ
.quelle
Python 3 ,
44(danke @ c-mcavoy) 40 BytesProbieren Sie es online!
quelle
C (gcc) ,
51484140 BytesProbieren Sie es online!
quelle
unsigned
n>>=1
zun/=2
. Ich denke auch , können Sie verwenden ,~n
anstattn^-1
, die Sie ermöglichen sollte , sich ändern&&
zu&
n
, und egal über die Änderung&&
zu&
, ich glaube nicht , dass das funktionieren würde. Aber es zu ändern*
scheint zu funktionieren&&
war nur, um den unsignierten Fall zu behandeln, aber da ich nur positive ganze Zahlen behandeln muss, kann ich alles zusammen entfernen. Gut, dass du/=
kürzer bist>>=
, danke!n&1?++i:--1
zui+=n%2*2-1
. Möglicherweise können Sie auch>0
feststellen, dass Sie Null für Heavy und Nicht-Null für Nicht-HeavyR ,
545351 Bytes-1 Byte danke an Max Lawnboy
liest von stdin; Gibt
TRUE
für binäre schwere Zahlen zurück.d
ist die Anzahl der Binärziffern;sum(n%/%2^(0:d)%%2
berechnet die Ziffernsumme (dh die Anzahl der Einsen).Probieren Sie es online!
quelle
log2(n)
anstattlog(n,2)
x86_64-Maschinencode,
232221 ByteZerlegt:
Danke @Ruslan, @PeterCordes für das
-1
Byte!Probieren Sie es online!
quelle
8d 1f
anstelle von verwenden89 fb
?add eax, 2
+ habendec eax
, aber Ihre Kommentare deuten darauf hin, dass Sie erhöhen möchtenebx
, nichteax
.jnz Next
/add
/dec
(7 Byte) mitlea -1(%rax, %rbx, 2), %eax
(4 Byte) zu tuneax += 2*ebx - 1
(wie in der anderen x86 - Computer-Code Antwort ). Dann außerhalb der Schleifeneg %eax
(2 Bytes), bevor das Vorzeichenbit nach unten verschoben wird. Nettoeinsparung von 1 Byte. Odertest %eax,%eax
/setge %al
würde auch funktionieren, wenn Ihr Rückgabewert einbool
oder istint8_t
.lea -1(%rax,rbx,2)
sondern nurlea -1(%eax,%eax,2)
und Bytes auf diese Weise verschwendet .. Wie auch immer, ihr beide hattet Recht, ich kann ein Byte wie dieses speichern. Vielen Dank (im Gegenzug werde ich daslea
auf einemov
Weile ändern, wenn ich dabei bin)!Perl 6 ,
32-30BytesProbier es aus
Probier es aus
Erweitert:
quelle
Wise ,
4039 BytesProbieren Sie es online!
Erläuterung
quelle
Haskell,
4134Wenn
n
ungerade ist, nimm a,-1
wenn es gerade ist, nimm a1
. Fügen Sie einen rekursiven Anruf mit hinzun/2
und stoppen Sie, wennn = 0
. Wenn das Ergebnis kleiner als0
die Zahl ist, ist es binärlastig.Probieren Sie es online!
Edit: @ Ørjan Johansen hat einige Verknüpfungen gefunden und 7 Bytes gespeichert. Vielen Dank!
quelle
mod n 2
kann gerecht seinn
, und es ist ein Byte kürzer ohne Akkumulator. Probieren Sie es online!Retina ,
37-34BytesProbieren Sie es online! Link enthält kleinere Testfälle (den größeren würde wahrscheinlich der Speicher ausgehen). Bearbeiten: 3 Bytes dank @MartinEnder gespeichert. Erläuterung: Die erste Stufe wird von dezimal nach unär konvertiert, und die nächsten beiden Stufen werden von unär nach binär konvertiert (dies ist fast direkt aus der unär arithmetischen Seite im Retina-Wiki heraus, außer dass ich
@
anstelle von verwende0
). Die dritte Stufe sucht nach Paaren unterschiedlicher Zeichen, die entweder@1
oder sein können1@
, und löscht sie, bis keine mehr übrig sind. Die letzte Stufe prüft dann auf verbleibende 1s.quelle
${1}
kann sein$+
. Oder Sie könnten verwenden!
statt0
und dann verkürzen01|10
zu.\b.
.$+
das, wenn das Muster a enthält|
? Ich frage mich, ob ich das vorher hätte benutzen können ...$+
ist super doof und benutzt einfach die gruppe mit der größten nummer, egal ob sie benutzt wurde oder nicht. Es ist nur zum Golfen nützlich, wenn Sie mehr als neun Gruppen haben oder in einer Situation wie der hier, und ich weiß nicht, warum ich es jemals in einer Produktions-Regex verwenden würde.R , 43 Bytes
Probieren Sie es online!
quelle
intToBits
Kotlin , 50 Bytes
Lambda impliziten Typs
(Int) -> Boolean
. Version 1.1 und höher nur aufgrund der Verwendung vonInt.toString(radix: Int)
.Leider scheint die Kotlin-Laufzeit von TIO 1.0.x zu sein, daher hier ein trauriger Hund anstelle eines TIO-Links:
quelle
Pyth,
97 BytesProbieren Sie es hier aus.
-2 danke an FryAmTheEggman .
quelle
>ysJjQ2lJ
.B
!)R,
3937 BytesHierbei handelt es sich um eine Kombination der von @MickyT und @Giuseppe verwendeten Methoden, wodurch einige weitere Bytes eingespart werden.
sum(intToBits(x) > 0)
zählt die Anzahl der1
Bits und2+log2(x)/2
ist die Hälfte der Gesamtanzahl der Bits, wenn abgerundet. Wir müssen nicht abrunden, weil die beiden Werte gleich sind.quelle
C # (.NET Core) ,
62, 49 BytesOhne LINQ.
BEARBEITEN: Dana mit einem -13-Byte-Golf, wobei die while-Anweisung in eine rekursive Anweisung geändert wird und ein Bool anstelle einer Ganzzahl zurückgegeben wird.
Probieren Sie es online!
quelle
Regex (ECMAScript),
857371 BytesProbieren Sie es online!
Erklärung per Deadcode
Die frühere 73-Byte-Version wird unten erklärt.
^((?=(x*?)\2(\2{4})+$)\2|(?=(x*?)(\4\4xx)*$)(\4|\5(x*)\7\7(?=\4\7$)\B))+$
Aufgrund der Einschränkungen von ECMAScript regex besteht eine effektive Taktik häufig darin, die Zahl schrittweise umzuwandeln, während die erforderliche Eigenschaft bei jedem Schritt unverändert bleibt. Wenn Sie beispielsweise auf ein perfektes Quadrat oder eine Zweierpotenz testen möchten, verringern Sie die Größe der Zahl, während Sie bei jedem Schritt ein Quadrat oder eine Zweierpotenz beibehalten.
Diese Lösung macht bei jedem Schritt Folgendes:
1
1
1
10
01
01
Wenn diese wiederholten Schritte nicht weiter ausgeführt werden können, ist das Endergebnis entweder eine zusammenhängende Folge von
1
Bits, die schwer ist, und zeigt an, dass die ursprüngliche Nummer ebenfalls schwer war, oder eine Potenz von 2, was anzeigt, dass die ursprüngliche Nummer nicht schwer war.Und obwohl diese Schritte oben im Hinblick auf typografische Manipulationen an der binären Darstellung der Zahl beschrieben wurden, werden sie natürlich tatsächlich als unäre Arithmetik implementiert.
quelle
\5
sind um eins versetzt). Ich habe dies untersucht und in meiner Antwort erklärt und kommentiert (da StackExchange keine mehrzeiligen Antworten zulässt).Regex (ECMAScript), 183 Bytes
Dies war ein weiteres interessantes Problem, das mit ECMA Regex gelöst werden konnte. Der "naheliegende" Weg, dies zu handhaben, besteht darin, die Anzahl der
1
Bits zu zählen und diese mit der Gesamtzahl der Bits zu vergleichen. In ECMAScript regex können Sie jedoch nicht direkt zählen. Das Fehlen dauerhafter Rückverweise bedeutet, dass in einer Schleife nur eine Nummer geändert und bei jedem Schritt nur verringert werden kann.Dieser unäre Algorithmus funktioniert wie folgt:
1
Bit an die niedrigstwertige Position, an der sich ein0
Bit befindet. Jeder dieser Schritte ist eine Subtraktion. Am Ende der Schleife ist die verbleibende Zahl (wie sie binär dargestellt würde) eine Zeichenfolge von1
s ohne0
s. Diese Operationen werden tatsächlich unärgerlich ausgeführt. Es ist nur konzeptionell, dass sie in binärer Form durchgeführt werden.1
s" mit der zuvor erhaltenen Quadratwurzel. Wenn die Quadratwurzel abgerundet werden musste, verwenden Sie eine doppelte Version davon. Dies stellt sicher, dass die "Binärzeichenfolge von1
s" mehr als die Hälfte der Binärziffern als N aufweisen muss, damit eine endgültige Übereinstimmung vorliegt.Um die Quadratwurzel zu erhalten, wird eine Variante des Multiplikationsalgorithmus verwendet, der in meinem regulären Post für Rocco-Zahlen kurz beschrieben ist. Um das niedrigstwertige
0
Bit zu identifizieren , wird der in meinem Regex-Post mit faktoriellen Zahlen kurz beschriebene Divisionsalgorithmus verwendet. Das sind Spoiler . So lesen Sie nicht weiter , wenn Sie nicht einige erweiterte einstellige regex Magie für Sie verwöhnen wollen . Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in der Liste der in diesem früheren Beitrag mit Spoiler-Tags gekennzeichneten empfohlenen Probleme zu lösen und zu versuchen, die mathematischen Erkenntnisse unabhängig voneinander zu entwickeln.Der Regex:
^(?=.*?(?!(x(xx)+)\1*$)(x)*?(x(x*))(?=(\4*)\5+$)\4*$\6)(?=(((?=(x(x+)(?=\10$))*(x*))(?!.*$\11)(?=(x*)(?=(x\12)*$)(?=\11+$)\11\12+$)(?=.*?(?!(x(xx)+)\14*$)\13(x*))\16)*))\7\4(.*$\3|\4)
Probieren Sie es online!
quelle
Gelee , 6 Bytes
Probieren Sie es online!
quelle
Bo-S
kann verwendet werden, um das binäre "Gewicht" der Eingabe zu berechnen, leider scheint der kürzeste Weg zu seinBo-S>0
...Ḷ
J , 12 Bytes
J führt Verben von rechts nach links aus. Beginnen wir also am Ende und arbeiten wir uns zum Anfang vor.
Erläuterung
quelle
(#<2*+/)@#:
sollte 1 sparen, es sei denn, ich vermisse etwas.Julia, 22 Bytes
quelle
Oktave , 26 Bytes
Probieren Sie es online!
quelle
mode(dec2bin(a)-48)
PHP , 44 Bytes
Probieren Sie es online!
PHP , 48 Bytes
Probieren Sie es online!
quelle
Python 2 , 44 Bytes
Probieren Sie es online!
Alte Antwort, 47 Bytes
Dies ist einfach eine Portierung von @ cleblancs C-Antwort . Es ist länger als andere Python-Antworten, aber ich dachte, es lohnt sich, etwas zu posten, da es eine völlig andere Methode ist, die Antwort zu finden.
Probieren Sie es online!
quelle
82 Bytes
quelle
n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
Convert
und einschließen müssenusing System.Linq;
(kürzer geschrieben alsnamespace System.Linq{}
). Eine nette Idee, die sich einfach nicht genug rasiert, um die Ersparnis in diesem Fall zu rechtfertigen.