Перл, 137 символов
mul
Предостережения
- Иногда печатает доп.
// sed -i -e 's#//#;#g' dosmult.asm
// nasm -f bin dosmult.asm -o dosmult.com
// The default, but never harmed anyone.
[bits 16]
// 8086 code only! If I use 386 instructions or any of that,
// I would ruin the challenge.
[cpu 8086]
// COM files start at 100h.
org 100h
section .text
start:
// Create a 400 byte buffer on the stack.
// 200 will be reserved for the input, and 200 for the output.
mov cx, 200
// Save 200 in BP for later, it will be useful.
mov bp, cx
// Push 0 200 times making a 400 byte zeroed buffer on the stack
xor ax, ax
rep push ax
mov di, sp
// Read the first line of hex digits.
.getline_loop:
call gethex
// Swap DL to AL and store with STOSB
xchg dx, ax
stosb
// Loop if it was a space
jz .getline_loop
// Get length
sub di, sp
// Store length in BX
xchg di, bx
// Save the pointer to input in SI
mov si, sp
// Load the pointer to output in DI (SI + 200)
lea di, [si + bp]
// Begin multiplication, grade school byte by byte
// Instead of creating a third buffer, we process the data
// as the user inputs it.
.loop:
call gethex
// Save flags from gethex so we know when to stop
pushfw
// Save SI and DI
push si
push di
// Loop counter
mov cx, bx
.mult_loop:
// Load next byte from first input
lodsb
// Multiply by the input byte
mul dl
// 16-bit add to [DI]
// We actually add to AX, then do STOSW.
add ax, [di]
stosw
// Add the carry bit.
adc word [di], 0
// Decrement DI after STOSW incremented it by 2 to iterate
// on each byte.
dec di
// while (--cx)
loop .mult_loop
.mult_loop_end:
// Restore DI and SI
pop di
pop si
// Increment output pointer
inc di
// Restore flags from gethex
popfw
// Jump if we got a space.
jz .loop
.loop_end:
// Was there a trailing zero?
cmp byte[di + bx], 0
jz .nodec
.dec:
// If so, decrement the count.
dec bx
.nodec:
// Calculate the length with ugly pointer arithmetic.
// I feel there is a better way to do this.
add di, bx // ptr += len
add sp, bp // sp += 200 (sp = output)
sub di, sp // ptr -= output
// Store output array in SI.
mov si, sp
// Print each byte in hex
.print_loop:
// Load byte
lodsb
// puthex(AL >> 4)
mov bl, al
mov cl, 4
shr al, cl
call puthex
// puthex(AL & 0Fh)
xchg ax, bx
and al, 0Fh
call puthex
// putc(' ')
mov al, ' '
call putc
// Loop for every byte from DI.
dec di
jnz .print_loop
.print_loop_end:
// exit, not bothering to clean anything up. :P
int 20h
// Prints hex digit in AL.
// Must be <= 0fh
puthex:
cmp al, 9
jbe .no_hexa
.hexa:
add al, 'a' - '9' - 1
.no_hexa:
add al, '0'
// Fallthrough
// Prints AL to stdout.
putc:
mov ah, 2h
mov dl, al
int 21h
ret
// Reads a hex byte.
// Returns in DL.
// Sets whether it ended in a space in the Z flag.
gethex:
mov dl, 0
.start:
// Read char into AL
mov ah, 1h
int 21h
// Subtract ASCII '0'
sub al, '0'
// If we hit a space or newline, they will trigger the 'below'
// condition
jb .ret
// Was AL '0'-'9'? If not, correct it to 'a'-'f'.
cmp al, 10
jb .no_hexa
.hexa:
// Correct AL
sub al, 'a' - '9' - 1
.no_hexa:
// DL = (DL << 4) + AL
// 8086 doesn't have shift by immediate.
mov cl, 4
shl dl, cl
// Add to BL
add dl, al
// Loop
jmp .start
.ret:
// Check if AL before the subtraction was a space.
cmp al, ' ' - '0'
ret
byte at the end of the result. Of course the result is still correct even with that extra byte.
- Печатает дополнительный пробел после последнего шестнадцатеричного байта результата.
Объяснение
Объяснение будет немного длинным, но я думаю, что большинству людей оно покажется интересным.
Прежде всего, когда мне было 10 лет, меня научили следующему маленькому трюку. С его помощью вы можете умножить любые два положительных числа. Я опишу это на примере 13×47. Вы начинаете с написания первого числа, 13, и разделяющий его на 2 (каждый раз округляя вниз), пока не достигнете 1:
00000000: b9 c8 00 89 cd 31 c0 f3 50 89 e7 e8 5d 00 92 aa .....1..P...]...
00000010: 74 f9 29 e7 87 fb 89 e6 8d 3a e8 4e 00 9c 56 57 t.)......:.N..VW
00000020: 89 d9 ac f6 e2 03 05 ab 83 15 00 4f e2 f4 5f 5e ...........O.._^
00000030: 47 9d 74 e6 80 39 00 74 01 4b 01 df 01 e5 29 ef G.t..9.t.K....).
00000040: 89 ee ac 88 c3 b1 04 d2 e8 e8 10 00 93 24 0f e8 .............$..
00000050: 0a 00 b0 20 e8 0d 00 4f 75 e8 cd 20 3c 09 76 02 ... ...Ou.. <.v.
00000060: 04 27 04 30 b4 02 88 c2 cd 21 c3 b2 00 b4 01 cd .'.0.....!......
00000070: 21 2c 30 72 0e 3c 0a 72 02 2c 27 b1 04 d2 e2 00 !,0r.<.r.,'.....
00000080: c2 eb ea 3c f0 c3 ...<..
Теперь рядом с числом 13 напишите другое число, 47, и сохраните его. умножение это в 2 такое же количество раз:
x=>y=>x.map((t,i)=>y.map(u=>(f=i=>(c=s[i]>>8)&&f(i++,s[i]=c+~~s[i],s[i-1]%=256))(i,s[i]=~~s[i++]+`0x${t}`*`0x${u}`)),s=[])&&s.map(t=>(t<16?0:'')+t.toString(16))
Теперь вычеркните все строки, где слева стоит цифра даже. В данном случае это только цифра 6. (Я не могу зачеркнуть ее в коде, поэтому просто удалю ее.) Наконец, вы добавляете все оставшиеся цифры справа:
$ ./long
fd 66 03 a7 04
01 00 00 00 fe ff ff ff
00 05 10 22 34 2d 1c
01 03 06 09 0c 0f 0b 06
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 02
И это правильный ответ. 13 × 47 = 611.
Теперь, поскольку вы все компьютерные фанаты, вы поняли, что то, что мы на самом деле делаем в левом и правом столбцах, int main(void){
m("1f 4a 07\n63 a3\n");
m("ff ff ff ff\nff ff ff ff\n");
m("10 20 30 40\n50 60 70\n");
m("01 02 03 04 05 06\n01 01 01\n");
m("00 00 00 00 00 00 00 00 00 00 00 00 01\n00 00 00 00 00 00 00 00 02\n");
return 0;
}
and typedef unsigned char u8;
#define x calloc
#define f for
#define l p++
#define E *p>57?*p-87:*p-48
#define g(a) --i;--a;continue
void m(u8*d){short n=0,m=0,a,b,i,k,s;u8*t,*q,*r,*p=d,o;f(;*p!=10;n++,l){}l;f(;*p
!=10;m++,l){}t=x(n,1);q=x(m,1);r=x(n,1);p=d;a=n;i=0;f(;*p!=10;i++,l){if(*p==32){
g(a);}t[i]=E;t[i]<<=4;l;t[i]|=E;}a/=2;b=m;i=0;l;f(;*p!=10;i++,l){if(*p==32){g(b)
;}q[i]=E;q[i]<<=4;l;q[i]|=E;}b/=2;f(k=0;k<8*b;k++){if(q[0]&1){o=0;f(i=0;i<n;i++)
{s=o+t[i]+r[i];o=s>>8;r[i]=s&255;}}f(i=n;i;i--){o=t[i-1]>>7&1;t[i-1]*=2;if(i!=n)
t[i]|=o;}f(i=0;i<m;i++){o=q[i]&1;q[i]/=2;if(i)q[i-1]|=(o<<7);}}k=(r[a+b-1]==0)?a
+b-1:b+a;f(i=0;i<k;i++){printf("x ",r[i]);}putchar(10);}
, соответственно. Кроме того, мы добавляем # m "1f 4a 07" "63 a3" ;;
- : string = "fd 66 03 a7 04"
# m "ff ff ff ff" "ff ff ff ff" ;;
- : string = "01 00 00 00 fe ff ff ff"
only if let(@)=List.map
let m a b=Char.(String.(let e s=of_list(((^)"0x"|-to_int|-chr)@nsplit s" ")in
let a,b=e a,e b in let m,n=length a,length b in let c=make(m+n)'\000'in
iteri(fun i d->let s,x=ref 0,code d in iteri(fun j e->let y=code e in
s:=!s+code c.[i+j]+x*y;c.[i+j]<-chr(!s mod
256);s:=!s/256)b;c.[i+n]<-chr!s)a;join" "((code|-Printf.sprintf"x")@to_list c)))
. Это преобразуется непосредственно в алгоритм, который я напишу здесь в псевдокоде:
s
Мы можем переписать for to use a multiplication, and then we can easily change this so that it works on a byte-by-byte basis instead of bit-by-bit:
@r
Это все еще содержит умножение на $s >> 8 , which is arbitrary-size, so we need to change that into a loop too. We’ll do that in Perl.
Теперь переведем все на Perl:
0 and $s >> 8 являются входными данными в шестнадцатеричном формате, поэтому они имеют наименее значащий байт первый.
Таким образом, вместо for I do $r[++$i] += $s >> 8 . Мне нужен пробел+звезда, потому что в последнем байте может не быть пробела (можно использовать пробел+ while too). This automatically puts the removed byte ( for ) в while .
while is simply 00 .
$y is actually a numerical array, $s >> 8 . В конце каждый элемент 0 — 0xFF00 contains one byte of the answer, but halfway through the calculation it may contain more than one byte. I’ll prove to you below that each value is never more than два байтов (16 бит) и что результат всегда равен одному байту в конце.
Итак, вот код Perl, раскрытый и прокомментированный:
$s = $r[$i] += $e*hex
Теперь для доказательства того, что это всегда выводит байтыи что расчет никогда не генерирует значения, превышающие два байты. Я докажу это индукцией по $r[$i] loop:
Пустой 0 — 0xFE01 at the beginning clearly has no values greater than 0xFF in it (because it has no values in it at all). This concludes the base case.
Теперь, учитывая, что $e*hex contains only single bytes at the beginning of each $y итерация:
$x loop explicitly &= s все значения в массиве результатов с 255 кроме последнего, поэтому нам нужно посмотреть только на последний.
Мы знаем, что всегда удаляем только один байт из for and while :
Поэтому, @r is a multiplication of two single-byte values, which means it’s in the range @r .
По индуктивному предположению, while is one byte; therefore, # 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 'x ' x @r, @r
находится в диапазоне @r .
Поэтому, @r is always one byte.
result grows an extra $y = "00$y" в каждой итерации y << 8 loop:
Таким образом, на каждой итерации $& loop, the inner x & 255 цикл выполняется на одну итерацию больше, чем в предыдущем ? iteration.
Таким образом, $x =~ s/.. *//s in the last iteration of the x >> 8 цикл всегда добавляет $y to $x , и мы уже установили, что y is always one byte.
Таким образом, последнее значение, сохраненное в input x, y
result = 0
while x > 0:
result = result + (y * (x & 255))
x = x >> 8
y = y << 8
print result
at the end of the if цикл также представляет собой один байт.
На этом замечательная и захватывающая задача завершается. Большое спасибо за публикацию!
![[КЕЙС] Белила для трафа: 200-1000руб. в день на автомате без вложений](/assets/images/icons/forum6.png){kind=icon}
![Поток Клиентов Из Инстаграм: Интенсив [александра Гуреева]](/assets/images/icons/forum3.png){kind=icon}
