¿Es el número pesado en binario?

58

Un entero es pesado en binario si su representación binaria contiene más 1s que 0s mientras ignora los ceros a la izquierda. Por ejemplo, 1 es pesado en binario, ya que su representación binaria es simple 1, sin embargo, 4 no es pesado en binario, como lo es su representación binaria 100. En caso de empate (por ejemplo 2, con una representación binaria de 10), el número no se considera pesado en binario.

Dado un entero positivo como entrada, genera un valor verdadero si es pesado en binario, y un valor falso si no lo es.

Casos de prueba

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

Puntuación

Este es el por lo que gana menos bytes en cada idioma

Skidsdev
fuente
¿Qué sucede si mi idioma no puede manejar el último caso de prueba porque está fuera de los límites de lo que se considera un entero positivo?
musicman523
1
@ musicman523 afaik Las reglas estándar de E / S establecen que solo tiene que aceptar números representables por el formato de número de su idioma. Tenga en cuenta que "jugar" esto mediante el uso de algo como boolfuck se considera una
escapatoria
¿Cuenta algún valor de verdad / falsedad o necesitamos dos valores distintos?
Erik the Outgolfer
@EriktheOutgolfer cualquier valor
Skidsdev
66
Aka A072600 , si esto ayuda a alguien.
dcsohl

Respuestas:

28

Código de máquina x86, 15 14 bytes

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

Esta es una función que utiliza la convención de llamadas __fastcall de Microsoft (primer y único parámetro en ecx, valor de retorno en eax, callee puede clobber edx), aunque puede modificarse trivialmente para otras convenciones de llamadas que pasan argumentos en los registros.

Devuelve 255 como verdadero y 0 como falsey.

Utiliza el código de operación no documentado (pero ampliamente compatible) salc.

Desmontaje a continuación:

;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

Pruébalo en línea!

Gracias a Peter Cordes por sugerir reemplazarlo lzcntcon bsr.

ZH Liu
fuente
Agradable. Llegué a lo obvio popcntantes de desplazarme hacia abajo para buscar respuestas, pero no había pensado lzcnten tratar solo con los dígitos significativos según lo requerido por la pregunta.
Peter Cordes
¿Hay alguna forma de obtener un ahorro neto al usar en bsrlugar de lzcnt(aka rep bsr)? Tendría que usar en sublugar de leaya que le da 32-lzcnt. (O deja el dst sin modificar para src = 0, en todo el hardware Intel y AMD existente. AMD incluso documenta este comportamiento, pero Intel dice que no está definido ... De todos modos, OP dijo positivo , lo que descarta 0).
Peter Cordes
1
Definitivamente estaba pensando en la misma línea que @Peter, ya que el desafío limita explícitamente las entradas a enteros positivos. De hecho, tenía una solución redactada usando popcnty bsr, pero tenía 17 bytes. Estaba pensando que era bastante bueno en comparación con la primera respuesta que vi , pero este ingenioso leatruco le quita los pantalones. También miré en comparar bsfy popcnt. Pero no veo de ninguna manera que se pueda superar esta solución, incluso teniendo en cuenta el 1 byte que podría guardar soltando el repprefijo.
Cody Gray
1
salcno es equivalente a setc al: este último se establece alen 1 si CF se establece, no en 255.
Ruslan
1
El equivalente real de salces sbb al, al, pero obtienes un ahorro de 1 byte para codificarlo. Por cierto, está documentado por AMD, y es ampliamente compatible con Intel, y la mnemotecnia incluso proviene del mapa de código de operación P6 de Intel. Así que este es bastante seguro de usar. Además, ¡una buena mejora aquí para pensar en usar esa instrucción! Esto es básicamente lo que hizo mi borrador original, excepto (1) que había usado código x86-64, por inclo que el doble de codificación, y (2) no había pensado salc, así que estaba haciendo el mismo trabajo en un camino más largo Lástima que solo pueda votar una vez.
Cody Gray
17

Jalea , 5 bytes

Bo-SR

Produce resultados no vacíos (verdad) o resultados vacíos (falsos).

Pruébalo en línea!

Cómo funciona

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
fuente
Agradable. Tenía Bo-S, pero no pude encontrar un átomo de 1 byte que convertiría positivo / no positivo en verdadero / falso ...
ETHproductions
Lógico o con −1, ¿verdad?
Lynn
@ Lynn Sí, de hecho. Gracias.
Dennis
1
4 bytes
caird coinheringaahing
@cairdcoinheringaahing Gracias, pero Æṃno existía en ese entonces.
Dennis
14

Python 2 , 35 bytes

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

Pruébalo en línea!

Antigua respuesta, 38 bytes

Salidas 0como falsas y / -2o -1verdaderas

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

Pruébalo en línea!

varilla
fuente
2
¿El 0 inicial en el retorno de bincausa problemas con esta solución?
Shadow
3
@shadow No hay problema, por la forma en que maxfunciona. En caso de empate, max devolverá el primer valor en el iterable que tiene el valor máximo. Este código utiliza ese hecho para asegurarse de que se devuelve 1 en caso de empate, lo que en realidad significa que hay más unos que ceros, ya que se agregó un cero adicional bin. En realidad, sería incorrecto si se escribiera de esta manera si no fuera por el cero extra.
FryAmTheEggman
@FryAmTheEggman esto también es cierto en la respuesta anterior, donde los cmpretornos 0cuando ambos son iguales
Rod
11

Octava , 18 bytes

@(n)mode(de2bi(n))

TIO no funciona ya que la caja de herramientas de comunicaciones no está incluida. Se puede probar en Octave-Online .

Cómo funciona esto:

de2biconvierte un número decimal en un vector numérico binario, no una cadena como lo dec2binhace.

modedevuelve el dígito más frecuente en el vector. El valor predeterminado es el más bajo en caso de empate.

@(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
fuente
¿Es la caja de herramientas de comunicaciones una parte estándar de Octave, o es más parecida a una biblioteca en otros idiomas?
dcsohl
Es un paquete que viene con la instalación. Debe cargarlo específicamente en algunas instalaciones, y se carga automáticamente como estándar en otras. Es parte del estándar en Octave-Online.net, así que lo estoy usando como referencia. (El código debe funcionar en al menos un intérprete que existía antes del desafío).
Stewie Griffin
9

JavaScript (ES6), 36 34 bytes

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0
ETHproducciones
fuente
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0por 35 bytes.
ovs
Use en n>>1lugar de n>>>1guardar un byte ya que la entrada nunca es negativa.
kamoroso94
@ kamoroso94 Gracias, pero fallaría el 2147483648.
ETHproductions
@ETHproductions Maldición, y n/2|0no es mejor: /
kamoroso94
8

Mathematica, 22 bytes

Guardado un byte gracias a @MartinEnder y @JungHwanMin .

#>#2&@@#~DigitCount~2&
alephalpha
fuente
2
Creo que la notación infija tiene mayor prioridad que @@.
Martin Ender
1
-1 byte (como señaló @MartinEnder):#>#2&@@#~DigitCount~2&
JungHwan Min
7

Brachylog , 6 bytes

ḃọtᵐ>₁

Pruébalo en línea!

Explicación

Example input: 13

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

Como nunca unificará su salida con una lista de dígitos con ceros a la izquierda, sabemos que las ocurrencias de 1siempre serán las primeras y las de 0siempre serán las segundas .

Fatalizar
fuente
7

Python 3 ,  44  (gracias @ c-mcavoy) 40 bytes

lambda n:bin(n).count('0')<len(bin(n))/2

Pruébalo en línea!

wrymug
fuente
55
Tachado 44 sigue siendo 44
JungHwan Min
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;}

Pruébalo en línea!

cleblanc
fuente
Sobre la base de la aclaración del OP, puede quitarunsigned
musicman523
Como nnn es positivo, puede cambiar n>>=1a n/=2. También creo que puedes usar en ~nlugar de n^-1, lo que también debería permitirte cambiar &&a&
musicman523
Ocurren cosas extrañas cuando editar comentarios - medios "nnn" n, y no importa acerca de cambiar &&a &, no creo que eso funcionaría. Pero cambiarlo a *parece funcionar
musicman523
@ musicman523 El &&fue solo para manejar el caso sin firmar, pero como solo necesito manejar enteros positivos, puedo eliminarlo todo junto. Sin embargo, un buen comentario sobre /=ser más bajo >>=, ¡Gracias!
cleblanc
Puede guardar un byte cambiando n&1?++i:--1a i+=n%2*2-1. También puedes deshacerte de él >0diciendo que producirás cero para pesado y distinto de cero para no pesado
musicman523
6

R , 54 53 51 bytes

-1 byte gracias a Max Lawnboy

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

lee de stdin; devuelve TRUEpara números pesados ​​binarios. des el número de dígitos binarios; sum(n%/%2^(0:d)%%2calcula la suma de dígitos (es decir, número de unidades).

Pruébalo en línea!

Giuseppe
fuente
Solo vi su respuesta después de publicar la mía ... De todos modos, puede usar en log2(n)lugar de log(n,2)guardar 1 byte
Maxim Mikhaylov
@MaxLawnboy ah, por supuesto. ¡Gracias!
Giuseppe
Golfed otros 12 bytes: codegolf.stackexchange.com/a/132396/59530
JAD
6

Código de máquina x86_64, 23 22 21 bytes

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

Desmontado:

  # 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

¡Gracias @Ruslan, @PeterCordes por el -1byte!

Pruébalo en línea!

ბიმო
fuente
¿Hay alguna razón en particular por la que uses en 8d 1flugar de 89 fb?
Ruslan
2
La verdadera pregunta es, ¿hay alguna razón en particular por la que estás usando esa sintaxis abominable de AT&T? Además, el desmontaje y el desmontaje tanto acepta que no tiene add eax, 2+ dec eax, pero sus comentarios sugieren que desee de la subasta ebx, no eax.
Cody Gray
1
Puede reemplazar jnz Next/ add/ dec(7 bytes) con lea -1(%rax, %rbx, 2), %eax(4 bytes) para hacer eax += 2*ebx - 1(como en la otra respuesta de código máquina x86 ). Luego, fuera del bucle neg %eax(2 bytes) antes de desplazar el bit de signo hacia abajo. Ahorro neto de 1 byte. O test %eax,%eax/ setge %altambién funcionaría, si su valor de retorno es un boolo int8_t.
Peter Cordes
1
@PeterCordes Creo que sé lo que pasó, pero no estoy seguro: podría no haberlo intentado, lea -1(%rax,rbx,2)pero solo lea -1(%eax,%eax,2)y haber perdido bytes de esta manera ... De todos modos, ambos tenían razón, puedo guardar un byte como este. ¡Muchas gracias (a cambio lo cambiaré leapor un movtiempo)!
ბიმო
1
@ moonheart08: No sabía sobre eso en ese entonces, pero alguien publicó una respuesta que ahorró 7 bytes.
ბიმო
5

Perl 6 ,  32  30 bytes

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

Pruébalo

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

Pruébalo

Expandido:

{      # 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
fuente
5

Sabio , 40 39 bytes

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

Pruébalo en línea!

Explicación

::^?                                      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
Asistente de trigo
fuente
5

Haskell, 41 34

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

Si nes extraño, tome un -1si es par, tome un 1. Agregue una llamada recursiva con n/2y pare si n = 0. Si el resultado es menor que 0el número es binario pesado.

Pruébalo en línea!

Editar: @ Ørjan Johansen encontró algunos accesos directos y guardó 7 bytes. ¡Gracias!

nimi
fuente
mod n 2puede ser justo n, y es un byte más corto sin un acumulador. Pruébalo en línea!
Ørjan Johansen
5

Retina , 37 34 bytes

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

1+

Pruébalo en línea! El enlace incluye casos de prueba más pequeños (los más grandes probablemente se quedarían sin memoria). Editar: Guardado 3 bytes gracias a @MartinEnder. Explicación: La primera etapa se convierte de decimal a unario, y las siguientes dos etapas se convierten de unario a binario (esto es casi directamente de la página aritmética unaria en la wiki de Retina, excepto que estoy usando en @lugar de 0). La tercera etapa busca pares de caracteres diferentes, que podrían ser uno @1o otro 1@, y los elimina hasta que no quede ninguno. La última etapa luego verifica los 1s restantes.

Neil
fuente
${1}puede ser $+. O podría usar en !lugar de 0y luego acortar 01|10a .\b..
Martin Ender
@ MartinEnder Huh, ¿ $+hace lo correcto cuando el patrón contiene un |? Me pregunto si podría haber usado eso antes ...
Neil
2
no, $+es súper estúpido y simplemente usa el grupo con el mayor número, ya sea que se haya usado o no. Solo es útil para jugar al golf cuando tienes más de nueve grupos o en una situación como la de aquí, y no sé por qué lo usaría en una expresión regular de producción.
Martin Ender
5

R , 43 bytes

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

Pruébalo en línea!

             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
fuente
¡+1 solución ordenada! Ni siquiera lo sabíaintToBits
Giuseppe
Golfed otros 4 bytes: codegolf.stackexchange.com/a/132396/59530
JAD
5

Kotlin , 50 bytes

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

Lambda de tipo implícito (Int) -> Boolean. Versión 1.1 y superior solo debido al uso de Int.toString(radix: Int).

Desafortunadamente, el tiempo de ejecución Kotlin de TIO parece ser 1.0.x, así que aquí hay un perro triste en lugar de un enlace TIO:

F. George
fuente
4

Pyth, 9 7 bytes

ehc2S.B

Pruébalo aquí

-2 gracias a FryAmTheEggman .

Erik el Outgolfer
fuente
Otro enfoque de 9 bytes:>ysJjQ2lJ
KarlKastor
1
7 bytes, pero siento que todavía debería haber algo más corto ...
FryAmTheEggman
@FryAmTheEggman Hmm ... eso solo podría funcionar como un programa completo. (¡Sabía que había una forma de usar .B!)
Erik the Outgolfer
4

R, 39 37 bytes

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

Esta es una combinación de los métodos utilizados por @MickyT y @Giuseppe, ahorrando otros pocos bytes.

sum(intToBits(x) > 0)cuenta la cantidad de 1bits y 2+log2(x)/2es la mitad de la cantidad total de bits cuando se redondea hacia abajo. No tenemos que redondear hacia abajo debido al comportamiento cuando los dos valores son iguales.

JAD
fuente
4

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

Sin LINQ

EDITAR: dana con un golf de -13 bytes que cambia el tiempo a un recursivo y devuelve un bool en lugar de un entero.

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

Pruébalo en línea!

Destroigo
fuente
4

Regex (ECMAScript), 85 73 71 bytes

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

Pruébalo en línea!

explicación por Deadcode

La versión anterior de 73 bytes se explica a continuación.

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

Debido a las limitaciones de la expresión regular ECMAScript, una táctica efectiva es a menudo transformar el paso número uno a la vez mientras se mantiene invariable la propiedad requerida en cada paso. Por ejemplo, para probar un cuadrado perfecto o una potencia de 2, reduzca el número en tamaño mientras mantiene un cuadrado o una potencia de 2 (respectivamente) en cada paso.

Esto es lo que hace esta solución en cada paso:

111100101ones>zeroes1

ones>zeroesones1>zeroes1

Cuando estos pasos repetidos no pueden ir más allá, el resultado final será una cadena contigua de 1bits, que es pesada, e indica que el número original también era pesado, o una potencia de 2, lo que indica que el número original no era pesado.

Y, por supuesto, aunque estos pasos se describen anteriormente en términos de manipulaciones tipográficas en la representación binaria del número, en realidad se implementan como aritmética unaria.

# 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.
Mugriento
fuente
2
Si bien esto está inspirado en la respuesta de Deadcode , el algoritmo es lo suficientemente diferente que sentí que merecía una respuesta por separado en lugar de un comentario.
Grimmy
2
Esto es fenomenal, y exactamente lo que quería ver (alguien sacando mi expresión del agua con un algoritmo mucho más conciso). Pero sus comentarios realmente no lo explican en absoluto, y la versión comentada de 73 bytes de la expresión regular ni siquiera funciona (las referencias \5posteriores están desactivadas por una). He estudiado esto y lo he explicado y comentado en mi respuesta (porque StackExchange no permite respuestas de varias líneas).
Código muerto
4

Regex (ECMAScript), 183 bytes

Este fue otro problema interesante para resolver con la expresión regular de ECMA. La forma "obvia" de manejar esto es contar el número de 1bits y compararlo con el número total de bits. Pero no puede contar directamente las cosas en la expresión regular ECMAScript: la falta de referencias persistentes significa que solo se puede modificar un número en un bucle y en cada paso solo se puede disminuir.

Este algoritmo unario funciona de la siguiente manera:

  1. Tome la raíz cuadrada de la mayor potencia de 2 que encaje en N y tome nota de si la raíz cuadrada era perfecta o si tenía que redondearse hacia abajo. Esto se usará más tarde.
  2. En un bucle, mueva cada 1bit más significativo a la posición menos significativa donde haya un 0bit. Cada uno de estos pasos es una resta. Al final del ciclo, el número restante (como se representaría en binario) es una cadena de 1s sin 0s. Estas operaciones se realizan realmente en unario; es solo conceptualmente que se están haciendo en binario.
  3. Compare esta "cadena binaria de 1s" con la raíz cuadrada obtenida anteriormente. Si la raíz cuadrada tuvo que redondearse hacia abajo, use una versión duplicada. Esto asegura que la "cadena binaria de 1s" debe tener más de la mitad de dígitos binarios que N para que haya una coincidencia final.

Para obtener la raíz cuadrada, se usa una variante del algoritmo de multiplicación brevemente descrito en mi publicación de expresiones regulares de números Rocco . Para identificar el 0bit menos significativo , se utiliza el algoritmo de división brevemente descrito en mi publicación de expresiones regulares de números factoriales . Estos son spoilers . Así que no sigas leyendo si no quieres que se te estropee un poco de magia regex unaria avanzada . Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la lista de problemas recomendados etiquetados consecutivamente con spoilers en esta publicación anterior , e intentando encontrar las ideas matemáticas de forma independiente.

Sin más preámbulos, la expresión regular:

^(?=.*?(?!(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)

Pruébalo en línea!

# 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.
)
Código muerto
fuente
1
-98 bytes
Grimmy
3

Jalea , 6 bytes

Bµċ0<S

Pruébalo en línea!

Erik el Outgolfer
fuente
Bo-Spuede usarse para calcular el "peso" binario de la entrada, desafortunadamente la forma más corta de usar que parece ser Bo-S>0...
ETHproductions
@ETHproductions Sí, todavía no hay un átomo "es positivo".
Erik the Outgolfer
Al parecer, funciona bien: P
ETHproductions
3

J , 12 bytes

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

J ejecuta verbos de derecha a izquierda, así que comencemos por el final y avancemos hacia el principio.

Explicación

         #:       NB. Convert input to list of bits
       -:@#       NB. Half (-:) the (@) length (#)
          >       NB. Greater than 
         +/       NB. Sum (really plus (+) reduce (/)
Dan Bron
fuente
1
(#<2*+/)@#:debería guardar 1 a menos que me falte algo.
FrownyFrog
3

Julia, 22 bytes

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

Python 2 , 44 bytes

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

Pruébalo en línea!

Respuesta anterior, 47 bytes

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

Esto es simplemente un puerto de la respuesta C de @ cleblanc . Es más largo que otras respuestas de Python, pero pensé que valía la pena publicarlo, ya que es un método completamente diferente para encontrar la respuesta.

Pruébalo en línea!

musicman523
fuente
2

C #, 82 bytes

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}
TheLethalCoder
fuente
Puede recortar un poco más tratando la cadena como IEnumerable <char>. n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
GalacticCowboy
@GalacticCowboy Eso agrega 11 bytes porque tienes que calificar Converte incluir completamente using System.Linq;(escrito más corto como namespace System.Linq{}). Una buena idea no se reduce lo suficiente como para garantizar el ahorro en este caso.
TheLethalCoder