Операция прибавления единицы

Наиболее простой компьютерной арифметической операцией над целыми числами, обычно реализованной аппаратно, является прибавление единицы. В большинстве языков программирования для выполнения такой операции существует специальное обозначение, отличное от обычного сложения. Так, в Turbo-Pascal это функция succ(a) и процедура inc(а). В языке С — эта операция а++ и ++а.

Результат функции succ(a) может быть помещен в любую переменную того же типа, что и а, и, если она отлична от а (например, b:=succ(a)), то значение переменной а при этом останется прежним. В результате выполнения процедуры inc(a) значение а окажется увеличенным на единицу.

В С операции а++ и ++а значение самой переменной а увеличивают на единицу, но в первом случае результатом выражения считается значение а до его увеличения, а во втором случае — после.

Сформулируем алгоритм реализации аппаратного прибавления единицы.

Любое целое число, записанное в k разрядах, будем обозначать как <начало><последний разряд>, где <начало> — это первые слева k-1 разрядов, а <последний разряд> самый правый разряд в записи числа. Число является четным, если <последний разряд> = 0, и нечетным — в противном случае. Заметим, что запись числа в дополнительном коде это правило не нарушает.

Рекурсивный алгоритм succ(a,k) прибавления единицы к левым разрядам числа а:

• если k = 0, то конец;
• если а — четное, то вносим единицу в <последний разряд>; конец;
• если а — нечетное, то вносим ноль в <последний разряд>; succ(a,k) = succ(<начало>, k-1); конец.

Очевидно, если все k разрядов исходного числа а состоят из единиц, алгоритм все равно закончит свою работу после k шагов (в остальных случаях их будет меньше) и результатом будет являться число 0.