extern io_get_udec, io_print_dec
section .bss
N resd 1
K resd 1
ans resd 1
zeros resd 1
len resd 1
mask resd 1
section .text
global main
main:
call io_get_udec
mov [N], eax
call io_get_udec
mov [K], eax
mov dword [ans], 0
mov dword [zeros], 0
; считаем длину N в битах
mov eax, [N]
xor ecx, ecx
count_len:
test eax, eax
jz len_done
inc ecx
shr eax, 1
jmp count_len
len_done:
mov [len], ecx
; числа с меньшей длиной: sum C(l-1, K)
mov esi, 1 ; текущая длина
less_loop:
cmp esi, [len]
jge same_len
mov eax, esi
dec eax ; n = l - 1
mov edx, [K] ; k = K
call Cnk
add [ans], eax
inc esi
jmp less_loop
same_len:
; mask = 1 << (len - 2), пропускаем старший бит
mov ecx, [len]
cmp ecx, 1
jbe check_N
sub ecx, 2
mov eax, 1
shl eax, cl
mov [mask], eax
scan_bits:
mov eax, [mask]
test eax, eax
jz check_N
mov ebx, [N]
test ebx, eax
jz bit_is_zero
; если в N стоит 1, можно поставить 0 и добрать справа
mov eax, [K]
mov edx, [zeros]
inc edx
sub eax, edx ; need = K - zeros - 1
js next_bit
mov edx, eax ; k = need
; считаем количество битов справа
mov eax, [mask]
xor ecx, ecx
right_count:
shr eax, 1
test eax, eax
jz right_done
inc ecx
jmp right_count
right_done:
mov eax, ecx ; n = bits_right
call Cnk
add [ans], eax
jmp next_bit
bit_is_zero:
inc dword [zeros]
next_bit:
shr dword [mask], 1
jmp scan_bits
check_N:
mov eax, [zeros]
cmp eax, [K]
jne print_answer
inc dword [ans]
print_answer:
mov eax, [ans]
call io_print_dec
xor eax, eax
ret
; C(n, k)
; вход: eax = n, edx = k
; выход: eax = C(n, k)
Cnk:
push ebx
push ecx
push esi
push edi
cmp edx, eax
ja C_zero
cmp edx, 0
je C_one
mov esi, eax ; n
mov ecx, edx ; k
mov ebx, 1 ; result
mov edi, 1 ; i
C_loop:
cmp edi, ecx
ja C_done
mov eax, esi
sub eax, edi
inc eax ; n - i + 1
mul ebx ; edx:eax = eax * result
div edi ; eax /= i
mov ebx, eax
inc edi
jmp C_loop
C_done:
mov eax, ebx
jmp C_ret
C_zero:
xor eax, eax
jmp C_ret
C_one:
mov eax, 1
C_ret:
pop edi
pop esi
pop ecx
pop ebx
ret