A Note on Correctness Proofs for Overflow Detection Logic in Adders for d-th Complement Numbers

Простая страница элемента
dc.creatorRederlechner,Bernd
dc.creatorKeller,Jörg
dc.date1997
dc.date.accessioned2024-02-06T12:49:06Z
dc.date.available2024-02-06T12:49:06Z
dc.descriptionWhen adding n-bit 2-th complement numbers, the result can be outside the range representable with n bits. A well-known theorem justifies the common overflow logic: Let a,b {0,1}n be the 2-th complement representations of signed integers [a] and [b], respectively, and let c0 {0, 1} be the carry-in bit. Then, [a] + [b] + c0 {-2n-1,...,2n-1-1} if and only if cn = cn-1 , where ci denotes the carry-bit from position i - 1 to position i when adding the binary numbers a and b. We present a proof of this theorem which is much shorter than previous proofs. This simplification can save valuable time in computer science classes. With a small extension the proof even holds for d-th complement numbers. Although the proof technique is known by some specialists, nobody seems to have written it up. With this note, it is once documented in a precise form, thus avoiding re-invention.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-003-10-1121
dc.identifierhttps://lib.jucs.org/article/27417/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/7236
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 3(10): 1121-1125
dc.subjectd-ary arithmetic
dc.subjectcorrectness proof
dc.subjectcomputer science education
dc.subjectoverflow testing
dc.titleA Note on Correctness Proofs for Overflow Detection Logic in Adders for d-th Complement Numbers
dc.typeResearch Article
Файлы
Коллекции