Перенос и переполнение - что они представляют собой на самом деле? — Архив WASM.RU
Данная статья ни в коем случае не претендует на полноту описания, и представляет собой лишь краткое дополнение к тем солидным учебным пособиям и справочникам, которые должны быть под рукой у каждого программиста. Просто мне не удалось найти ни в одном из подобных изданий тех элементарных сведений, которые будут изложены ниже. Видимо, авторам этот вопрос кажется настолько тривиальным и очевидным, что они не заостряют на нем внимания, полагая, что двух - трех строк достаточно для полного понимания. Однако это далеко не так - вопрос выходит далеко за те рамки, в которые его пытаются загнать авторы. А дело вот в чем.
Любой начинающий работать на языке Ассемблера программист рано или поздно в своей деятельности доходит до изучения команд, изменяющих флаги переноса и переполнения в соответствии с определенными правилами. К таковым относятся, например, команды сложения, вычитания, умножения, логических и арифметических сдвигов. Естественно, работа с этими командами требует четкого понимания понятий переноса и переполнения. (Если быть более точным, следует осознавать, каким образом знаковые или беззнаковые числа, сочетаясь в арифметических командах, дают различные комбинации флагов переноса и переполнения. Это - азбука начинающего программиста, и без ее освоения дальнейшая работа невозможна).
Раскроем любой учебник по языку Ассемблера, например, очень хороший учебник В.Юрова "Ассемблер: учебный курс". Какую информацию он содержит по нашему вопросу?
В таблице "Флаги состояния" находим следующие сведения:
"... Флаг переноса CF ... устанавливается в 1, если арифметическая операция произвела перенос из старшего бита результата. Старшим является 7, 15 или 31-й бит в зависимости от размерности операнда."
"... Флаг переполнения OF ... устанавливается в 1, если в результате операции происходит перенос (заем) в(из) старшего, знакового бита результата (биты 7, 15 или 31 для 8, 16 или 32-разрядных операндов соответственно)."Это интересно. Получается, что автор учебника предлагает нам согласиться с тем, что:
1) Перенос происходит тогда, когда единица выносится за пределы разрядной сетки (при операции сложения) или занимается из этих пределов (при операции вычитания);
2) Переполнение происходит тогда, когда единица выносится в последний разряд числа (при операции сложения) или занимается из этого разряда (при операции вычитания).
Проверим, так ли это на самом деле. Сложим в программе два числа и проанализируем получившийся код отладчиком, обращая особое внимание на состояние флагов OF (переполнения) и CF (переноса) до и после выполнения команды. Например:mov al, 10000000b ;//Произошел вынос единицы ТОЛЬКО за
mov bl, 10000000b ;//пределы разрядной сетки, однако...
add al, bl ;//...есть и переполнение (OF=1), ;//и перенос (CF=1)
mov al, 11111111b ;//Имели место выносы единицы КАК за
mov bl, 00000001b ;//пределы разрядной сетки, так и в старший
add al, bl ;//бит, однако перенос есть, а переполнения нетНалицо явное противоречие теории, изложенной в учебнике, и действительности, открывшейся после манипуляций с отладчиком. Что же, продолжим изучение теории. Что утверждают в своем учебнике "Язык Ассемблера и организация ЭВМ" В.Сорокин и В.Сарычев?
"... Флаг переноса CF устанавливается в единицу, если произошел перенос из самого старшего разряда числа при команде сложения или если требуется заем для самого старшего разряда уменьшаемого при вычитании."
"... Флаг переполнения OF используется как индикатор переполнения при работе с числами со знаком. Он устанавливается в 1, если результат операции над числами со знаком выйдет за пределы допустимого диапазона результата и устанавливается в 0 в противном случае."По порядку установки флага переноса авторы не сообщили нам ничего нового. Более интересна информация о флаге переполнения, где вскользь упоминается о его зависимости от наличия у числа знака; чтобы выяснить, отличаются ли данные сведения от тех, что были найдены в предыдущем учебнике, произведем краткий экскурс в теорию знаковых и беззнаковых чисел, и вспомним, чем они отличаются друг от друга.
На уровне машинных команд между этими двумя видами чисел нет никакой разницы. Находящийся в памяти или в одном из регистров операнд представляет собой (в зависимости от используемой модели адресации) 8-,16- или 32-разрядное число, все разряды которого абсолютно равноправны. Понятие знака введено исключительно для возможности манипулирования (на логическом уровне) с отрицательными числами - для процессора все числа одинаковы, а для программиста они отличаются тем, что для одних высший разряд выступает в качестве информации о знаке числа (знаковые числа), а для других все разряды несут информации о самом числе (беззнаковые числа). Естественно, выделение одного разряда под знак приводит к уменьшению возможной величины знакового числа вдвое 1; так, максимальное значение беззнакового 8-разрядного числа равно 11111111b, или 255, максимальное же (минимальное) значение аналогичного знакового числа равно соответственно 01111111b, или 127 (-128, или 10000000b). Если старший разряд знакового числа равен 1, число считается отрицательным, если 0 - положительным. Чтобы определить величину знакового числа, следует обратить в нем все биты (изменить их значения с 0 на 1 и наоборот), и приписать к полученному модулю (он считается беззнаковым) знак (-), если старший бит искомого числа был равен 1 2. Исходя из этого, становится понятным различие на 1 в диапазонах для положительных и отрицательных величин (127,-128) - для последних может использоваться старший бит, который и дает единичную прибавку. Легко видеть, что больше 127 (меньше -128) знаковое число быть не может, поскольку для этих величин все информационные разряды уже взведены (сброшены), и дальнейшее увеличение (уменьшение) числа приведет к переносу в знаковый разряд (заему из него) и, соответственно, изменению знака числа...
... а это и есть пересказ иными словами того, что написано по поводу флага переполнения в учебнике "Язык Ассемблера и организация ЭВМ". То есть и здесь авторы не сообщили нам ничего нового - речь идет все о том же пресловутом переносе в знаковый бит (старший разряд). А это, как мы уже убедились, не соответствует действительности.Популярные учебники не могут помочь нам в выяснении того, когда при выполнении арифметических команд возникает перенос, а когда - переполнение. Остается выяснить это самостоятельно, складывая между собой различные числа во всевозможных комбинациях, и анализируя состояние флагов OF и CF. При этом каждая пара чисел будет интерпретироваться дважды - сперва как две знаковых, затем как две беззнаковых величины.
mov al, 00111111b ;//Нет ни переполнения,ни переноса
mov bl, 00000001b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: нет
add al, bl ;//Вынос за разрядную сетку - нет
mov al, 11111101b ;//Перенос есть,переполнения нет
mov bl, 00000101b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 253 + 5 = 2 (неверно) ; ИЛИ -3 + 5 = 2 (верно)
mov al, 11111100b ;//Перенос есть,переполнения нет
mov bl, 00000101b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 252 + 5 = 1 (неверно) ИЛИ -4 + 5 = 1 (верно)
mov al, 01000000b ;//Перенос есть,переполнения нет
mov bl, 11000000b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 64 + 192 = 0 (неверно) ИЛИ 64 - 64 = 0 (верно)
mov al, 11100000b ;//Перенос есть,переполнения нет
mov bl, 01100000b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 224 + 96 = 64 (неверно) ИЛИ -32 + 96 = 64 (верно)
mov al, 01100000b ;//Перенос есть,переполнения нет
mov bl, 11100000b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 96 + 224 = 64 (неверно) ИЛИ 96 - 32 = 64 (верно)
mov al, 11100000b ;//Перенос есть,переполнения нет
mov bl, 11100000b ;//7-й бит: стал равен 1; перенос в 7-й бит:есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 224 + 224 = 192 (неверно) ИЛИ -32 - 32 = -64(верно)
mov al, 11000000b ;//Перенос есть,переполнения нет
mov bl, 11000000b ;//7-й бит: стал равен 1 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 192 + 192 = 128 (неверно) ИЛИ -64 - 64 = -128(верно)
mov al, 11111111b ;//Перенос есть,переполнения нет
mov bl, 00000001b ;//7-й бит: стал равен 0 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 255 + 1 = 0 (неверно) ИЛИ -1 + 1 = 0 (верно)
mov al, 11111111b ;//Перенос есть,переполнения нет
mov bl, 10000001b ;//7-й бит: стал равен 1 ; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 255 + 129 = 128 (неверно) ИЛИ -1 - 127 = -128 (верно)
mov al, 11111111b ;//Перенос есть,переполнения нет
mov bl, 11000001b ;//7-й бит: стал равен 1; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 255 + 193 = 192 (неверно) ИЛИ -1 - 63 = -64 (верно)
mov al, 11111111b ;//Перенос есть,переполнения нет
mov bl, 01000001b ;//7-й бит: стал равен 0; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - есть
;// 255 + 65 = 64 (неверно) ИЛИ -1 + 65 = 64 (верно)
mov al, 01000000b ;//Переполнение есть,переноса нет
mov bl, 01000000b ;//7-й бит: стал равен 1; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - нет
;// 64 + 64 = 128 (верно) ИЛИ +64 + +64 = -128(неверно)
mov al, 01100000b ;//Переполнение есть,переноса нет
mov bl, 01100000b ;//7-й бит: стал равен 1; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - нет
;// 96 + 96 = 192 (верно) ИЛИ +96 + +96 = -64 (неверно)
mov al, 01111111b ;//Переполнение есть,переноса нет
mov bl, 00000001b ;//7-й бит: стал равен 1; перенос в 7-й бит: есть
add al, bl ;//Вынос за разрядную сетку - нет
;// 127 + 1 = 128 (верно) ИЛИ +127 + +1 = -128 (неверно)
mov al, 10000000b ;//Есть и перенос,и переполнение
mov bl, 10000000b ;//7-й бит: стал равен 0; перенос в 7-й бит: нет
add al, bl ;//Вынос за разрядную сетку - есть
;// 128 + 128 = 0 (неверно) ИЛИ -128 - 128 = 0 (неверно)Итак, установка флажков переноса и переполнения производится по следующим правилам:
ПЕРЕНОС БЕЗ ПЕРЕПОЛНЕНИЯ (CF=1, OF=0) - тогда,когда производится перенос единицы в знаковый разряд (7,15,31-й) и перенос единицы из разрядной сетки (из 7,15 или 31-го разрядов в 8,16,32, несуществующие для регистра указанной размерности).
Сложение БЕЗЗНАКОВЫХ чисел при возникновении переноса протекает неправильно (ТОЛЬКО из-за переноса из разрядной сетки - перенос в знаковый разряд роли не играет). При интерпретации слагаемых как беззнаковых чисел перенос из разрядной сетки приводит к потере старших разрядов числа, и результат оказывается неверным.
Сложение ЗНАКОВЫХ чисел при возникновении переноса протекает правильно, так как при такой интерпретации слагаемые представляют собой ЛИБО пару "ПОЛОЖИТЕЛЬНОЕ ЧИСЛО + ОТРИЦАТЕЛЬНОЕ ЧИСЛО" (старший бит одного слагаемого равен 0, а второго - 1, и перенос из шестого (четырнадцатого, тридцатого) бита приводит к переносу в старший и переносу из разрядной сетки), и результат такого сложения не может быть неправильным - он будет находиться в пределах -128 - +127; ЛИБО пару "ДВА ОТРИЦАТЕЛЬНЫХ ЧИСЛА,СУММА КОТОРЫХ НЕ МЕНЬШЕ -128" (это означает, что сочетания единичных битов первого и второго слагаемых ОБЯЗАТЕЛЬНО приведут к переносу в старший разряд в то время,как будет произведен перенос из разрядной сетки, и знаковый бит не будет потерян; для этого и налагается условие на сумму - -127 - 1, -120 - 8, -64 - 64, НО НЕ - -127 - 2, -64 - 65). В последних случаях возникает перенос с переполнением, так как производится только перенос из разрядной сетки.
ПЕРЕПОЛНЕНИЕ БЕЗ ПЕРЕНОСА (OF=1, CF=0) - тогда, когда производится ТОЛЬКО перенос единицы в знаковый разряд.
Сложение ЗНАКОВЫХ чисел при возникновении переполнения протекает неправильно, так как слагаемые могут представлять собой ТОЛЬКО беззнаковые числа (иначе при переносе единицы из шестого бита наличие единицы в знаковом разряде приведет к переносу из разрядной сетки; в результате переполнения не будет,а будет перенос). Поэтому перенос единицы в знаковый разряд приводит к появлению знакового (отрицательного) числа, что неправильно - сложение двух положительных чисел может иметь результатом только положительное число.
Сложение БЕЗЗНАКОВЫХ чисел в данном случае протекает правильно,так как для этих чисел 7-й бит не играет особой роли и представляет собой лишь добавочный разряд; перенос в него не приводит к ошибке.
ПЕРЕНОС С ПЕРЕПОЛНЕНИЕМ (CF=1,OF=1) - тогда,когда производится ТОЛЬКО перенос единицы из разрядной сетки.
Сложение БЕЗЗНАКОВЫХ чисел в данном случае протекает неправильно, так как перенос единицы из разрядной сетки приводит к потере старшего разряда.
Сложение ЗНАКОВЫХ чисел ТОЖЕ протекает неправильно, так как в результате переноса из разрядной сетки теряется знаковый бит,и сумма двух отрицательных чисел (а перенос с переполнением возможен только при сложении двух отрицательных чисел,т.к. для переноса единицы из разрядной сетки без переноса в знаковый бит необходимы единицы в старших разрядах обоих слагаемых) превращается в положительное число,что неправильно.
ОТСУТСТВИЕ ПЕРЕНОСА И ПЕРЕПОЛНЕНИЯ - тогда, когда нет переносов ни в знаковый разряд, ни из разрядной сетки.
На основании всего вышеизложенного может быть составлена следующаяИстинная таблица установки флагов переноса и переполнения для сложения:
Перенос из разрядной сетки Перенос в знаковый бит Флаги Есть Есть CF=1, OF=0 Есть Нет CF=1, OF=1 Нет Есть CF=0, OF=1 Нет Нет CF=0, OF=0 Совершенно аналогично операциям сложения можно произвести ряд операций вычитания над знаковыми и беззнаковыми числами, отслеживая зависимость флагов OF и CF от наличия заемов из старшего и из "запредельного" разрядов.
mov al, 11100000b ;//Нет ни переполнения,ни переноса
mov bl, 00100000b ;//Заем в 7-й бит: нет; заем из 7-го бита: нет
sub al, bl
mov al, 00111111b ;//Перенос есть,переполнения нет
mov bl, 11111111b ;//Заем в 7-й бит: есть; заем из 7-го бита: есть
sub al, bl
mov al, 10000011b ;//Перенос есть,переполнения нет
mov bl, 10011010b ;//Заем в 7-й бит: есть; заем из 7-го бита: есть
sub al, bl
mov al, 10000000b ;//Перенос есть,переполнения нет
mov bl, 10000001b ;//Заем в 7-й бит: есть; заем из 7-го бита: есть
sub al, bl
mov al, 10000000b ;//Перенос есть,переполнения нет
mov bl, 11000000b ;//Заем в 7-й бит: есть; заем из 7-го бита: есть
sub al, bl
mov al, 10001010b ;//Перенос есть,переполнения нет
mov bl, 10100101b ;//Заем в 7-й бит: есть; заем из 7-го бита: есть
sub al, bl
mov al, 10000000b ;//Переполнение есть,переноса нет
mov bl, 01000000b ;//Заем в 7-й бит: нет; заем из 7-го бита: есть
sub al, bl
mov al, 10000000b ;//Переполнение есть,переноса нет
mov bl, 00000001b ;//Заем в 7-й бит: нет; заем из 7-го бита: есть
sub al, bl
mov al, 01000000b ;//Есть и переполнение,и перенос
mov bl, 11000000b ;//Заем в 7-й бит: есть; заем из 7-го бита: нет
sub al, bl
mov al, 01100000b ;//Есть и переполнение,и перенос
mov bl, 10100000b ;//Заем в 7-й бит: есть; заем из 7-го бита: нет
sub al, bl
mov al, 01111111b ;//Есть и переполнение,и перенос
mov bl, 11111111b ;//Заем в 7-й бит: есть; заем из 7-го бита: нет
sub al, bl
mov al, 01110011b ;//Есть и переполнение,и перенос
mov bl, 10110111b ;//Заем в 7-й бит: есть; заем из 7-го бита: нет
sub al, blПравила установки флагов переноса и переполнения для команды вычитания аналогичны тем, что уже излагались для команды сложения; единственное различие - вместо словосочетания "перенос в..." всюду следует подставить словосочетание "заем из...". А
Истинная таблица установки флагов переноса и переполнения для вычитания
Заем в 7-й(старший) бит Заем из 7-го(знакового) бита Флаги Есть Есть CF=1, OF=0 Есть Нет CF=1, OF=1 Нет Есть CF=0, OF=1 Нет Нет CF=0, OF=0 Итак, мы на собственном опыте убедились, как на деле сложен тот вопрос, от которого авторы популярных учебников отделались парой абзацев. Надеюсь, что данная статья поможет всем начинающим программистам быстро освоить этот непростой материал.
(c) 2003, Чугайнов Н.Г.
1 Видимо автор имел ввиду беззнаковое число. (прим. ред.)
2 Такое преобразование над числом так же называется дополнением до двух. А само представление отрицательных чисел - дополнительным кодом. (прим. ред.)
© Чугайнов Н.Г.
Перенос и переполнение - что они представляют собой на самом деле?
Дата публикации 27 июл 2003
