Jako dane wejściowe zostanie podana liczba całkowita kz zakresu od -4503599627370496(-2 ⁵² ) do 4503599627370496(2 ⁵² ). Jak dobrze wiadomo , liczby całkowite w tym zakresie można przedstawić dokładnie jako wartości zmiennoprzecinkowe podwójnej precyzji.

Zalecana moc na wadze Hamminga (liczba jedynek) z kodowaniem kw formacie binary64 . Wykorzystuje to 1 bit dla znaku, 11 bitów dla wykładnika wykładnika (zakodowanych z przesunięciem) i 52 dla mantysy; zobacz powyższy link, aby uzyskać szczegółowe informacje.

Na przykład liczba 22jest reprezentowana jako

0 10000000011 0110000000000000000000000000000000000000000000000000

Ponieważ są 5takie, wynikiem jest 5.

Zauważ, że endianness nie wpływa na wynik, więc możesz bezpiecznie użyć rzeczywistej wewnętrznej reprezentacji wartości podwójnej precyzji w celu obliczenia wyniku.

Dodatkowe zasady

• Programy lub funkcje są dozwolone.
• Można użyć dowolnego języka programowania .
• Standardowe luki są zabronione
• Podana liczba będzie dziesiętna. Poza tym środki wejścia / wyjścia i format są jak zwykle elastyczne .
• Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

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

MATL , 5 bajtów

3Z%Bz

Wypróbuj online!

Dokładna transliteracja mojej odpowiedzi MATLAB. Zauważ, że dane wejściowe i wyjściowe są niejawne. -2 bajty dzięki Luisowi 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

język maszynowy x86_64 (Linux), 16 bajtów

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

Akceptuje pojedynczy 64-bitowy parametr liczby całkowitej RDI, konwertuje go na wartość zmiennoprzecinkową w XMM0, przechowuje te bity z powrotem RAX, a następnie oblicza ciężar Hamminga RAX, pozostawiając wynik, RAXaby mógł zostać zwrócony dzwoniącemu.

Wymaga procesora obsługującego POPCNTinstrukcję, którym byłby Intel Nehalem, AMD Barcelona i późniejsze mikroarchitekty.

Aby Spróbuj online! , skompiluj i uruchom następujący program 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));
}

C (gcc) , 82 68 bajtów

9 bajtów dzięki Neilowi.

hakowanie złego zmiennoprzecinkowego poziomu bitowego

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

Wypróbuj online!

Python 3 , 72 71 bajtów

1 bajt dzięki Lynn.

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

Wypróbuj online!

Wyjaśnienie

Format binary64 składa się z trzech elementów:

• pierwszy bit jest bitem znaku, czyli 1jeśli liczba jest ujemna
• następne 11 bitów przechowuje wykładnik z dodanym 1023
• następne 52 bity przechowują znaczenie lub mantysę.

C (gcc) , 47 bajtów

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

To nie jest przenośne; został przetestowany z gcc 7.1.1 na x86_64 z systemem Linux, bez flag kompilatora.

Wypróbuj online!

Java (OpenJDK 8) , 92 bajty

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

Wypróbuj online!

C (gcc), 63 bajty

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

To rozwiązanie opiera się na odpowiedzi @ LeakyNun, ale ponieważ nie chce poprawić swojej własnej odpowiedzi, zamieszczam tutaj bardziej golfową wersję.

Wypróbuj online

C #, 81 70 68 bajtów

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

Zaoszczędź 11 bajtów dzięki @Leaky Nun.
Zaoszczędź 2 bajty dzięki @Neil.

Wypróbuj online! Używa System.BitConverter.DoubleToInt64Bitszamiast unsafekodu, ponieważ nie mogłem zmusić TIO do pracy z nim.

Pełna / sformatowana wersja:

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 bajtów

-12 bajtów, dzięki tylko @ ASCII

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

Wypróbuj online!

JavaScript (ES6), 81 80 77 bajtów

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

Edycja: Zapisano 1 bajt dzięki @Arnauld. Zaoszczędź 3 bajty dzięki @DocMax.

Kod maszynowy x86-64, 12 bajtów na int64_twejście

6 bajtów na doublewejście

Wymaga popcntrozszerzenia ISA ( CPUID.01H:ECX.POPCNT [Bit 23] = 1).

(Lub 13 bajtów, jeśli modyfikacja argumentu w miejscu wymaga zapisania wszystkich 64-bitów, zamiast pozostawiania śmieci w górnej 32. Myślę, że uzasadnione jest twierdzenie, że osoba dzwoniąca i tak prawdopodobnie chce załadować tylko niski 32b, a x86 zero - niejawnie rozszerza się z 32 na 64 przy każdej 32-bitowej operacji. Mimo to powstrzymuje dzwoniącego przed zrobieniem add rbx, [rdi]czegoś.)

Instrukcje x87 są krótsze niż bardziej oczywiste SSE2 cvtsi2sd/ movq(używane w odpowiedzi @ ceilingcat ), a [reg]tryb adresowania ma taki sam rozmiar jak reg: tylko bajt mod / rm.

Sztuczka polegała na znalezieniu sposobu na przekazanie wartości do pamięci, bez potrzeby zbyt wielu bajtów dla trybów adresowania. (np. przekazywanie stosu nie jest takie świetne.) Na szczęście reguły zezwalają na odczytywanie / zapisywanie argumentów lub oddzielne argumenty wyjściowe , więc mogę po prostu poprosić osobę wywołującą, aby przekazała mi wskaźnik do pamięci, którą wolno mi pisać.

Można wywołać z C z podpisem: void popc_double(int64_t *in_out); Tylko niskie 32b wyniku jest prawidłowe, co może być dziwne dla C, ale naturalne dla asm. (Naprawienie tego wymaga prefiksu REX w sklepie końcowym ( mov [rdi], rax), a więc jeszcze jednego bajtu.) W systemie Windows zmień rdina rdx, ponieważ Windows nie używa ABI x86-64 System V.

Lista NASM. Łącze TIO ma kod źródłowy bez demontażu.

  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

Wypróbuj online! Obejmuje_startprogram testowy, który przekazuje mu wartość i kończy działanie ze kodem zakończenia status = wartość zwracana popcnt. (Otwórz kartę „debugowanie”, aby ją zobaczyć.)

Przekazywanie oddzielnych wskaźników wejścia / wyjścia również by działało (rdi i rsi w x86-64 SystemV ABI), ale wtedy nie możemy racjonalnie zniszczyć 64-bitowego wejścia lub tak łatwo uzasadnić potrzebę 64-bitowego bufora wyjściowego, pisząc tylko niski 32b.

Jeśli chcemy argumentować, że możemy wziąć wskaźnik do wejściowej liczby całkowitej i zniszczyć go, zwracając dane wyjściowe do rax, po prostu pomiń mov [rdi], eaxod popcnt_double_outarg, zmniejszając go do 10 bajtów.

Alternatywa bez głupich sztuczek związanych z konwencją wywoływania, 14 bajtów

użyj stosu jako miejsca na zarysowania, pushaby się tam dostać. Użyj push/, popaby skopiować rejestry w 2 bajtach zamiast 3 dla mov rdi, rsp. ( [rsp]zawsze potrzebuje bajtu SIB, więc warto wydać 2 bajty, aby skopiować rspprzed trzema instrukcjami, które go używają).

Zadzwoń z C z tym podpisem: 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.

Akceptowanie danych wejściowych w doubleformacie

Pytanie tylko mówi, że jest liczbą całkowitą w pewnym zakresie, a nie, że musi być w reprezentacji binarnej liczby całkowitej base2. Akceptacja doubledanych wejściowych oznacza, że ​​nie ma już sensu używać x87. (Chyba że użyjesz niestandardowej konwencji wywoływania, w której doubles są przekazywane do rejestrów x87. Następnie zapisz w czerwonej strefie poniżej stosu i stamtąd popcnt.)

11 bajtów:

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

Ale możemy użyć tej samej sztuczki pass-by-reference jak poprzednio, aby stworzyć wersję 6-bajtową: int pcd(const double&d);

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

6 bajtów .

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

Zaoszczędzono 1 bajt dzięki hobbs

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

Wypróbuj online!

MATLAB, 36 bajtów

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

Wykorzystując fakt, że de2bijest nie tylko krótszy niżdec2bin , ale także daje wynik w postaci zer i jedynek zamiast ASCII 48, 49.

Java (64, 61, 41 bajtów)

Całkowicie prosty w użyciu standardowej biblioteki (Java SE 5+):

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

Wkład Kevina Cruijssena (Java SE 5+):

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

Wkład Kevina Cruijssena (Java SE 8+, funkcja lambda):

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

Żeby wypróbować inne, bezpieczniejsze niż TheLethalCoder podejście, wpadłem na to (szkoda, że ​​C # ma tak długie nazwy metod):

C # (.NET Core) , 76 + 13 bajtów

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

Wypróbuj online!

Liczba bajtów obejmuje 13 bajtów using System;. Najpierw muszę przekonwertować doubleplik na taki, longktóry ma taką samą reprezentację binarną, a następnie mogę przekonwertować go na plik binarny string, a następnie liczę 1s, dzieląc ciąg i licząc podciągi minus 1.

Galaretka , 19 bajtów

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

Wypróbuj online!

dc, 79 bajtów

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

Wyjście pozostawia się na górze stosu.
Wyjaśnię później.

Wypróbuj online!

Zauważ, że liczby ujemne są poprzedzone _, a nie -.

Groovy (z parserem Parrot) , 46 bajtów

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

C, 67 bajtów

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

kod kontrolny i wyniki

#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 bajtów

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

Anonimowa funkcja, która liczy wszystkie 1s w liczbie zakodowanej jako liczba zmiennoprzecinkowa 64-bitowa.

referencje:

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