Ist die Zahl binär schwer?

58

Eine Ganzzahl ist binärlastig, wenn ihre Binärdarstellung mehr 1s als 0s 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 so dass die wenigsten Bytes in jeder Sprache gewinnen

Skidsdev
quelle
Was ist, wenn meine Sprache den letzten Testfall nicht verarbeiten kann, weil er außerhalb der Grenzen einer positiven Ganzzahl liegt?
Musicman523
1
@ musicman523 afaik Standard-E / A-Regeln besagen, dass Sie nur Zahlen akzeptieren müssen, die durch das Zahlenformat Ihrer Sprache dargestellt werden können. Beachten Sie, dass "Spielen" mit so etwas wie Boolfuck als Standard-Regelungslücke gilt
Skidsdev
Zählt ein wahrer / falscher Wert oder brauchen wir zwei unterschiedliche Werte?
Erik der Outgolfer
@EriktheOutgolfer jeden Wert
Skidsdev
6
Aka A072600 , wenn das jemandem hilft.
Dcsohl

Antworten:

28

x86-Maschinencode, 15 bis 14 Byte

F3 0F B8 C1 0F BD D1 03 C0 42 2B D0 D6 C3

Dies 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:

;F3 0F B8 C1 
  popcnt eax, ecx ; Sets eax to number of bits set in ecx

;0F BD D1
  bsr edx, ecx    ; Sets edx to the index of the leading 1 bit of ecx

;03 C0
  add eax, eax

;42
  inc edx

;2B D0
  sub edx, eax

  ; At this point, 
  ;   edx = (index of highest bit set) + 1 - 2*(number of bits set)
  ; This is negative if and only if ecx was binary-heavy.

;D6
  salc           ; undocumented opcode. Sets al to 255 if carry flag 
                 ; is set, and to 0 otherwise. 

;C3
  ret

Probieren Sie es online!

Dank Peter Cordes für die Annahme , ersetzt lzcntmit bsr.

ZH Liu
quelle
Nett. Ich war bis zum Offensichtlichen popcntvorgerückt, um nach Antworten zu suchen, hatte aber nicht daran gedacht, mich lzcntnur mit den für die Frage erforderlichen signifikanten Ziffern zu befassen.
Peter Cordes
Gibt es eine Möglichkeit, durch die Verwendung bsrvon lzcnt(aka rep bsr) Nettoeinsparungen zu erzielen ? Sie müssten substatt verwenden, leada 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ßt 0.)
Peter Cordes
1
Ich habe definitiv in die gleiche Richtung gedacht wie @Peter, da die Herausforderung die Eingabe explizit auf positive ganze Zahlen beschränkt. In der Tat hatte ich eine Lösung mit popcntund entworfen bsr, aber es war 17 Bytes. Ich dachte, das wäre ziemlich gut im Vergleich zu der ersten Antwort, die ich gesehen habe , aber dieser clevere leaTrick schlägt die Hose aus. Ich habe mir auch Vergleichen bsfund angeschaut popcnt. 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 des repPräfixes sparen könnten .
Cody Grey
1
salcist nicht gleichbedeutend mit setc al: Letzteres setzt alauf 1, wenn CF gesetzt ist, nicht auf 255.
Ruslan
1
Das tatsächliche Äquivalent von salcist sbb 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, also incdoppelt so lang für die Codierung war, und (2) ich nicht daran gedacht hatte salc, also die gleiche Arbeit in a zu tun längerer Weg. Schade, dass ich nur einmal upvoten kann.
Cody Grey
17

Gelee , 5 Bytes

Bo-SR

Ergibt eine nicht leere Ausgabe (wahr) oder eine leere Ausgabe (falsch).

Probieren Sie es online!

Wie es funktioniert

Bo-SR  Main link. Argument: n

B      Binary; convert n to base 2.
 o-    Compute the logical OR with -1, mapping 1 -> 1 and 0 -> -1.
   S   Take the sum s. We need to check if the sum is strictly positive.
    R  Range; yield [1, ..., s], which is non-empty iff s > 0.
Dennis
quelle
Nett. Ich hatte Bo-S, aber ich konnte kein 1-Byte-Atom finden, das positiv / nicht positiv in wahr / falsch konvertieren würde ...
ETHproductions
Logisch oder mit −1, richtig?
Lynn
@Lynn Ja, in der Tat. Vielen Dank.
Dennis
1
4 Bytes
Caird Coinheringaahing
@cairdcoinheringaahing Danke, gab es aber Æṃdamals nicht.
Dennis
14

Python 2 , 35 Bytes

lambda n:max('10',key=bin(n).count)

Probieren Sie es online!

Alte Antwort, 38 Bytes

Ausgaben 0als falsch und / -2oder -1als wahr

lambda n:~cmp(*map(bin(n).count,'10'))

Probieren Sie es online!

Stange
quelle
2
binVerursacht die führende 0 in der Rückkehr dieser Lösung Probleme?
Schatten
3
@shadow Es gibt kein Problem, weil die Art und Weise maxfunktioniert. 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 wurde bin. Es wäre tatsächlich falsch, wenn es auf diese Weise geschrieben würde, wenn es nicht die zusätzliche Null gäbe.
FryAmTheEggman
@FryAmTheEggman Dies gilt auch für die alte Antwort, bei der die cmpRenditen, 0wenn beide gleich sind
Rod
11

Oktave , 18 Bytes

@(n)mode(de2bi(n))

TIO funktioniert nicht, da die Kommunikations-Toolbox nicht enthalten ist. Es kann auf Octave-Online getestet werden .

Wie das funktioniert:

de2bikonvertiert eine Dezimalzahl in einen binären numerischen Vektor und nicht wie dec2bingewohnt in eine Zeichenfolge .

modeGibt die häufigste Ziffer im Vektor zurück. Bei einem Unentschieden ist die Standardeinstellung die niedrigste.

@(n)                % Anonymous function that takes a decimal number as input 'n'
    mode(        )  % Computes the most frequent digit in the vector inside the parentheses
         de2bi(n)   % Converts the number 'n' to a binary vector
Stewie Griffin
quelle
Ist die Kommunikations-Toolbox ein Standardbestandteil von Octave oder ähnelt sie eher einer Bibliothek in anderen Sprachen?
Dcsohl
Es ist ein Paket, das mit der Installation geliefert wird. Sie müssen es in einigen Installationen speziell laden, in anderen wird es automatisch als Standard geladen. Es ist Teil des Standards auf Octave-Online.net, also verwende ich das als Referenz. (Der Code muss in mindestens einem Interpreter funktionieren, der vor der Abfrage vorhanden war.)
Stewie Griffin
9

JavaScript (ES6), 36 34 Bytes

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0
ETHproductions
quelle
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0für 35 Bytes.
OVS
Verwenden Sie n>>1statt n>>>1, um ein Byte zu speichern, da die Eingabe niemals negativ ist.
kamoroso94
@ kamoroso94 Danke, aber dann würde es am 2147483648 scheitern.
ETHproductions
@ ETHproductions Darn, und n/2|0ist nicht besser: /
Kamoroso94
8

Mathematica, 22 Bytes

Dank @MartinEnder und @JungHwanMin ein Byte gespart .

#>#2&@@#~DigitCount~2&
Alephalpha
quelle
2
Ich denke, die Infixnotation hat eine höhere Priorität als @@.
Martin Ender
1
-1 Byte (wie bei @MartinEnder vermerkt):#>#2&@@#~DigitCount~2&
JungHwan Min
7

Brachylog , 6 Bytes

ḃọtᵐ>₁

Probieren Sie es online!

Erläuterung

Example input: 13

ḃ        Base (default: binary): [1,1,0,1]
 ọ       Occurences:             [[1,3],[0,1]]
  tᵐ     Map Tail:               [3,1]
    >₁   Strictly decreasing list

Da die Ausgabe niemals mit einer Liste von Ziffern mit führenden Nullen vereinheitlicht wird, wissen wir, dass die Vorkommen von 1immer an erster Stelle stehen und die Vorkommen von 0immer an zweiter Stelle stehen .

Tödlich
quelle
6

C (gcc) , 51 48 41 40 Bytes

i;f(n){for(i=0;n;n/=2)i+=n%2*2-1;n=i>0;}

Probieren Sie es online!

Cleblanc
quelle
Basierend auf der Klarstellung von OP können Sieunsigned
musicman523
Da nnn positiv ist, können Sie ändern n>>=1zu n/=2. Ich denke auch , können Sie verwenden , ~nanstatt n^-1, die Sie ermöglichen sollte , sich ändern &&zu&
musicman523
Seltsame Dinge passieren , wenn ich Kommentare bearbeiten - „nnn“ bedeutet n, und egal über die Änderung &&zu &, ich glaube nicht , dass das funktionieren würde. Aber es zu ändern *scheint zu funktionieren
musicman523
@ musicman523 Das &&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!
Cleblanc
Sie können ein Byte speichern Wechsel n&1?++i:--1zu i+=n%2*2-1. Möglicherweise können Sie auch >0feststellen, dass Sie Null für Heavy und Nicht-Null für Nicht-Heavy
ausgeben
6

R , 54 53 51 Bytes

-1 Byte danke an Max Lawnboy

n=scan();d=floor(log2(n))+1;sum(n%/%2^(0:d)%%2)*2>d

liest von stdin; Gibt TRUEfür binäre schwere Zahlen zurück. dist die Anzahl der Binärziffern; sum(n%/%2^(0:d)%%2berechnet die Ziffernsumme (dh die Anzahl der Einsen).

Probieren Sie es online!

Giuseppe
quelle
Hab deine Antwort erst gesehen, nachdem ich meine gepostet habe ... Wie auch immer, du kannst 1 Byte speichern log2(n)anstatt log(n,2)
Maxim Mikhaylov
@ MaxLawnboy ah, natürlich. Vielen Dank!
Giuseppe
: Weitere 12 Bytes golfed off codegolf.stackexchange.com/a/132396/59530
JAD
6

x86_64-Maschinencode, 23 22 21 Byte

31 c0 89 fa 83 e2 01 8d 44 50 ff d1 ef 75 f3 f7 d8 c1 e8 1f c3

Zerlegt:

  # zero out eax
  xor  %eax, %eax
Loop:
  # copy input to edx
  mov  %edi, %edx
  # extract LSB(edx)
  and  $0x1, %edx
  # increment(1)/decrement(0) eax depending on that bit
  lea -1(%rax,%rdx,2), %eax
  # input >>= 1
  shr  %edi
  # if input != 0: repeat from Loop
  jnz  Loop

  # now `eax < 0` iff the input was not binary heavy,
  neg %eax
  # now `eax < 0` iff the input was binary heavy (which means the MSB is `1`)
  # set return value to MSB(eax)
  shr  $31, %eax
  ret

Danke @Ruslan, @PeterCordes für das -1Byte!

Probieren Sie es online!

ბიმო
quelle
Gibt es einen bestimmten Grund, warum Sie 8d 1fanstelle von verwenden 89 fb?
Ruslan,
2
Die eigentliche Frage ist, gibt es einen bestimmten Grund, warum Sie diese abscheuliche AT & T-Syntax verwenden?!? Sowohl die Demontage als auch die Demontage stimmen überein, dass Sie add eax, 2+ haben dec eax, aber Ihre Kommentare deuten darauf hin, dass Sie erhöhen möchten ebx, nicht eax.
Cody Grey
1
Sie können ersetzen jnz Next/ add/ dec(7 Byte) mit lea -1(%rax, %rbx, 2), %eax(4 Byte) zu tun eax += 2*ebx - 1(wie in der anderen x86 - Computer-Code Antwort ). Dann außerhalb der Schleife neg %eax(2 Bytes), bevor das Vorzeichenbit nach unten verschoben wird. Nettoeinsparung von 1 Byte. Oder test %eax,%eax/ setge %alwürde auch funktionieren, wenn Ihr Rückgabewert ein booloder ist int8_t.
Peter Cordes
1
@PeterCordes Ich glaube ich weiß was passiert ist, aber ich bin mir nicht sicher: Ich hätte es vielleicht nicht versucht lea -1(%rax,rbx,2)sondern nur lea -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 das leaauf eine movWeile ändern, wenn ich dabei bin)!
14.
1
@ moonheart08: Das wusste ich damals noch nicht, aber jemand hat eine Antwort gepostet , die 7 Bytes spart.
7.
5

Perl 6 ,  32-30  Bytes

{[>] .base(2).comb.Bag{qw<1 0>}}

Probier es aus

{[>] .polymod(2 xx*).Bag{1,0}}

Probier es aus

Erweitert:

{      # bare block lambda with implicit parameter 「$_」

  [>]  # reduce the following with &infix:« > »

    .polymod(2 xx *) # turn into base 2 (reversed) (implicit method call on 「$_」)
    .Bag\            # put into a weighted Set
    { 1, 0 }         # key into that with 1 and 0
                     # (returns 2 element list that [>] will reduce)
}
Brad Gilbert b2gills
quelle
5

Wise , 40 39 Bytes

::^?[:::^~-&[-~!-~-~?]!~-?|>]|:[>-?>?]|

Probieren Sie es online!

Erläuterung

::^?                                      Put a zero on the bottom
    [                                     While
     :::^~-&                              Get the last bit
            [-~!-~-~?]!~-?|               Increment counter if 0 decrement if 1
                           >              Remove the last bit
                            ]|            End while
                              :[>-?>?]|   Get the sign
Weizen-Assistent
quelle
5

Haskell, 41 34

g 0=0
g n=g(div n 2)+(-1)^n
(<0).g

Wenn nungerade ist, nimm a, -1wenn es gerade ist, nimm a 1. Fügen Sie einen rekursiven Anruf mit hinzu n/2und stoppen Sie, wenn n = 0. Wenn das Ergebnis kleiner als 0die Zahl ist, ist es binärlastig.

Probieren Sie es online!

Edit: @ Ørjan Johansen hat einige Verknüpfungen gefunden und 7 Bytes gespeichert. Vielen Dank!

nimi
quelle
mod n 2kann gerecht sein n, und es ist ein Byte kürzer ohne Akkumulator. Probieren Sie es online!
Ørjan Johansen
5

Retina , 37-34 Bytes

.+
$*
+`(1+)\1
$1@
@1
1
+`.\b.

1+

Probieren 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 verwende 0). Die dritte Stufe sucht nach Paaren unterschiedlicher Zeichen, die entweder @1oder sein können 1@, und löscht sie, bis keine mehr übrig sind. Die letzte Stufe prüft dann auf verbleibende 1s.

Neil
quelle
${1}kann sein $+. Oder Sie könnten verwenden !statt 0und dann verkürzen 01|10zu .\b..
Martin Ender
@MartinEnder Huh, stimmt $+das, wenn das Muster a enthält |? Ich frage mich, ob ich das vorher hätte benutzen können ...
Neil,
2
nein, $+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.
Martin Ender
5

R , 43 Bytes

max(which(B<-intToBits(scan())>0))/2<sum(B)

Probieren Sie es online!

             intToBits(scan())              # converts to bits
          B<-                 >0            # make logical and assign to B
max(which(                      ))/2        # get the length of the trimmed binary and halve
                                    <sum(B) # test against the sum of bits
MickyT
quelle
+1 saubere Lösung! Ich wusste nicht einmal überintToBits
Giuseppe
: Weitere 4 Bytes golfed off codegolf.stackexchange.com/a/132396/59530
JAD
5

Kotlin , 50 Bytes

{i:Int->i.toString(2).run{count{it>'0'}>length/2}}

Lambda impliziten Typs (Int) -> Boolean. Version 1.1 und höher nur aufgrund der Verwendung von Int.toString(radix: Int).

Leider scheint die Kotlin-Laufzeit von TIO 1.0.x zu sein, daher hier ein trauriger Hund anstelle eines TIO-Links:

F. George
quelle
4

Pyth, 9 7 Bytes

ehc2S.B

Probieren Sie es hier aus.

-2 danke an FryAmTheEggman .

Erik der Outgolfer
quelle
Ein weiterer 9-Byte-Ansatz:>ysJjQ2lJ
KarlKastor
1
7 Bytes, aber ich
denke,
@FryAmTheEggman Hmm ... das konnte nur als volles Programm funktionieren. (Ich wusste, dass es eine Möglichkeit gibt .B!)
Erik the Outgolfer
4

R, 39 37 Bytes

sum(intToBits(x<-scan())>0)>2+log2(x)

Hierbei 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 der 1Bits und 2+log2(x)/2ist die Hälfte der Gesamtanzahl der Bits, wenn abgerundet. Wir müssen nicht abrunden, weil die beiden Werte gleich sind.

JAD
quelle
4

C # (.NET Core) , 62 , 49 Bytes

Ohne 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.

x=>{int j=0;for(;x>0;x/=2)j+=x%2*2-1;return j>0;}

Probieren Sie es online!

Destroigo
quelle
4

Regex (ECMAScript), 85 73 71 Bytes

^((?=(x*?)\2(\2{4})+$|(x*?)(\4\4xx)*$)(\2\4|(x*)\5\7\7(?=\4\7$\2)\B))*$

Probieren 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:

111100101ones>zeroes1

ones>zeroesones1>zeroes1

Wenn diese wiederholten Schritte nicht weiter ausgeführt werden können, ist das Endergebnis entweder eine zusammenhängende Folge von 1Bits, 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.

# For these comments, N = the number to the right of the "cursor", a.k.a. "tail",
# and "rightmost" refers to the big-endian binary representation of N.
^
(                          # if N is even and not a power of 2:
    (?=(x*?)\2(\2{4})+$)   # \2 = smallest divisor of N/2 such that the quotient is
                           # odd and greater than 1; as such, it is guaranteed to be
                           # the largest power of 2 that divides N/2, iff N is not
                           # itself a power of 2 (using "+" instead of "*" is what
                           # prevents a match if N is a power of 2).
    \2                     # N = N - \2. This changes the rightmost "10" to a "01".
|                          # else (N is odd or a power of 2)
    (?=(x*?)(\4\4xx)*$)    # \4+1 = smallest divisor of N+1 such that the quotient is
                           # odd; as such, \4+1 is guaranteed to be the largest power
                           # of 2 that divides N+1. So, iff N is even, \4 will be 0.
                           # Another way of saying this: \4 = the string of
                           # contiguous 1 bits from the rightmost part of N.
                           # \5 = (\4+1) * 2 iff N+1 is not a power of 2, else
                           # \5 = unset (NPCG) (iff N+1 is a power of 2), but since
                           #   N==\4 iff this is the case, the loop will exit
                           #   immediately anyway, so an unset \5 will never be used.
    (
        \4                 # N = N - \4. If N==\4 before this, it was all 1 bits and
                           # therefore heavy, so the loop will exit and match. This
                           # would work as "\4$", and leaving out the "$" is a golf
                           # optimization. It still works without the "$" because if
                           # N is no longer heavy after having \4 subtracted from it,
                           # this will eventually result in a non-match which will
                           # then backtrack to a point where N was still heavy, at
                           # which point the following alternative will be tried.
    |
        # N = (N + \4 - 2) / 4. This removes the rightmost "01". As such, it removes
        # an equal number of 0 bits and 1 bits (one of each) and the heaviness of N
        # is invariant before and after. This fails to match if N is a power of 2,
        # and in fact causes the loop to reach a dead end in that case.
        \5                 # N = N - (\4+1)*2
        (x*)\7\7(?=\4\7$)  # N = (N - \4) / 4 + \4
        \B                 # Assert N > 0 (this would be the same as asserting N > 2
                           # before the above N = (N + \4 - 2) / 4 operation).
    )
)+
$       # This can only be a match if the loop was exited due to N==\4.
Grimmig
quelle
2
Obwohl dies von Deadcodes Antwort inspiriert ist , ist der Algorithmus so unterschiedlich, dass ich der Meinung war, dass er eine separate Antwort und keinen Kommentar verdient.
Grimmy
2
Dies ist phänomenal und genau das, was ich sehen wollte (jemand bläst meine Regex mit einem viel präziseren Algorithmus aus dem Wasser). Aber Ihre Kommentare erklären es überhaupt nicht, und die kommentierte 73-Byte-Version des regulären Ausdrucks funktioniert nicht einmal (die Rückwärtsreferenzen \5sind um eins versetzt). Ich habe dies untersucht und in meiner Antwort erklärt und kommentiert (da StackExchange keine mehrzeiligen Antworten zulässt).
Deadcode
4

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 1Bits 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. Nehmen Sie die Quadratwurzel der größten Potenz von 2, die in N passt, und notieren Sie, ob die Quadratwurzel perfekt war oder abgerundet werden musste. Dies wird später verwendet.
  2. Verschieben Sie in einer Schleife jedes höchstwertige 1Bit an die niedrigstwertige Position, an der sich ein 0Bit befindet. Jeder dieser Schritte ist eine Subtraktion. Am Ende der Schleife ist die verbleibende Zahl (wie sie binär dargestellt würde) eine Zeichenfolge von 1s ohne 0s. Diese Operationen werden tatsächlich unärgerlich ausgeführt. Es ist nur konzeptionell, dass sie in binärer Form durchgeführt werden.
  3. Vergleichen Sie diese "binäre Zeichenfolge von 1s" mit der zuvor erhaltenen Quadratwurzel. Wenn die Quadratwurzel abgerundet werden musste, verwenden Sie eine doppelte Version davon. Dies stellt sicher, dass die "Binärzeichenfolge von 1s" 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 0Bit 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!

# For the purposes of these comments, the input number = N.
^
# Take the floor square root of N
(?=
    .*?
    (?!(x(xx)+)\1*$)    # tail = the largest power of 2 less than tail
    (x)*?               # \3 = nonzero if we will need to round this square root
                        #      up to the next power of two
    (x(x*))             # \4 = potential square root; \5 = \4 - 1
    (?=
        (\4*)\5+$       # Iff \4*\4 == our number, then the first match here must result in \6==0
    )
    \4*$\6              # Test for divisibility by \4 and for \6==0 simultaneously
)
# Move all binary bits to be as least-significant as possible, e.g. 11001001 -> 1111
(?=
    (                                 # \7 = tool for making tail = the result of this move
        (
            (?=
                (x(x+)(?=\10$))*(x*)  # \11 = {divisor for getting the least-significant 0 bit}-1
            )
            (?!.*$\11)                # Exit the loop when \11==0
            (?=
                (x*)                  # \12 = floor((tail+1) / (\11+1)) - 1
                (?=(x\12)*$)          # \13 = \12+1
                (?=\11+$)
                \11\12+$
            )
            (?=
                .*?
                (?!(x(xx)+)\14*$)     # tail = the largest power of 2 less than tail
                \13                   # tail -= \13
                (x*)                  # \16 = tool to move the most-significant 1 bit to the
                                      # least-significant 0 bit available spot for it
            )
            \16
        )*
    )
)
\7                  # tail = the result of the move
\4                  # Assert that \4 is less than or equal to the result of the move
(
    .*$\3
|
    \4              # Double the value of \4 to compare against if \3 is non-empty,
                    # i.e. if we had an even number of total digits.
)
Deadcode
quelle
1
-98 Bytes
Grimmy
3

Gelee , 6 Bytes

Bµċ0<S

Probieren Sie es online!

Erik der Outgolfer
quelle
Bo-Skann verwendet werden, um das binäre "Gewicht" der Eingabe zu berechnen, leider scheint der kürzeste Weg zu sein Bo-S>0...
ETHproductions
@ETHproductions Ja, es gibt noch kein "ist positiv" Atom.
Erik der Outgolfer
Naja anscheinend
klappt das
3

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

         #:       NB. Convert input to list of bits
       -:@#       NB. Half (-:) the (@) length (#)
          >       NB. Greater than 
         +/       NB. Sum (really plus (+) reduce (/)
Dan Bron
quelle
1
(#<2*+/)@#:sollte 1 sparen, es sei denn, ich vermisse etwas.
FrownyFrog
3

Julia, 22 Bytes

x->2*x<4^count_ones(x)
Tanj
quelle
2

Python 2 , 44 Bytes

f=lambda n,c=0:f(n/2,c+n%2*2-1)if n else c>0

Probieren Sie es online!

Alte Antwort, 47 Bytes

c,n=0,input()
while n:c+=n%2*2-1;n/=2
print c>0

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!

musicman523
quelle
2

82 Bytes

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}
TheLethalCoder
quelle
Sie können weitere Zeichenfolgen abschneiden, indem Sie die Zeichenfolge als IEnumerable <char> behandeln. n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
GalacticCowboy
@GalacticCowboy Das fügt 11 Bytes hinzu, weil Sie vollständig qualifizieren Convertund einschließen müssen using System.Linq;(kürzer geschrieben als namespace System.Linq{}). Eine nette Idee, die sich einfach nicht genug rasiert, um die Ersparnis in diesem Fall zu rechtfertigen.
TheLethalCoder