Vous recevrez en entrée un entier kcompris entre -4503599627370496(−2 ⁵² ) et 4503599627370496(2 ⁵² ). Comme cela est bien connu , les nombres entiers dans cette plage peuvent être représentés exactement comme des valeurs à virgule flottante double précision.

Vous devez sortir le poids de Hamming (nombre d'un) de l'encodage kau format binaire64 . Cela utilise 1 bit pour le signe, 11 bits pour l'exposant (codé avec un décalage) et 52 pour la mantisse; voir le lien ci-dessus pour plus de détails.

Par exemple , le nombre 22est représenté par

0 10000000011 0110000000000000000000000000000000000000000000000000

Puisqu'il y 5en a, la sortie est 5.

Notez que l'endianité n'affecte pas le résultat, vous pouvez donc utiliser en toute sécurité la représentation interne réelle de votre machine des valeurs de double précision pour calculer la sortie.

Règles supplémentaires

• Les programmes ou fonctions sont autorisés.
• N'importe quel langage de programmation peut être utilisé.
• Les failles standard sont interdites
• Le numéro saisi sera en décimal. En dehors de cela, les moyens et le format d'entrée / sortie sont flexibles comme d'habitude.
• Le code le plus court en octets gagne.

Cas de test

22                ->   5
714               ->   6
0                 ->   0
1                 ->  10
4503599627370496  ->   5
4503599627370495  ->  55
1024              ->   3
-1024             ->   4
-4096             ->   5
1000000000        ->  16
-12345678         ->  16

MATL , 5 octets

3Z%Bz

Essayez-le en ligne!

Translittération exacte de ma réponse MATLAB. Notez que l'entrée et la sortie sont implicites. -2 octets grâce à 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

langage machine x86_64 (Linux), 16 octets

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

Accepte un seul paramètre entier 64 bits dans RDI, le convertit en une valeur à virgule flottante dans XMM0, stocke ces bits RAX, puis calcule le poids de hachage de RAX, laissant le résultat dans RAXafin qu'il puisse être retourné à l'appelant.

Nécessite un processeur qui prend en charge l' POPCNTinstruction, qui serait Intel Nehalem, AMD Barcelona et les microarchitectures ultérieures.

Pour l' essayer en ligne! , compilez et exécutez le programme C suivant:

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

C (gcc) , 82 68 octets

9 octets grâce à Neil.

piratage de niveau de bit à virgule flottante mal

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

Essayez-le en ligne!

Python 3 , 72 71 octets

1 octet merci à Lynn.

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

Essayez-le en ligne!

Explication

Le format binaire64 se compose de trois composants:

• le premier bit est le bit de signe, qui est 1si le nombre est négatif
• les 11 bits suivants stockent l'exposant avec 1023 ajoutés
• les 52 bits suivants stockent la signification ou la mantisse.

C (gcc) , 47 octets

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

Ce n'est pas portable; il a été testé avec gcc 7.1.1 sur x86_64 sous Linux, sans drapeaux de compilation.

Essayez-le en ligne!

Java (OpenJDK 8) , 92 octets

int f(long n){int s=0;for(n=Double.doubleToLongBits((double)n);n!=0;n>>>=1)s+=n&1;return s;}

Essayez-le en ligne!

C (gcc), 63 octets

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

Cette solution est basée sur la réponse de @ LeakyNun, mais parce qu'il ne veut pas améliorer sa propre réponse, je poste ici une version plus golfée.

Essayez-le en ligne

C #, 81 70 68 octets

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

Économisez 11 octets grâce à @Leaky Nun.
Enregistré 2 octets grâce à @Neil.

Essayez-le en ligne! Utilise à la System.BitConverter.DoubleToInt64Bitsplace du unsafecode car je n'ai pas pu faire fonctionner TIO avec.

Version complète / formatée:

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

Python 2 , 69 octets

-12 octets, grâce à @ ASCII uniquement

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

Essayez-le en ligne!

JavaScript (ES6), 81 80 77 octets

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: 1 octet enregistré grâce à @Arnauld. Enregistré 3 octets grâce à @DocMax.

code machine x86-64, 12 octets pour int64_tentrée

6 octets pour l' doubleentrée

Nécessite l' popcntextension ISA ( CPUID.01H:ECX.POPCNT [Bit 23] = 1).

(Ou 13 octets si la modification de l'argument sur place nécessite l'écriture de tous les 64 bits, au lieu de laisser des ordures dans les 32 supérieurs. Je pense qu'il est raisonnable de dire que l'appelant ne voudra probablement que charger le 32b bas de toute façon, et x86 zéro -étend implicitement de 32 à 64 à chaque opération 32 bits. Néanmoins, cela empêche l'appelant de faire add rbx, [rdi]quelque chose.)

Les instructions x87 sont plus courtes que la SSE2 cvtsi2sd/ la plus évidente movq(utilisée dans la réponse de @ plafondcat ), et un [reg]mode d'adressage a la même taille qu'un reg: juste un octet mod / rm.

L'astuce consistait à trouver un moyen de faire passer la valeur en mémoire, sans avoir besoin de trop d'octets pour les modes d'adressage. (Par exemple, transmettre la pile n'est pas terrible.) Heureusement, les règles autorisent les arguments de lecture / écriture ou les arguments de sortie séparés , donc je peux simplement demander à l'appelant de me passer un pointeur sur la mémoire que je suis autorisé à écrire.

Appelable depuis C avec la signature: void popc_double(int64_t *in_out); seul le 32b bas du résultat est valide, ce qui est peut-être bizarre pour C mais naturel pour asm. (La correction de ce problème nécessite un préfixe REX sur le magasin final ( mov [rdi], rax), donc un octet de plus.) Sous Windows, passez rdià rdx, car Windows n'utilise pas le x86-64 System V ABI.

Liste NASM. Le lien TIO a le code source sans le démontage.

  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

Essayez-le en ligne! Comprend un_startprogramme de test qui lui transmet une valeur et se termine avec exit status = popcnt return value. (Ouvrez l'onglet "debug" pour le voir.)

Passer des pointeurs d'entrée / sortie séparés fonctionnerait également (rdi et rsi dans l'ABI System86 x64-64), mais nous ne pouvons alors pas raisonnablement détruire l'entrée 64 bits ou justifier aussi facilement d'avoir besoin d'un tampon de sortie 64 bits tout en écrivant uniquement le faible 32b.

Si nous voulons affirmer que nous pouvons prendre un pointeur sur l'entier d'entrée et le détruire, tout en renvoyant la sortie dans rax, puis simplement omettre le mov [rdi], eaxfrom popcnt_double_outarg, le ramenant à 10 octets.

Alternative sans astuces de convention d'appel idiotes, 14 octets

utilisez la pile comme espace de travail, pushpour y arriver. Utilisez push/ poppour copier les registres en 2 octets au lieu de 3 pour mov rdi, rsp. ( [rsp]nécessite toujours un octet SIB, il vaut donc la peine de dépenser 2 octets à copier rspavant trois instructions qui l'utilisent.)

Appelez de C avec cette signature: 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.

Accepter une entrée au doubleformat

La question dit simplement que c'est un entier dans une certaine plage, pas qu'il doive être dans une représentation d'entier binaire base2. Accepter l' doubleentrée signifie qu'il n'y a plus aucun intérêt à utiliser x87. (À moins que vous n'utilisiez une convention d'appel personnalisée dans laquelle les doubles sont passés dans les registres x87. Ensuite, stockez-les dans la zone rouge sous la pile et ouvrez-les à partir de là.)

11 octets:

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

Mais nous pouvons utiliser la même astuce passe-par-référence qu'avant pour créer une version à 6 octets: int pcd(const double&d);

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

6 octets .

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

1 octet enregistré grâce à Hobbs

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

Essayez-le en ligne!

MATLAB, 36 octets

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

En utilisant le fait qui de2biest non seulement plus court que dec2bin, mais fournit également un résultat en uns et en zéros plutôt qu'en ASCII 48, 49.

Java (64, 61, 41 octets)

Complètement simple en utilisant la bibliothèque standard (Java SE 5+):

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

Contribution de Kevin Cruijssen (Java SE 5+):

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

Contribution de Kevin Cruijssen (Java SE 8+, fonction lambda):

n->n.bitCount(Double.doubleToLongBits(n))

Juste pour essayer une approche différente et plus sûre que TheLethalCoder , j'ai trouvé ceci (c'est dommage que C # ait des noms de méthode si longs):

C # (.NET Core) , 76 + 13 octets

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

Essayez-le en ligne!

Le nombre d'octets comprend 13 octets pour using System;. Je dois d'abord convertir le doubleen un longqui a la même représentation binaire, puis je peux le convertir en un binaire string, puis je compte les 1s juste en divisant la chaîne et en comptant les sous-chaînes moins 1.

Gelée , 19 octets

AB©L+⁽¡ßB;®ċ1_>0$a@

Essayez-le en ligne!

dc, 79 octets

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

La sortie est laissée en haut de la pile.
J'ajouterai une explication plus tard.

Essayez-le en ligne!

Notez que les nombres négatifs sont précédés de _, non -.

Groovy (avec analyseur Parrot) , 46 octets

f=n->Long.bitCount(Double.doubleToLongBits(n))

C, 67 octets

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

code de contrôle et résultats

#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

Erlang 55 octets

fun(X)->length([Y||<<Y:1>><=<<X:64/float>>,Y=:=1])end.

Une fonction anonyme qui compte tous les 1s dans un nombre codé comme un flottant de 64 bits.

les références:

• http://erlang.org/doc/programming_examples/bit_syntax.html
• http://erlang.org/doc/programming_examples/list_comprehensions.html