Perl, 137 znaków
($x,$y)=<>;while($x=~s/.. *//s){$e=hex$&;$i=0;$s=$r[$i]+=$e*hex,$r[$i]&=255,$r[++$i]+=$s>>8 for$y=~/.. */gs;$y="00$y"}printf'%02x 'x@r,@r
Ostrzeżenia
- Czasami drukuje dodatkowy
00bajt na końcu wyniku. Oczywiście wynik jest nadal poprawny, nawet z tym dodatkowym bajtem.
- Drukuje dodatkową spację po ostatnim bajcie szesnastkowym w wyniku.
Wyjaśnienie
Wyjaśnienie to będzie trochę długie, ale myślę, że większość ludzi uzna to za interesujące.
Po pierwsze, kiedy miałem 10 lat, nauczyłem się następującej małej sztuczki. Możesz pomnożyć przez to dowolne dwie liczby dodatnie. Opiszę to na przykładzie 13 × 47. Zaczynasz od napisania pierwszej liczby, 13, i podzielenia jej przez 2 (za każdym razem zaokrąglaj w dół), aż osiągniesz 1:
13
6
3
1
Teraz, obok 13, napisz drugą liczbę, 47, i mnoż ją przez 2 tyle samo:
13 47
6 94
3 188
1 376
Teraz wykreślisz wszystkie linie, w których liczba po lewej jest parzysta . W tym przypadku jest to tylko 6. (Nie mogę przekreślić kodu, więc po prostu go usunę). Na koniec dodajesz wszystkie pozostałe liczby po prawej stronie:
13 47
3 188
1 376
----
611
I to jest właściwa odpowiedź. 13 × 47 = 611.
Teraz, ponieważ wszyscy jesteście maniaków komputerowych, będziesz sobie sprawę, że to, co my właściwie robi w lewej i prawej kolumny jest x >> 1i y << 1, odpowiednio. Ponadto dodajemy ytylko jeśli x & 1 == 1. To przekłada się bezpośrednio na algorytm, który napiszę tutaj w pseudokodzie:
input x, y
result = 0
while x > 0:
if x & 1 == 1:
result = result + y
x = x >> 1
y = y << 1
print result
Możemy ponownie napisać, ifaby użyć mnożenia, a następnie możemy łatwo to zmienić, aby działało na zasadzie bajt po bajcie zamiast bit po bicie:
input x, y
result = 0
while x > 0:
result = result + (y * (x & 255))
x = x >> 8
y = y << 8
print result
To wciąż zawiera mnożenie y, które ma dowolny rozmiar, więc musimy też zmienić to w pętlę. Zrobimy to w Perlu.
Teraz przetłumacz wszystko na Perla:
$xi $ysą nakłady w formacie hex, więc mają one najmniejszy bajt pierwszy .
Dlatego zamiast tego x >> 8robię $x =~ s/.. *//s. Potrzebuję spacji + gwiazdy, ponieważ ostatni bajt może nie mieć na nim spacji (mógłby użyć spacji + ?). To automatycznie wstawia usunięty byte ( x & 255) do $&.
y << 8jest po prostu $y = "00$y".
resultJest rzeczywiście tablica liczbowa @r. Na koniec każdy element @rzawiera jeden bajt odpowiedzi, ale w połowie obliczeń może zawierać więcej niż jeden bajt. Udowodnię ci poniżej, że każda wartość nigdy nie jest większa niż dwa bajty (16 bitów) i że wynik jest zawsze jeden bajt na końcu.
Oto kod Perla rozwiązany i skomentowany:
# Input x and y
($x, $y) = <>;
# Do the equivalent of $& = x & 255, x = x >> 8
while ($x =~ s/.. *//s)
{
# Let e = x & 255
$e = hex $&;
# For every byte in y... (notice this sets $_ to each byte)
$i = 0;
for ($y =~ /.. */gs)
{
# Do the multiplication of two single-byte values.
$s = $r[$i] += $e*hex,
# Truncate the value in $r[$i] to one byte. The rest of it is still in $s
$r[$i] &= 255,
# Move to the next array item and add the carry there.
$r[++$i] += $s >> 8
}
# Do the equivalent of y = y << 8
$y = "00$y"
}
# Output the result in hex format.
printf '%02x ' x @r, @r
Teraz dowód, że to zawsze generuje bajty i że obliczenia nigdy nie generują wartości większych niż dwa bajty. Udowodnię to przez indukcję w whilepętli:
Pusty @rna początku wyraźnie nie ma w nim wartości większych niż 0xFF (ponieważ nie ma w nim żadnych wartości). To kończy przypadek podstawowy.
Teraz, biorąc pod uwagę, że @rzawiera tylko pojedyncze bajty na początku każdej whileiteracji:
forPętla wyraźnie &=s wszystkie wartości w tablicy wynikowej z 255 wyjątkiem ostatniego , więc tylko trzeba spojrzeć na tego ostatniego.
Wiemy, że zawsze usuwamy tylko jeden bajt $xi $y:
Dlatego $e*hexjest mnożeniem dwóch jednobajtowych wartości, co oznacza, że należy do zakresu 0 — 0xFE01.
Zgodnie z hipotezą indukcyjną $r[$i]jest jeden bajt; dlatego $s = $r[$i] += $e*hexjest w zakresie 0 — 0xFF00.
Dlatego $s >> 8zawsze ma jeden bajt.
$yrośnie 00w każdej iteracji whilepętli:
Dlatego w każdej iteracji whilepętli wewnętrzna forpętla działa o jeszcze jedną iterację niż w poprzedniej whileiteracji.
Dlatego $r[++$i] += $s >> 8w ostatniej iteracji forpętli zawsze dodaje $s >> 8się 0i już ustaliliśmy, że $s >> 8zawsze jest to jeden bajt.
Dlatego ostatnia wartość przechowywana @rna końcu forpętli jest również pojedynczym bajtem.
To kończy wspaniałe i ekscytujące wyzwanie. Wielkie dzięki za opublikowanie go!