Wykładnik w zapisie dwójkowym

Szybkie potęgowanie iteracyjnie i zapis dwójkowy wykładnika - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Wykładnik zapisany dwójkowo to suma potęg dwójki: `13 = 1101₂ = 8 + 4 + 1`, więc `x¹³ = x⁸ · x⁴ · x¹`. Kolejne potęgi `x, x², x⁴, x⁸, ...` powstają przez podnoszenie do kwadratu, a do wyniku mnoży się tylko te, przy których w zapisie wykładnika stoi jedynka. Program wypisuje to rozbicie dla `3¹³`.

x, n = 3, 13
print(n, "=", bin(n)[2:])
result = 1
square = x
k = 0
while n > 0:
    if n % 2 == 1:
        print("bit", k, "= 1: mnożę przez", square)
        result *= square
    square *= square
    n //= 2
    k += 1
print(result, 3 ** 13)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.