Flotador 754 a Hamming

29

Se le dará como entrada un número entero ken 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 ken 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 22se representa como

0 10000000011 0110000000000000000000000000000000000000000000000000

Como hay 5unos, 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

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
Luis Mendo
fuente
1
¿Pretende que las funciones puedan aceptar sus entradas ya en binary64formato 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 C long. En C, puede argumentar que el lenguaje se convertirá por usted, como cuando llama sqrt((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 un binary64valor ahorraría 5 bytes.
Peter Cordes
Si es así, ¿todo lo relacionado con el rango limitado es solo en caso de que alguien quiera piratear la conversión a un patrón binario de 64 bits en lugar de escribir un punteo? ¿O para idiomas sin tipografía? Hmm, un desafío interesante podría ser agregar el exponente y la mantisa de a binary64como 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.
Peter Cordes
2
@PeterCordes Sí, puede ingresar en forma de un número de coma flotante. El rango limitado es asegurarse de que la representación de punto flotante sea precisa
Luis Mendo
Vale gracias. Supongo que querías dejar la opción de escribir una función que tome un long, por lo que no podrías decir cualquier binario64 double, porque no todos los dobles son enteros. Pero todos los doubles con valores enteros se pueden convertir ay longviceversa, hasta los límites de long. (Como señala, lo contrario no es cierto. Obtiene el representable más cercano double, 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>. <
Peter Cordes
"Tenga en cuenta que la resistencia no afecta el resultado, por lo que puede utilizar de manera segura la representación interna real de su máquina de valores de doble precisión para calcular la salida". a menos que su máquina no utilice el formato de coma flotante IEEE ...
Jerry Jeremiah

Respuestas:

8

MATL , 5 bytes

3Z%Bz

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.

3Z%   % Typecast: changes input (implicitly taken and converted to double) to uint64 without changing underlying bits
B     % Convert integer to array of 1s and 0s
z     % Count nonzero entries
Sanchises
fuente
33

lenguaje de máquina x86_64 (Linux), 16 bytes

0:       f2 48 0f 2a c7          cvtsi2sd %rdi,  %xmm0
5:       66 48 0f 7e c0          movq     %xmm0, %rax
a:       f3 48 0f b8 c0          popcnt   %rax,  %rax
f:       c3                      retq

Acepta un único parámetro de entero de 64 bits RDI, lo convierte en un valor de punto flotante XMM0, almacena esos bits nuevamente RAXy luego calcula el peso de Hamming RAX, dejando el resultado RAXpara que pueda ser devuelto a la persona que llama.

Requiere un procesador que admita la POPCNTinstrucción, que sería Intel Nehalem, AMD Barcelona y microarquitecturas posteriores.

Para probarlo en línea! , compila y ejecuta el siguiente programa en C:

#include<stdio.h>
const char g[]="\xF2\x48\x0F\x2A\xC7\x66\x48\x0F\x7E\xC0\xF3\x48\x0F\xB8\xC0\xC3";
#define f(x) ((int(*)(long))g)(x)

int main(int a){
  printf("%d\n",f(22));
  printf("%d\n",f(714));
  printf("%d\n",f(0));
  printf("%d\n",f(1));
  printf("%d\n",f(4503599627370496L));
  printf("%d\n",f(4503599627370495L));
  printf("%d\n",f(1024));
  printf("%d\n",f(-1024));
  printf("%d\n",f(-4096));
  printf("%d\n",f(1000000000));
  printf("%d\n",f(-12345678));
}
techo
fuente
2
¡+1, la herramienta adecuada para el trabajo! Esta podría ser la única vez que x86 puede competir legítimamente con los idiomas de golf o vencer a Jelly. :)
DJMcMayhem
2
Ew, sintaxis de AT&T? Puede usar objdump -drwC -Mintelpara desmontar en la sintaxis de Intel. Si tuviera un puntero en un registro que pudiera usar para almacenar / recargar, podría guardar bytes con movaps [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: /
Peter Cordes
Me salvé 4 bytes con una convención de llamada personalizados . O aún guarde 2 bytes con la misma convención de llamada que esto, usando las instrucciones x87.
Peter Cordes
1
@DJMcMayhem: Quizás no sea la única vez. Todavía no hay respuestas en lenguaje de golf en el desafío Extreme Fibonacci (imprima los primeros 1000 dígitos de Fib (1 billón), y mi código de máquina x86 responde (105 bytes rápido, o 101 bytes que se ejecutan en 5 minutos en lugar de 1 minuto) no es mucho más grande que algunas de las otras respuestas, y todos están en idiomas con números enteros de precisión extendida incorporados.
Peter Cordes
2
O un desafío más simple (y sin un requisito de rendimiento), combinación de teclas de croma con una variedad de enteros . Mi respuesta de código de máquina es la mitad de la longitud de la respuesta de Pyth.
Peter Cordes
11

C (gcc) , 82 68 bytes

9 bytes gracias a Neil.

piratería de nivel de bits de punto flotante malvado

s;f(long n){double d=n;n=*(long*)&d;for(s=0;n;n*=2)s+=n<0;return s;}

Pruébalo en línea!

Monja permeable
fuente
Sabía que serías el primero, pero no esperaba el idioma :-D
Luis Mendo
@LuisMendo Solo pensé que sería conveniente en ese idioma ... No sé de otros idiomas que puedan hacer esto
Leaky Nun
2
Ahorre 9 bytes cambiando a otro lado: ... ;long l=... ;l*=2;)s+=l<0;...
Neil
1
Por supuesto, esto requiere una implementación en C con 64 bits long. Funciona en Linux x86-64, pero fallaría en Windows. Sugeriría decir "gcc con 64 bits long", ya que gcc se ejecuta en muchas plataformas, muchas de ellas con diferentes ABI.
Peter Cordes
1
El comentario de @ Peter es por qué agregué "LP64" en una edición. También reorganicé el otro texto en lo que pensé que era un orden más lógico. Supongo que no le gustó ese cambio y lo revertió, pero LP64 es un término estándar que describe el ABI donde longs y punteros son valores de 64 bits (en comparación con ILP64, donde ints también son de 64 bits, o LLP64, como se usa en Windows, donde solo los largos y punteros largos son de 64 bits y los largos aún son de 32 bits). Tal vez debería haber agregado más explicaciones o un enlace en línea al artículo relevante de Wikipedia.
Cody Gray
8

Python 3 , 72 71 bytes

1 byte gracias a Lynn.

lambda n:n and(bin(1020+len(bin(abs(n))))+bin(abs(n))).count('1')-(n>0)

Pruébalo en línea!

Explicación

El formato binario64 consta de tres componentes:

  • el primer bit es el bit de signo, que es 1 si el número es negativo
  • los siguientes 11 bits almacenan el exponente con 1023 agregados
  • los siguientes 52 bits almacenan el significado, o la mantisa.
Monja permeable
fuente
n and(…)-(n>0)es un byte más corto, ¿no?
Lynn
O int-> float, o cualquier flota, para el caso.
user2357112 es compatible con Monica el
8

C (gcc) , 47 bytes

f(double n){n=__builtin_popcountl(*(long*)&n);}

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!

Dennis
fuente
1
La entrada tiene que ser un número entero. ¿O está bien dejar que la persona que llama maneje eso mediante la conversión implícita de longa doubleen el sitio de la llamada?
Peter Cordes
1
Además, basándose en un golpe de suerte de la conducta compilador para pasar a dejar nen raxla 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 bits longcon optimización deshabilitada. Si pones todos esos requisitos en tu respuesta, votaré. Supongo que hay plataformas compatibles con gcc que tienen 64 bits, longpero que dejan el popcountlresultado en un registro distinto del registro de valor de retorno.
Peter Cordes
1
Tomé entero en el sentido matemático. He agregado las especificaciones de mis entornos de prueba, ya que no estoy seguro de que gcc, x86-64 y 64 bits sean suficientes. Dicho esto, al menos en x86, las funciones sin retorno funcionan con gcc (y tcc) la mayoría de las veces.
Dennis
Sí, solo estaba releyendo la pregunta, y estoy de acuerdo en que aceptar el argumento como doubledeberí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á el popcntinsn, y emitirá una secuencia de instrucciones para emularlo. Algunas arquitecturas no tienen una instrucción popcnt en absoluto, por lo que __builtin_popcountlsiempre tiene que usar alguna secuencia de insns)
Peter Cordes
Sí, muchas __builtin_*funciones (¿la mayoría?) Tienen versiones heredadas para evitar generar instrucciones ilegales. -march=nativeusa popcntqsolo si está disponible.
Dennis
6

C (gcc), 63 bytes

f(double d){long s=0,n=*(long*)&d;for(;n;n*=2)s+=n<0;return s;}

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
2
Dudo mucho que alguien no quiera mejorar su respuesta.
Sr. Xcoder
1
@ Mr.Xcoder. Ok, guardaré esto aquí hasta que edite su propia respuesta. Si no quiere editar, esto se quedará aquí. Publiqué esta mejora como un comentario en su respuesta y él la rechazó.
1
Creo que la entrada debe ser de tipo entero y no real.
ceilingcat
3
@ThePirateBay No vi tu comentario sobre mi respuesta y todavía no lo veo ahora.
Leaky Nun
9
La decisión de sugerir mejoras o publicar su propia respuesta es suya, pero 6 minutos es apenas una hora .
Dennis
5

C #, 81 70 68 bytes

d=>{unsafe{long l=*(long*)&d,s=0;for(;l!=0;l*=2)s-=l>>63;return s;}}

Ahorre 11 bytes gracias a @Leaky Nun.
Guardado 2 bytes gracias a @Neil.

Pruébalo en línea! Utiliza en System.BitConverter.DoubleToInt64Bitslugar del unsafecódigo, ya que no pude hacer que TIO trabaje con él.

Versión completa / formateada:

namespace System
{
    class P
    {
        static void Main()
        {
            Func<double, long> f = d =>
            {
                unsafe
                {
                    long l = *(long*)&d, s = 0;

                    for (; l != 0; l *= 2)
                        s -= l >> 63;
                    return s;
                }
            };

            Console.WriteLine(f(22));
            Console.WriteLine(f(714));
            Console.WriteLine(f(0));
            Console.WriteLine(f(1));
            Console.WriteLine(f(4503599627370496));
            Console.WriteLine(f(4503599627370495));
            Console.WriteLine(f(1024));
            Console.WriteLine(f(-1024));
            Console.WriteLine(f(-4096));
            Console.WriteLine(f(1000000000));
            Console.WriteLine(f(-12345678));

            Console.ReadLine();
        }
    }
}
TheLethalCoder
fuente
for(;l!=0;l*=2)y no necesitarás el ternario
Leaky Nun
@LeakyNun Gracias. Me estaba rascando la cabeza por años
TheLethalCoder
Puedes usar s-=l>>31?
Neil
@Neil no parece funcionar. ¿Asumo que quieres reemplazar s+=l<0?1:0?
TheLethalCoder
Mi error; les largo, por lo que necesita s-=l>>63?
Neil
4

Python 2 , 69 bytes

-12 bytes, gracias solo a @ ASCII

lambda n:bin(*unpack('Q',pack('d',n))).count('1')
from struct import*

Pruébalo en línea!

Zarigüeya muerta
fuente
1
71 bytes
ASCII-only
1
Golfing your approach, 76 bytes, I do recommend ASCII-only's approach though
Mr. Xcoder
@Mr.Xcoder the ! isn't needed since byte order doesn't matter here
ASCII-only
1
69 bytes
ASCII-only
@ASCII-only Pack the unpacked. Thanks :D
Dead Possum
4

JavaScript (ES6), 81 80 77 bytes

f=
n=>new Uint8Array(Float64Array.of(n).buffer).map(g=i=>i&&g(i^i&-i,x++),x=0)|x
<input oninput=o.textContent=f(this.value)><pre id=o>0

Edit: Saved 1 byte thanks to @Arnauld. Saved 3 bytes thanks to @DocMax.

Neil
fuente
Could you do g(i^i&-i,x++) for -1 byte?
Arnauld
@Arnauld I did wonder whether there was a golfier bit twiddle, thanks for finding it!
Neil
1
-3 more if you replace new Float64Array([n]) with Float64Array.of(n)
DocMax
4

x86-64 machine code, 12 bytes for int64_t input

6 bytes for double input

Requires 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 a reg: 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, cambie rdiardx, since Windows doesn't use the x86-64 System V ABI.

Listado NASM. El enlace TIO tiene el código fuente sin el desmontaje.

  1  addr    machine      global popcnt_double_outarg
  2          code         popcnt_double_outarg:
  3                           ;; normal x86-64 ABI, or x32: void pcd(int64_t *in_out)
  4 00000000 DF2F             fild qword  [rdi]    ; int64_t -> st0
  5 00000002 DD1F             fstp qword  [rdi]    ; store binary64, using retval as scratch space.
  6 00000004 F3480FB807       popcnt rax, [rdi]
  7 00000009 8907             mov    [rdi], eax    ; update only the low 32b of the in/out arg
  8 0000000B C3               ret
    # ends at 0x0C = 12 bytes

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 el mov [rdi], eaxfrom popcnt_double_outarg, reduciéndolo a 10 bytes.


Alternativa sin trucos tontos de convenciones de llamadas, 14 bytes

usa la pila como espacio de cero, pushpara llegar allí. Use push/ poppara copiar registros en 2 bytes en lugar de 3 para mov rdi, rsp. ( [rsp]siempre necesita un byte SIB, por lo que vale la pena gastar 2 bytes para copiar rspantes de las tres instrucciones que lo usan).

Llame desde C con esta firma: int popcnt_double_push(int64_t);

 11                               global popcnt_double_push
 12                               popcnt_double_push:
 13 00000040 57                       push   rdi         ; put the input arg on the stack (still in binary integer format)
 14 00000041 54                       push   rsp         ; pushes the old value (rsp updates after the store).
 15 00000042 5A                       pop    rdx         ; mov      rdx, rsp
 16 00000043 DF2A                     fild   qword [rdx]
 17 00000045 DD1A                     fstp   qword [rdx]
 18 00000047 F3480FB802               popcnt rax,  [rdx]
 19 0000004C 5F                       pop    rdi         ; rebalance the stack
 20 0000004D C3                       ret
    next byte is 0x4E, so size = 14 bytes.

Aceptar entrada en doubleformato

La 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 doubleentrada significa que ya no tiene sentido usar x87. (A menos que use una convención de llamada personalizada donde doublese pasan s en registros x87. Luego almacene en la zona roja debajo de la pila, y popcnt desde allí).

11 bytes:

 57 00000110 66480F7EC0               movq    rax, xmm0
 58 00000115 F3480FB8C0               popcnt  rax, rax
 59 0000011A C3                       ret

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);

 58 00000110 F3480FB807               popcnt  rax, [rdi]
 59 00000115 C3                       ret

6 bytes .

Peter Cordes
fuente
4

Perl 5 , 33 32 + 1 (-p) = 34 33 bytes

Guardado 1 byte gracias a hobbs

$_=(unpack"B*",pack d,$_)=~y/1//

Pruébalo en línea!

Xcali
fuente
Puede guardar 1 byte haciendo duna palabra (en pack d,$_lugar de pack"d",$_)
hobbs
3

MATLAB, 36 bytes

@(n)nnz(de2bi(typecast(n,'uint64')))

Usando el hecho de que de2bino solo es más corto dec2bin, sino que también proporciona un resultado en unos y ceros en lugar de ASCII 48, 49.

Sanchises
fuente
3

Java (64, 61, 41 bytes)

Completamente sencillo utilizando la biblioteca estándar (Java SE 5+):

int f (long n) {return Long. bitCount (Double. doubleToLongBits (n));}

Contribución de Kevin Cruijssen (Java SE 5+):

int f(Long n){return n.bitCount(Double.doubleToLongBits(n));}

Contribución de Kevin Cruijssen (Java SE 8+, función lambda):

n->n.bitCount(Double.doubleToLongBits(n))
Nayuki
fuente
¡Bien hecho! :-)
Leaky Nun
1
Buena respuesta, +1 de mi parte. Puede jugar golf tres bytes tomando el parámetro como Long ny usarlo en n.bitCount(...)lugar de Long.bitCount(...). Además, si usa Java 8+, puede n->n.bitCount(Double.doubleToLongBits(n))
jugarlo
2

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

d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Split('1').Length-1

Pruébalo en línea!

El recuento de bytes incluye 13 bytes para using System;. Primero necesito convertir el doublea a longque tiene la misma representación binaria, luego puedo convertirlo a un binario string, y luego cuento los 1s simplemente dividiendo la cadena y contando las subcadenas menos 1.

Charlie
fuente
Nice alternative but you need to include the using into your byte count.
TheLethalCoder
El uso de LINQ de 95 bytes de sólo unos pocos más: namespace System.Linq;{d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Count(c=>c>48)}. Aunque no lo he probado, debería funcionar.
TheLethalCoder
@TheLethalCoder funciona, pero traté de evitar a Linq, así que no tuve que agregar una segunda usingdirectiva.
Charlie
1
Cuando agrega el segundo, namespacees ú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.
TheLethalCoder
@TheLethalCoder, Sum(c=>c&1)es más corto. OSum()-768
Peter Taylor
1

cc, 79 bytes

[pq]su[-1r]st0dsb?dd0=u0>tsa[1+]ss[la2%1=slb1+sblad2/sa1<r]dsrxlb1022+sa0lrx+1-

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

poi830
fuente
1

C, 67 bytes

int i;g(char*v){int j=v[i/8]&1<<i%8;return!!j+(++i<64?g(v):(i=0));}

código de control y resultados

#define R     return
#define u32 unsigned
#define F        for
#define P     printf

int main()
{/*           5   6 0 10                5               55    3      4       16*/
 double v[]={22,714,0,1 ,4503599627370496,4503599627370495,1024, -1024, -12345678};
 int i; 

 F(i=0;i<9;++i)
     P("%f = %d\n", v[i], g(&v[i]));
 R 0;
}

>tri4
22.000000 = 5
714.000000 = 6
0.000000 = 0
1.000000 = 10
4503599627370496.000000 = 5
4503599627370495.000000 = 55
1024.000000 = 3
-1024.000000 = 4
-12345678.000000 = 16
RosLuP
fuente