Le nombre est-il binaire?

58

Un entier est lourd en binaire si sa représentation binaire contient plus de 1s que 0s tout en ignorant les zéros de tête. Par exemple, 1 est lourd en binaire, tout comme sa représentation en binaire 1, mais 4 n'est pas lourd en binaire, au contraire de sa représentation en binaire 100. En cas d'égalité (par exemple 2, avec une représentation binaire de 10), le nombre n'est pas considéré comme lourd.

Si vous entrez un nombre entier positif, indiquez une valeur de vérité si elle est lourde comme un binaire et une valeur de falsey si ce n'est pas le cas.

Testcases

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

Notation

C'est le donc le moins d'octets dans chaque langue gagne

Skidsdev
la source
Que se passe-t-il si ma langue ne peut pas gérer le dernier cas de test parce que cela dépasse les limites de ce qui est considéré comme un entier positif?
musicman523
1
@ musicman523 afaik Les règles d'E / S standard stipulent que vous ne devez accepter que des nombres pouvant être représentés par le format numérique de votre langue. Notez que "jouer" en utilisant quelque chose comme boolfuck est considéré comme une
échappatoire
Est-ce qu'une valeur de vérité / falsification compte ou avons-nous besoin de deux valeurs distinctes?
Erik the Outgolfer
@EriktheOutgolfer n'importe quelle valeur
Skidsdev le
6
Aka A072600 , si cela aide quelqu'un.
dcsohl

Réponses:

28

Code machine x86, 15 à 14 octets

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

Il s'agit d'une fonction utilisant la convention d'appel __fastcall de Microsoft (premier et unique paramètre dans ecx, valeur de retour dans eax, l'appelant est autorisé à masquer edx), bien qu'il puisse être modifié de manière triviale pour d'autres conventions d'appel transmettant des arguments dans des registres.

Il renvoie 255 en tant que vérité et 0 en tant que falsey.

Il utilise l'opcode non documenté (mais largement pris en charge) salc.

Démontage ci-dessous:

;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

Essayez-le en ligne!

Merci à Peter Cordes d’ avoir suggéré de remplacer lzcntpar bsr.

ZH Liu
la source
Agréable. J'étais allé jusqu'à l'évidence popcntavant de faire défiler la liste pour rechercher les réponses, mais je n'avais pas pensé lzcntà gérer uniquement les chiffres significatifs, comme l'exigeait la question.
Peter Cordes
Existe-t-il un moyen de réaliser des économies nettes en utilisant bsrplutôt que lzcnt(aka rep bsr)? Vous devriez utiliser à la subplace de leapuisque cela vous donne 32-lzcnt. (Ou laisse le dst non modifié pour src = 0, sur tout le matériel Intel et AMD existant. AMD documente même ce comportement, mais Intel dit non défini ... Quoi qu'il en soit, OP dit positif , ce qui exclut 0.)
Peter Cordes
1
Je pensais certainement dans le même sens que @Peter, car le défi limite explicitement les entrées aux entiers positifs. En fait, j'ai eu une solution rédigée en utilisant popcntet bsr, mais c'était 17 octets. Je pensais que c’était plutôt bien comparé à la première réponse asm que j’ai vue , mais cette leaastuce habile trompe le pantalon. J'ai aussi regardé comparer bsfet popcnt. Mais je ne vois aucun moyen de battre cette solution, même en tenant compte du 1 octet que vous pourriez économiser en supprimant le reppréfixe.
Cody Grey
1
salcn'équivaut pas à setc al: ce dernier alest défini sur 1 si CF est défini, pas sur 255.
Ruslan
1
L'équivalent réel de salcest sbb al, al, mais vous obtenez une économie de 1 octet pour le coder. À propos, il est documenté par AMD et largement supporté par Intel, le mnémonique provenant même de la carte d'opcode P6 d'Intel. Donc, celui-ci est en fait assez sûr à utiliser. Aussi, belle amélioration ici de penser à utiliser cette instruction! C’est fondamentalement ce que mon projet original faisait, sauf que (1) j’avais utilisé du code x86-64, donc incdeux fois plus de temps pour encoder, et (2) je n’avais pas pensé salc, alors je faisais le même travail dans un chemin plus long. Dommage que je ne puisse voter qu'une fois.
Cody Grey
17

Gelée , 5 octets

Bo-SR

Donne une sortie non vide (vérité) ou vide (falsy).

Essayez-le en ligne!

Comment ça fonctionne

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
la source
Agréable. J'avais Bo-S, mais je ne pouvais pas trouver un atome de 1 octet qui convertirait positif / non positif en vérité / fausseté ...
ETHproductions
Logique ou avec −1, non?
Lynn
@ Lynn Oui, en effet. Merci.
Dennis
1
4 octets
caird coinheringaahing Le 12/12/17
@cairdcoinheringaahing Merci, mais Æṃn'existait pas à l'époque.
Dennis
14

Python 2 , 35 octets

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

Essayez-le en ligne!

Ancienne réponse, 38 octets

Sorties 0sous forme de fausseté et / -2ou -1de vérité

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

Essayez-le en ligne!

Barre
la source
2
Est-ce que le 0 dans le retour de bincause cause cette solution?
Shadow
3
@shadow Il n'y a pas de problème, à cause de la façon dont maxfonctionne. En cas d'égalité, max renverra la première valeur de l'itérable qui a la valeur maximale. Ce code utilise ce fait pour s'assurer que 1 est renvoyé en cas d'égalité, ce qui signifie en fait qu'il y en a plus que de zéros, puisqu'un zéro supplémentaire a été ajouté par bin. Ce serait en fait inexact si vous l’écriviez de cette façon, si ce n’était pour le zéro supplémentaire.
FryAmTheEggman
@FryAmTheEggman c'est également vrai pour l'ancienne réponse, où les cmpretours 0quand ils sont égaux
Rod
11

Octave , 18 octets

@(n)mode(de2bi(n))

TIO ne fonctionne pas car la boîte à outils de communication n'est pas incluse. Il peut être testé sur Octave-Online .

Comment ça marche:

de2biconvertit un nombre décimal en un vecteur numérique binaire, pas une chaîne comme le dec2binfait le.

moderenvoie le chiffre le plus fréquent dans le vecteur. La valeur par défaut est la plus basse en cas d'égalité.

@(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
la source
La boîte à outils de communication est-elle un élément standard d’Octave ou ressemble-t-elle davantage à une bibliothèque dans d’autres langues?
dcsohl
C'est un paquet qui vient avec l'installation. Vous devez le charger spécifiquement dans certaines installations, et il est automatiquement chargé en standard dans d'autres. Cela fait partie de la norme sur Octave-Online.net, je l'utilise donc comme référence. (Le code doit fonctionner dans au moins un interprète qui existait avant le challenge).
Stewie Griffin
9

JavaScript (ES6), 36 34 octets

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0
ETHproductions
la source
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0pour 35 octets.
ovs le
Utilisez n>>1au lieu de n>>>1pour sauvegarder un octet puisque l'entrée n'est jamais négative.
kamoroso94
@ kamoroso94 Merci, mais alors cela échouerait le 2147483648.
ETHproductions
@ETHproductions Darn, et n/2|0ne vaut pas mieux: /
kamoroso94
8

Mathematica, 22 octets

Enregistré un octet grâce à @MartinEnder et à @JungHwanMin .

#>#2&@@#~DigitCount~2&
Alephalpha
la source
2
Je pense que la notation infixe a une priorité plus élevée que @@.
Martin Ender
1
-1 octet (comme l'a noté @MartinEnder):#>#2&@@#~DigitCount~2&
JungHwan Min
7

Brachylog , 6 octets

ḃọtᵐ>₁

Essayez-le en ligne!

Explication

Example input: 13

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

Puisqu'il ne sera jamais unifier sa sortie avec une liste de chiffres avec des zéros au début, nous savons que les occurrences de 1seront toujours en premier et les occurrences de 0seront toujours deuxièmes après .

Fataliser
la source
6

C (gcc) , 51 48 41 40 octets

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

Essayez-le en ligne!

cleblanc
la source
Sur la base de la clarification de OP, vous pouvez supprimerunsigned
musicman523 le
Puisque nnn est positif, vous pouvez changer n>>=1en n/=2. Je pense aussi que vous pouvez utiliser à la ~nplace de n^-1, ce qui devrait également vous permettre de passer &&à&
musicman523
Il se passe des choses étranges lorsque je modifie des commentaires - "nnn" signifie n, et je ne pense pas &&à changer en &, je ne pense pas que cela fonctionnerait. Mais le changer *semble fonctionner
musicman523
@ musicman523 Le &&n'était que pour gérer le cas non signé, mais comme je n'ai besoin que de gérer des entiers positifs, je peux tout supprimer. Bon pouint d' /=être plus court que ça >>=, merci!
cleblanc
Vous pouvez enregistrer un octet en le remplaçant n&1?++i:--1par i+=n%2*2-1. Vous pourriez également être en mesure de vous en débarrasser >0en déclarant que vous allez afficher zéro pour lourd et non nul pour non lourd
musicman523
6

R , 54 53 51 octets

-1 octet grâce à Max Lawnboy

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

lit de stdin; retourne TRUEpour les nombres lourds binaires. dest le nombre de chiffres binaires; sum(n%/%2^(0:d)%%2calcule la somme des chiffres (c.-à-d. le nombre de uns).

Essayez-le en ligne!

Giuseppe
la source
Seulement vu votre réponse après avoir posté le mien ... Quoi qu'il en soit, vous pouvez utiliser log2(n)au lieu de log(n,2)pour économiser 1 octet
Maxim Mikhaylov
@ MaxLawnboy ah, bien sûr. Merci!
Giuseppe
12 autres octets sur le golf
JAD
6

x86_64 code machine, 23 22 21 octets

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

Démonté:

  # 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

Merci @Ruslan, @PeterCordes pour -1byte!

Essayez-le en ligne!

ბიმო
la source
Y a-t-il une raison particulière pour laquelle vous utilisez 8d 1fau lieu de 89 fb?
Ruslan
2
La vraie question est la suivante: existe-t-il une raison particulière pour laquelle vous utilisez cette abominable syntaxe AT & T?!? En outre, le désassemblage et votre désassemblage conviennent tous les deux que vous avez add eax, 2+ dec eax, mais vos commentaires suggèrent que vous souhaitez augmenter ebx, pas eax.
Cody Grey
1
Vous pouvez remplacer jnz Next/ add/ dec(7 octets) par lea -1(%rax, %rbx, 2), %eax(4 octets) eax += 2*ebx - 1(comme dans l’autre réponse code machine x86 ). Ensuite, en dehors de la boucle neg %eax(2 octets) avant de décaler le bit de signe vers le bas. Économie nette de 1 octet. Ou test %eax,%eax/ setge %alfonctionnerait également, si votre valeur de retour est un boolou int8_t.
Peter Cordes
1
@PeterCordes Je pense savoir ce qui s'est passé, mais je ne suis pas sûr: je n'aurais peut-être pas essayé, lea -1(%rax,rbx,2)mais seulement lea -1(%eax,%eax,2)et gaspillé des octets de cette façon ... Quoi qu'il en soit, vous aviez tous les deux raison, je peux enregistrer un octet comme celui-ci. Merci beaucoup (en retour, je vais changer cela leapour un movmoment, je suis là)!
ბიმო
1
@ moonheart08: Je ne savais rien à ce sujet à l'époque, mais quelqu'un a posté une réponse permettant d'économiser 7 octets.
ბიმო
5

Perl 6 ,  32  30 octets

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

Essaye-le

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

Essaye-le

Étendu:

{      # 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
la source
5

Sage , 40 39 octets

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

Essayez-le en ligne!

Explication

::^?                                      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
Assistant de blé
la source
5

Haskell, 41 34

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

Si nc'est étrange, prenez un -1si c'est pair, prenez un 1. Ajouter un appel récursif avec n/2et arrêter si n = 0. Si le résultat est inférieur, 0le nombre est binaire.

Essayez-le en ligne!

Edit: @ Ørjan Johansen a trouvé des raccourcis et a sauvegardé 7 octets. Merci!

nimi
la source
mod n 2peut être juste n, et c'est un octet plus court sans accumulateur. Essayez-le en ligne!
Ørjan Johansen
5

Retina , 37 34 bytes

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

1+

Essayez-le en ligne! Link inclut des cas de test plus petits (les plus gros manquent probablement de mémoire). Edit: 3 octets enregistrés grâce à @MartinEnder. Explication: La première étape est convertie du nombre décimal au unaire, et les deux étapes suivantes sont converties du unaire au binaire (ceci sort presque directement de la page arithmétique unaire du wiki Retina, sauf que j'utilise @plutôt que 0). La troisième étape recherche des paires de caractères différents, qui peuvent être l'un @1ou l' autre 1@, et les supprime jusqu'à ce qu'il n'en reste plus. La dernière étape vérifie ensuite les 1 restants.

Neil
la source
${1}peut être $+. Ou vous pouvez utiliser !au lieu de 0et puis raccourcir 01|10à .\b..
Martin Ender
@MartinEnder Huh, fait $+-il ce qu'il faut quand le motif contient un |? Je me demande si j'aurais pu l'utiliser auparavant ...
Neil
2
non, $+c'est super stupide et utilise simplement le groupe avec le plus grand nombre, qu'il ait été utilisé ou non. Ce n'est utile que pour le golf lorsque vous avez plus de neuf groupes ou dans une situation comme celle-ci, et je ne sais pas pourquoi je l'utilisais jamais dans une regex de production.
Martin Ender
5

R , 43 octets

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

Essayez-le en ligne!

             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
la source
+1 solution soignée! Je ne savais même pas queintToBits
Giuseppe
Golf de 4 autres octets: codegolf.stackexchange.com/a/132396/59530
JAD
5

Kotlin , 50 octets

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

Lambda de type implicite (Int) -> Boolean. Version 1.1 et ultérieure uniquement en raison de l'utilisation de Int.toString(radix: Int).

Malheureusement, le runtime Kotlin de TIO semble être 1.0.x, alors voici un chien triste au lieu d'un lien TIO:

F. George
la source
4

Pyth, 9 à 7 octets

ehc2S.B

Essayez ici.

-2 grâce à FryAmTheEggman .

Erik le golfeur
la source
Une autre approche de 9 octets:>ysJjQ2lJ
KarlKastor
1
7 octets, mais je pense qu'il devrait encore y avoir quelque chose de plus court ...
FryAmTheEggman
@FryAmTheEggman Hmm ... cela ne pourrait fonctionner que comme un programme complet. (Je savais qu'il y avait un moyen de l'utiliser .B!)
Erik l'Outgolfer
4

R, 39 37 octets

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

Ceci est une combinaison des méthodes utilisées par @MickyT et @Giuseppe, en économisant quelques octets supplémentaires.

sum(intToBits(x) > 0)compte le nombre de 1bits et 2+log2(x)/2correspond à la moitié du nombre total de bits arrondis. Nous n'avons pas à arrondir à cause du comportement lorsque les deux valeurs sont égales.

JAD
la source
4

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

Sans LINQ.

EDIT: dana avec un golf de -13 octets changeant le temps en un récursif pour et retournant un booléen au lieu d’entier.

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

Essayez-le en ligne!

Destroigo
la source
4

Regex (ECMAScript), 85 73 71 octets

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

Essayez-le en ligne!

explication par Deadcode

La version antérieure de 73 octets est expliquée ci-dessous.

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

En raison des limitations de la regex ECMAScript, une tactique efficace consiste souvent à transformer l’étape numéro un à la fois tout en maintenant l’invariant de propriété requis à chaque étape. Par exemple, pour tester un carré parfait ou une puissance de 2, réduisez le nombre en conservant un carré ou une puissance de 2 (respectivement) à chaque étape.

Voici ce que cette solution fait à chaque étape:

111100101ones>zeroes1

ones>zeroesones1>zeroes1

Lorsque ces étapes répétées ne peuvent plus aller plus loin, le résultat final sera soit une chaîne de 1bits contigus , ce qui est lourd et indique que le nombre d'origine était également lourd, ou une puissance de 2 indiquant que le nombre d'origine n'était pas lourd.

Et bien sûr, bien que ces étapes soient décrites ci-dessus en termes de manipulations typographiques sur la représentation binaire du nombre, elles sont en réalité implémentées sous forme d'arithmétique unaire.

# 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.
Grimmy
la source
2
Bien que cela soit inspiré par la réponse de Deadcode , l’algorithme est suffisamment différent pour que j’ai estimé qu’il méritait une réponse séparée plutôt qu’un commentaire.
Grimmy
2
C’est phénoménal, et c’est exactement ce que je voulais voir (quelqu’un qui sortait ma regex de l’eau avec un algorithme beaucoup plus concis). Mais vos commentaires ne l'expliquent vraiment pas du tout et la version commentée de 73 octets de la regex ne fonctionne même pas (les backrefs \5suivants sont décalés de un). J'ai étudié cela et expliqué et commenté dans ma réponse (parce que StackExchange n'autorise pas les réponses multilignes).
Deadcode
4

Regex (ECMAScript), 183 octets

C’était un autre problème intéressant à résoudre avec la regex ECMA. La manière "évidente" de gérer cela consiste à compter le nombre de 1bits et à le comparer au nombre total de bits. Mais vous ne pouvez pas compter directement dans ECMAScript regex - l'absence de références arrières persistantes signifie qu'un seul nombre peut être modifié dans une boucle et qu'il ne peut être que réduit à chaque étape.

Cet algorithme unaire fonctionne comme suit:

  1. Prenez la racine carrée de la plus grande puissance de 2 qui rentre dans N et notez si la racine carrée était parfaite ou devait être arrondie. Ce sera utilisé plus tard.
  2. Dans une boucle, déplacez chaque 1bit le plus significatif vers la position la moins significative où il y a un 0bit. Chacune de ces étapes est une soustraction. À la fin de la boucle, le nombre restant (comme il serait représenté en binaire) est une chaîne de 1s sans 0s. Ces opérations sont en réalité effectuées à l’unisson; ce n'est que conceptuellement qu'ils se font en binaire.
  3. Comparez cette "chaîne binaire de 1s" à la racine carrée obtenue précédemment. Si la racine carrée doit être arrondie, utilisez-en une version doublée. Cela garantit que la "chaîne binaire de 1s" doit avoir plus de la moitié de chiffres binaires comme N pour qu'il y ait une correspondance finale.

Pour obtenir la racine carrée, on utilise une variante de l'algorithme de multiplication brièvement décrit dans mon numéro Rocco regex post . Pour identifier le 0bit le moins significatif , on utilise l'algorithme de division décrit brièvement dans mon numéro factoriel regex post . Ce sont des spoilers . Donc , ne lisez pas plus loin si vous ne voulez pas que la magie avancée des regex unaires soit gâtée . Si vous voulez essayer vous-même de découvrir cette magie, je vous recommande vivement de commencer par résoudre certains problèmes de la liste des problèmes recommandés consécutivement marqués par des spoilers dans cet article précédent , puis d'essayer de fournir des informations mathématiques indépendantes.

Sans plus tarder, la 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)

Essayez-le en ligne!

# 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
la source
1
-98 octets
Grimmy le
3

Gelée , 6 octets

Bµċ0<S

Essayez-le en ligne!

Erik le golfeur
la source
Bo-Speut être utilisé pour calculer le "poids" binaire de l'entrée, malheureusement, le moyen le plus court qui semble être Bo-S>0
utilisé
@ETHproductions Oui, il n'y a pas encore d'atome "is positif".
Erik the Outgolfer
Apparemment
ça
3

J , 12 octets

(+/>-:@#)@#:

J exécute les verbes de droite à gauche, alors commençons par la fin et poursuivons notre chemin vers le début.

Explication

         #:       NB. Convert input to list of bits
       -:@#       NB. Half (-:) the (@) length (#)
          >       NB. Greater than 
         +/       NB. Sum (really plus (+) reduce (/)
Dan Bron
la source
1
(#<2*+/)@#:devrait sauver 1 sauf si je manque quelque chose.
FrownyFrog
3

Julia, 22 octets

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

Python 2 , 44 octets

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

Essayez-le en ligne!

Réponse ancienne, 47 octets

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

Ceci est simplement un port de la réponse C de @ cleblanc . C'est plus long que les autres réponses Python mais je me suis dit que ça valait le coup de poster car c'est une méthode complètement différente pour trouver la réponse.

Essayez-le en ligne!

musicman523
la source
2

C #, 82 octets

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}
TheLethalCoder
la source
Vous pouvez en couper davantage en traitant la chaîne comme un <type> IEnumerable. n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
GalacticCowboy
@ GalacticCowboy Cela ajoute 11 octets parce que vous devez pleinement qualifier Convertet inclure using System.Linq;(écrit plus court que namespace System.Linq{}). La bonne idée ne suffit pas pour nous permettre de réaliser des économies dans ce cas.
TheLethalCoder