Jako dane wejściowe zostanie podana liczba całkowita k
z zakresu od -4503599627370496
(-2 52 ) do 4503599627370496
(2 52 ). 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 k
w 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 22
jest reprezentowana jako
0 10000000011 0110000000000000000000000000000000000000000000000000
Ponieważ są 5
takie, 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
źródło
binary64
formacie zmiennoprzecinkowym , jeśli chcą? Niektórzy ludzie (w tym ja, początkowo) zostały interpretacji pytanie, wymagając, aby zaakceptować funkcje wejść jako typ C na całkowitą podobnegolong
. W C możesz argumentować, że język zostanie dla ciebie przekonwertowany, tak jak podczas rozmowysqrt((int)foo)
. Ale istnieją odpowiedzi ASM na kod maszynowy x86 (takie jak codegolf.stackexchange.com/a/136360/30206 i moje), które zakładały, że musimy zaakceptować 64-bitowe liczby całkowite. Zaakceptowaniebinary64
wartości pozwoliłoby zaoszczędzić 5 bajtów.binary64
jako liczb całkowitych base2. Jeśli mimo to musisz poradzić sobie z nimi osobno, może warto zrobić coś innego niż pisanie na klawiaturze i zapętlić wszystkie bity.long
Wydaje mi się, że chciałeś zostawić opcję napisania funkcji, która zajmuje , więc nie możesz po prostu powiedzieć binarnego64double
, ponieważ nie wszystkie liczby podwójne są liczbami całkowitymi. Ale wszystkie wartości całkowitedouble
mogą być konwertowane dolong
iz powrotem, do graniclong
. (Jak zauważyłeś, odwrotność nie jest prawdą. Otrzymujesz najbliższy reprezentowalnydouble
, zakładając domyślny tryb zaokrąglania). W każdym razie był to całkowicie prawidłowy sposób postawienia pytania; Po prostu nie przeczytałem go dokładnie>. <Odpowiedzi:
MATL , 5 bajtów
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.
źródło
język maszynowy x86_64 (Linux), 16 bajtów
Akceptuje pojedynczy 64-bitowy parametr liczby całkowitej
RDI
, konwertuje go na wartość zmiennoprzecinkową wXMM0
, przechowuje te bity z powrotemRAX
, a następnie oblicza ciężar HammingaRAX
, pozostawiając wynik,RAX
aby mógł zostać zwrócony dzwoniącemu.Wymaga procesora obsługującego
POPCNT
instrukcję, którym byłby Intel Nehalem, AMD Barcelona i późniejsze mikroarchitekty.Aby Spróbuj online! , skompiluj i uruchom następujący program C:
źródło
objdump -drwC -Mintel
do dezasemblacji w składni Intela. Jeśli masz w rejestrze wskaźnik, którego możesz użyć do przechowywania / przeładowywania, możesz zapisać bajty za pomocąmovaps [rsi], xmm0
/popcnt rax, [rsi]
. (movaps ma tylko 3 bajty, 2 krótsze niż movq.) Ale to nie pomaga tutaj, ponieważ[rsp-24]
wymaga 2 dodatkowych bajtów (SIB z użycia RSP jako podstawy plus disp8). Te dodatkowe bajty są potrzebne zarówno w sklepie, jak i podczas ponownego ładowania. No cóż, myślałem, że widziałem oszczędność, ale nie: /C (gcc) ,
8268 bajtów9 bajtów dzięki Neilowi.
hakowanie złego zmiennoprzecinkowego poziomu bitowego
Wypróbuj online!
źródło
;long l=
...;l*=2;)s+=l<0;
...long
. Działa na Linuksie x86-64, ale nie działa w systemie Windows. Sugeruję powiedzenie „gcc z wersją 64-bitowąlong
”, ponieważ gcc działa na wielu platformach, wiele z nich z różnymi ABI.Python 3 ,
7271 bajtów1 bajt dzięki Lynn.
Wypróbuj online!
Wyjaśnienie
Format binary64 składa się z trzech elementów:
1
jeśli liczba jest ujemnaźródło
n and(…)-(n>0)
jest bajt krótszy, nie?C (gcc) , 47 bajtów
To nie jest przenośne; został przetestowany z gcc 7.1.1 na x86_64 z systemem Linux, bez flag kompilatora.
Wypróbuj online!
źródło
long
nadouble
w witrynie wywołującej?n
wrax
z un-zoptymalizowany kod jest dość kiepskie. Zepsuje się, jeśli włączysz-O3
, więc nie jest to tylko gcc w ogóle, to gcc na x86-64 z 64-bitamilong
z wyłączoną optymalizacją. Jeśli uwzględnisz wszystkie te wymagania w swojej odpowiedzi, głosuję. Zakładam, że istnieją platformy obsługujące gcc, które mają 64-bit,long
ale zdarza się, że pozostawiająpopcountl
wynik w rejestrze innym niż rejestr wartości zwracanej.double
powinno być w porządku. Nie mówi nic o wymaganiu od funkcji akceptacji w formacie base2. I tak, różne wersje gcc mogą emitować inny kod, więc to też ważne. (Ciekawostka: bez-mpopcnt
, gcc nie użyjepopcnt
insn i wyemituje sekwencję instrukcji w celu jego emulacji. Niektóre architektury w ogóle nie mają instrukcji popcnt, więc__builtin_popcountl
zawsze musi korzystać z sekwencji insns)__builtin_*
Funkcji ma starsze wersje, aby uniknąć generowania nielegalnych instrukcji.-march=native
używapopcntq
tylko, jeśli jest dostępny.Java (OpenJDK 8) , 92 bajty
Wypróbuj online!
źródło
C (gcc), 63 bajty
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
źródło
C #,
817068 bajtówZaoszczędź 11 bajtów dzięki @Leaky Nun.
Zaoszczędź 2 bajty dzięki @Neil.
Wypróbuj online! Używa
System.BitConverter.DoubleToInt64Bits
zamiastunsafe
kodu, ponieważ nie mogłem zmusić TIO do pracy z nim.Pełna / sformatowana wersja:
źródło
for(;l!=0;l*=2)
i nie będziesz potrzebować trójskładnikas-=l>>31
?s+=l<0?1:0
?l
jest długi, więc potrzebujes-=l>>63
?Python 2 , 69 bajtów
-12 bajtów, dzięki tylko @ ASCII
Wypróbuj online!
źródło
!
nie jest potrzebny, ponieważ kolejność bajtów nie ma tutaj znaczeniaJavaScript (ES6),
818077 bajtówEdycja: Zapisano 1 bajt dzięki @Arnauld. Zaoszczędź 3 bajty dzięki @DocMax.
źródło
g(i^i&-i,x++)
dla -1 bajtów?new Float64Array([n])
sięFloat64Array.of(n)
Kod maszynowy x86-64, 12 bajtów na
int64_t
wejście6 bajtów na
double
wejścieWymaga
popcnt
rozszerzenia 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 jakreg
: 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ńrdi
nardx
, ponieważ Windows nie używa ABI x86-64 System V.Lista NASM. Łącze TIO ma kod źródłowy bez demontażu.
Wypróbuj online! Obejmuje
_start
program 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], eax
odpopcnt_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,
push
aby się tam dostać. Użyjpush
/,pop
aby skopiować rejestry w 2 bajtach zamiast 3 dlamov rdi, rsp
. ([rsp]
zawsze potrzebuje bajtu SIB, więc warto wydać 2 bajty, aby skopiowaćrsp
przed trzema instrukcjami, które go używają).Zadzwoń z C z tym podpisem:
int popcnt_double_push(int64_t);
Akceptowanie danych wejściowych w
double
formaciePytanie tylko mówi, że jest liczbą całkowitą w pewnym zakresie, a nie, że musi być w reprezentacji binarnej liczby całkowitej base2. Akceptacja
double
danych wejściowych oznacza, że nie ma już sensu używać x87. (Chyba że użyjesz niestandardowej konwencji wywoływania, w którejdouble
s są przekazywane do rejestrów x87. Następnie zapisz w czerwonej strefie poniżej stosu i stamtąd popcnt.)11 bajtów:
Ale możemy użyć tej samej sztuczki pass-by-reference jak poprzednio, aby stworzyć wersję 6-bajtową:
int pcd(const double&d);
6 bajtów .
źródło
Perl 5 ,
3332 + 1 (-p) =3433 bajtyZaoszczędzono 1 bajt dzięki hobbs
Wypróbuj online!
źródło
d
jedno słowo (pack d,$_
zamiastpack"d",$_
)MATLAB, 36 bajtów
Wykorzystując fakt, że
de2bi
jest nie tylko krótszy niżdec2bin
, ale także daje wynik w postaci zer i jedynek zamiast ASCII 48, 49.źródło
Java (64, 61, 41 bajtów)
Całkowicie prosty w użyciu standardowej biblioteki (Java SE 5+):
Wkład Kevina Cruijssena (Java SE 5+):
Wkład Kevina Cruijssena (Java SE 8+, funkcja lambda):
źródło
Long n
i używajn.bitCount(...)
zamiastLong.bitCount(...)
. Ponadto, jeśli używasz Java 8+, możesz grać w golfa don->n.bitCount(Double.doubleToLongBits(n))
( 41 bajtów )Ż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
Wypróbuj online!
Liczba bajtów obejmuje 13 bajtów
using System;
. Najpierw muszę przekonwertowaćdouble
plik na taki,long
który ma taką samą reprezentację binarną, a następnie mogę przekonwertować go na plik binarnystring
, a następnie liczę1
s, dzieląc ciąg i licząc podciągi minus 1.źródło
using
w swojej liczbie bajtów.namespace System.Linq;{d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Count(c=>c>48)}
. Chociaż go nie testowałem, powinno działać.using
dyrektywy.namespace
się przyda. Ale tak, w tym przypadku unikanie Linq było nieco tańsze. Chciałem tylko skomentować to podejście na wypadek, gdybyś miał jakieś pomysły, jak je skrócić, aby zaoszczędzić bajty.Sum(c=>c&1)
jest krótszy. LubSum()-768
Galaretka , 19 bajtów
Wypróbuj online!
źródło
dc, 79 bajtów
Wyjście pozostawia się na górze stosu.
Wyjaśnię później.
Wypróbuj online!
Zauważ, że liczby ujemne są poprzedzone
_
, a nie-
.źródło
Groovy (z parserem Parrot) , 46 bajtów
źródło
C, 67 bajtów
kod kontrolny i wyniki
źródło
Erlang 55 bajtów
Anonimowa funkcja, która liczy wszystkie
1
s w liczbie zakodowanej jako liczba zmiennoprzecinkowa 64-bitowa.referencje:
źródło