Se le dará como entrada un número entero k
en el rango de -4503599627370496
(−2 52 ) a 4503599627370496
(2 52 ). Como es bien sabido , los enteros en este rango se pueden representar exactamente como valores de punto flotante de doble precisión.
Debe generar el peso de Hamming (número de unidades ) de la codificación k
en formato binario64 . Utiliza 1 bit para el signo, 11 bits para el exponente (codificado con un desplazamiento) y 52 para la mantisa; ver el enlace de arriba para más detalles.
Como ejemplo , el número 22
se representa como
0 10000000011 0110000000000000000000000000000000000000000000000000
Como hay 5
unos, la salida es 5
.
Tenga en cuenta que la resistencia no afecta el resultado, por lo que puede utilizar de forma segura la representación interna real de su máquina de valores de doble precisión para calcular la salida.
Reglas adicionales
- Se permiten programas o funciones .
- Se puede usar cualquier lenguaje de programación .
- Las lagunas estándar están prohibidas
- El número de entrada estará en decimal. Aparte de eso, los medios de entrada / salida y el formato son flexibles como de costumbre.
- El código más corto en bytes gana.
Casos de prueba
22 -> 5
714 -> 6
0 -> 0
1 -> 10
4503599627370496 -> 5
4503599627370495 -> 55
1024 -> 3
-1024 -> 4
-4096 -> 5
1000000000 -> 16
-12345678 -> 16
fuente
binary64
formato de punto flotante si lo desean? Algunas personas (incluido yo mismo, en un principio) estaban interpretando la pregunta como que las funciones aceptan entradas como un tipo entero de como Clong
. En C, puede argumentar que el lenguaje se convertirá por usted, como cuando llamasqrt((int)foo)
. Pero hay algunas respuestas asm de código máquina x86 (como codegolf.stackexchange.com/a/136360/30206 y la mía) que suponían que teníamos que aceptar entradas enteras de 64 bits. Aceptar unbinary64
valor ahorraría 5 bytes.binary64
como enteros base2. Si necesita manejarlos por separado de todos modos, podría valer la pena hacer algo más que escribir un punzón y recorrer todos los bits.long
, por lo que no podrías decir cualquier binario64double
, porque no todos los dobles son enteros. Pero todos losdouble
s con valores enteros se pueden convertir aylong
viceversa, hasta los límites delong
. (Como señala, lo contrario no es cierto. Obtiene el representable más cercanodouble
, asumiendo el modo de redondeo predeterminado). De todos modos, esta era una forma totalmente válida de configurar la pregunta; Simplemente no lo leí con cuidado>. <Respuestas:
MATL , 5 bytes
Pruébalo en línea!
Transliteración exacta de mi respuesta MATLAB. Tenga en cuenta que la entrada y la salida son implícitas. -2 bytes gracias a Luis Mendo.
fuente
lenguaje de máquina x86_64 (Linux), 16 bytes
Acepta un único parámetro de entero de 64 bits
RDI
, lo convierte en un valor de punto flotanteXMM0
, almacena esos bits nuevamenteRAX
y luego calcula el peso de HammingRAX
, dejando el resultadoRAX
para que pueda ser devuelto a la persona que llama.Requiere un procesador que admita la
POPCNT
instrucción, que sería Intel Nehalem, AMD Barcelona y microarquitecturas posteriores.Para probarlo en línea! , compila y ejecuta el siguiente programa en C:
fuente
objdump -drwC -Mintel
para desmontar en la sintaxis de Intel. Si tuviera un puntero en un registro que pudiera usar para almacenar / recargar, podría guardar bytes conmovaps [rsi], xmm0
/popcnt rax, [rsi]
. (movaps es solo 3 bytes, 2 más cortos que movq.) Pero eso no ayuda aquí, porque[rsp-24]
toma 2 bytes adicionales (SIB de usar RSP como base, más disp8). Y esos bytes adicionales son necesarios tanto en la tienda como en la recarga. Bueno, pensé que vi un ahorro, pero no: /C (gcc) ,
8268 bytes9 bytes gracias a Neil.
piratería de nivel de bits de punto flotante malvado
Pruébalo en línea!
fuente
;long l=
...;l*=2;)s+=l<0;
...long
. Funciona en Linux x86-64, pero fallaría en Windows. Sugeriría decir "gcc con 64 bitslong
", ya que gcc se ejecuta en muchas plataformas, muchas de ellas con diferentes ABI.Python 3 ,
7271 bytes1 byte gracias a Lynn.
Pruébalo en línea!
Explicación
El formato binario64 consta de tres componentes:
1
si el número es negativofuente
n and(…)-(n>0)
es un byte más corto, ¿no?C (gcc) , 47 bytes
Esto no es portátil; se probó con gcc 7.1.1 en x86_64 con Linux, sin banderas de compilación.
Pruébalo en línea!
fuente
long
adouble
en el sitio de la llamada?n
enrax
la ONU código optimizado es bastante cursi. Se rompe si lo habilita-O3
, por lo que no es solo gcc en general, es gcc en x86-64 con 64 bitslong
con optimización deshabilitada. Si pones todos esos requisitos en tu respuesta, votaré. Supongo que hay plataformas compatibles con gcc que tienen 64 bits,long
pero que dejan elpopcountl
resultado en un registro distinto del registro de valor de retorno.double
debería estar bien. No dice nada acerca de requerir que la función lo acepte en formato base2. Y sí, diferentes versiones de gcc podrían emitir un código diferente, por lo que también es importante. (Dato curioso : sin-mpopcnt
, gcc no usará elpopcnt
insn, y emitirá una secuencia de instrucciones para emularlo. Algunas arquitecturas no tienen una instrucción popcnt en absoluto, por lo que__builtin_popcountl
siempre tiene que usar alguna secuencia de insns)__builtin_*
funciones (¿la mayoría?) Tienen versiones heredadas para evitar generar instrucciones ilegales.-march=native
usapopcntq
solo si está disponible.Java (OpenJDK 8) , 92 bytes
Pruébalo en línea!
fuente
C (gcc), 63 bytes
Esta solución se basa en la respuesta de @ LeakyNun, pero debido a que no quiere mejorar su propia respuesta, estoy publicando aquí más versiones de golf.
Pruébalo en línea
fuente
C #,
817068 bytesAhorre 11 bytes gracias a @Leaky Nun.
Guardado 2 bytes gracias a @Neil.
Pruébalo en línea! Utiliza en
System.BitConverter.DoubleToInt64Bits
lugar delunsafe
código, ya que no pude hacer que TIO trabaje con él.Versión completa / formateada:
fuente
for(;l!=0;l*=2)
y no necesitarás el ternarios-=l>>31
?s+=l<0?1:0
?l
es largo, por lo que necesitas-=l>>63
?Python 2 , 69 bytes
-12 bytes, gracias solo a @ ASCII
Pruébalo en línea!
fuente
!
isn't needed since byte order doesn't matter hereJavaScript (ES6),
818077 bytesEdit: Saved 1 byte thanks to @Arnauld. Saved 3 bytes thanks to @DocMax.
fuente
g(i^i&-i,x++)
for -1 byte?new Float64Array([n])
withFloat64Array.of(n)
x86-64 machine code, 12 bytes for
int64_t
input6 bytes for
double
inputRequires the
popcnt
ISA extension (CPUID.01H:ECX.POPCNT [Bit 23] = 1
).(Or 13 bytes if modifying the arg in-place requires writing all 64-bits, instead of leaving garbage in the upper 32. I think it's reasonable to argue that the caller would probably only want to load the low 32b anyway, and x86 zero-extends from 32 to 64 implicitly with every 32-bit operation. Still, it does stop the caller from doing
add rbx, [rdi]
or something.)x87 instructions are shorter than the more obvious SSE2
cvtsi2sd
/movq
(used in @ceilingcat's answer), and a[reg]
addressing mode is the same size as areg
: just a mod/rm byte.The trick was to come up with a way to have the value passed in memory, without needing too many bytes for addressing modes. (e.g. passing on the stack isn't that great.) Fortunately, the rules allow read/write args, or separate output args, so I can just get the caller to pass me a pointer to memory I'm allowed to write.
Se puede llamar desde C con la firma:
void popc_double(int64_t *in_out);
solo los 32b bajos del resultado son válidos, lo que puede ser extraño para C pero natural para asm. (La solución requiere un prefijo REX en la tienda final (mov [rdi], rax
), por lo que un byte más). En Windows, cambierdi
ardx
, since Windows doesn't use the x86-64 System V ABI.Listado NASM. El enlace TIO tiene el código fuente sin el desmontaje.
Pruébalo en línea! Incluye un
_start
programa de prueba que le pasa un valor y sale con estado de salida = valor de retorno popcnt. (Abra la pestaña "depurar" para verlo).Pasar punteros de entrada / salida separados también funcionaría (rdi y rsi en el x86-64 SystemV ABI), pero no podemos destruir razonablemente la entrada de 64 bits o justificar tan fácilmente la necesidad de un búfer de salida de 64 bits mientras solo escribimos bajo 32b.
Si queremos argumentar que podemos tomar un puntero al entero de entrada y destruirlo, mientras devuelve la salida
rax
, simplemente omita elmov [rdi], eax
frompopcnt_double_outarg
, reduciéndolo a 10 bytes.Alternativa sin trucos tontos de convenciones de llamadas, 14 bytes
usa la pila como espacio de cero,
push
para llegar allí. Usepush
/pop
para copiar registros en 2 bytes en lugar de 3 paramov rdi, rsp
. ([rsp]
siempre necesita un byte SIB, por lo que vale la pena gastar 2 bytes para copiarrsp
antes de las tres instrucciones que lo usan).Llame desde C con esta firma:
int popcnt_double_push(int64_t);
Aceptar entrada en
double
formatoLa pregunta solo dice que es un entero en un cierto rango, no que tiene que estar en una representación de entero binario base2. Aceptar la
double
entrada significa que ya no tiene sentido usar x87. (A menos que use una convención de llamada personalizada dondedouble
se pasan s en registros x87. Luego almacene en la zona roja debajo de la pila, y popcnt desde allí).11 bytes:
Pero podemos usar el mismo truco de paso por referencia que antes para hacer una versión de 6 bytes:
int pcd(const double&d);
6 bytes .
fuente
Perl 5 ,
3332 + 1 (-p) =3433 bytesGuardado 1 byte gracias a hobbs
Pruébalo en línea!
fuente
d
una palabra (enpack d,$_
lugar depack"d",$_
)MATLAB, 36 bytes
Usando el hecho de que
de2bi
no solo es más cortodec2bin
, sino que también proporciona un resultado en unos y ceros en lugar de ASCII 48, 49.fuente
Java (64, 61, 41 bytes)
Completamente sencillo utilizando la biblioteca estándar (Java SE 5+):
Contribución de Kevin Cruijssen (Java SE 5+):
Contribución de Kevin Cruijssen (Java SE 8+, función lambda):
fuente
Long n
y usarlo enn.bitCount(...)
lugar deLong.bitCount(...)
. Además, si usa Java 8+, pueden->n.bitCount(Double.doubleToLongBits(n))
Solo para probar un TheLethalCoder's diferente y más seguro enfoque , se me ocurrió esto (es una pena que C # tenga nombres de método tan largos):
C # (.NET Core) , 76 + 13 bytes
Pruébalo en línea!
El recuento de bytes incluye 13 bytes para
using System;
. Primero necesito convertir eldouble
a along
que tiene la misma representación binaria, luego puedo convertirlo a un binariostring
, y luego cuento los1
s simplemente dividiendo la cadena y contando las subcadenas menos 1.fuente
using
into your byte count.namespace System.Linq;{d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Count(c=>c>48)}
. Aunque no lo he probado, debería funcionar.using
directiva.namespace
es útil. Pero sí, en este caso evitar a Linq era un poco más barato. Solo quería comentar con su enfoque en caso de que tuviera alguna idea sobre cómo acortarlo para ahorrar bytes.Sum(c=>c&1)
es más corto. OSum()-768
Jalea , 19 bytes
Pruébalo en línea!
fuente
cc, 79 bytes
La salida se deja en la parte superior de la pila.
Agregaré una explicación más tarde.
Pruébalo en línea!
Tenga en cuenta que los números negativos están precedidos por
_
, no-
.fuente
Groovy (con analizador Parrot) , 46 bytes
fuente
C, 67 bytes
código de control y resultados
fuente
Erlang 55 bytes
Una función anónima que cuenta todas las
1
s en un número codificado como flotante de 64 bits.referencias:
fuente