Dodawanie z przeniesieniem

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Dodawanie z przeniesieniem (ang. addition with carry, mnemonik asemblera x86 ADC) to operacja arytmetyczna polegająca na dodaniu 2 liczb n-bitowych i jednej 1-bitowej która daje (n+1)-bitowy wynik:

Argument1 + Argument2 + Przeniesienie = 2n*Nowe_przesienienie + Wynik

Operacja ta umożliwia proste dodawanie liczb dowolnej wielkości. Bez niej potrzebny byłby znacznie większy i wolniejszy kod ze skokami warunkowymi. Jest też bardzo tania do implementacji w sprzęcie, jeśli ma on tylko dodawanie (konieczne w każdym praktycznym procesorze) oraz flagę przeniesienia (konieczną do wielu innych celów, np. porównywania liczb).

Załóżmy że ALU potrafi dodawać 8-bitowe liczby, a chcemy dodać 2 liczby 32-bitowe a i b, zapisane w 4 bajtach każda a[0], a[1], a[2], a[3] i b[0], b[1], b[2], b[3].

Najpierw dodajemy (operacją dodawania bez przeniesienia lub wyzerowawszy bit przeniesienia) najmniej znaczące bajty:

256 * Carry1 + c[0] = a[0] + b[0] + 0

Następnie trzykrotnie robimy dodawanie z przeniesieniem:

256 * Carry2 + c[1] = a[1] + b[1] + Carry1
256 * Carry3 + c[2] = a[2] + b[2] + Carry2
256 * Carry4 + c[3] = a[3] + b[3] + Carry3

Przykład[edytuj | edytuj kod]

Dodajmy liczby 3735928559 (0xDEADBEEF) i 305419896 (0x12345678) używając 8-bitowego dodawania z przeniesieniem, jak powyżej. Kolejne operacje i ich wyniki to:

Wyniki Argumenty
Nowe przeniesienie Wynik c[i] a[i] b[i] Stare przeniesienie
1 103 (0x67) 239 (0xEF) 120 (0x78) 0
1 21 (0x15) 190 (0xBE) 86 (0x56) 1
0 226 (0xE2) 173 (0xAD) 52 (0x34) 1
0 240 (0xF0) 222 (0xDE) 18 (0x12) 0

Wynik: 0xF0E21567, czyli 4041348455.