Dodawanie z przeniesieniem
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
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.