整数の加算・減算におけるキャリー・ボローとオーバーフローを判定する

結論からいうと

• キャリー：足し算をして桁上りしたか
• ボロー：キャリーが「無い」か
• オーバーフロー：足される数と足す数の符号が同じ、かつ結果の符号がそれと違うか

キャリーの判定

桁上りのことを、「キャリー」と呼ぶ。
すなわち、足し算を行った結果がもとの (符号なしの) 入力の範囲を超えた場合は「キャリーがある」、超えていない場合は「キャリーが無い」となる。
たとえば、8ビットの整数同士の足し算の場合、入力の範囲は 0x00～0xff であり、和がこれを超える値、すなわち 0x100 以上なら「キャリーがある」となる。
8ビットの整数2個の和が 0x200 以上になることは無いので、「和と 0x100 をビット演算した結果が非零」とも言いかえることができる。

ボローの判定

2の補数の引き算は、「引く数をビット反転して 1 を足した数を足す」ことで実現できることが知られている。
この「1 を足す」というのを、下位からのキャリーとしてとらえることができる。
そう考えたとき、もし下位からのキャリーが無かったら、1 が足されないため、計算結果は本来より 1 小さくなってしまう。
「計算結果が本来より 1 小さくなる」というのは、まさにボローがあるときに起こることである。
よって、「ボローがある」かどうかは、足し算によって引き算をしたとき「キャリーが無い」かで判定できる。

オーバーフローの判定

整数の加算におけるオーバーフローは、「入出力を符号付き整数としてみたとき、得られた計算結果がもしも精度が無限だったときの計算結果と異なる」ことである。
このような事象は、符号付き整数として見たときの入力の和が、計算結果の幅で表現できないとき起こる。

符号が違う2個の値を足したときは、オーバーフローは決して起こらない。
なぜなら、符号が違う値を足すとその和の絶対値は必ず入力の値それぞれの絶対値以下になり、入力の値を表現できているので必ず和も表現できるからである。

符号が同じ2個の値を足したときは、本来ならばその和の符号も必ず入力の値の符号になるはずである。
にもかかわらず和の符号が入力の符号と違うのであれば、それは異常、すなわちオーバーフローが起きたということである。
逆に、2個の値を足しても高々もとの値の2倍にしかならず、符号ビットを変えずにその上のビットを変えるような大幅な超過はできないため、オーバーフローが起きた場合は必ず和の符号が入力の符号と違う結果になる。

よって、オーバーフローが起きたかは、「足す2個の値の符号が同じで、和の符号がその符号と異なる」かで判定できる。

引き算においても、引き算は引く値をビット反転して 1 を加えた値を足すことで表現できるので、同様に判定できる。
すなわち、「引かれる値と引く値の符号が異なり、差の符号も引かれる値の符号と異なる」かで判定できる。

検証

x86 の ADC 命令および SBB 命令 の結果と、自前で加減算とフラグ判定を行った結果を比較した。

#include <stdio.h>

/* aの下位8bit + bの下位8bit + c を計算する */
/* [OF][CF][和8bit] を返す */
int adc_asm(int a, int b, int c) {
	int sum, flags;
	__asm__ __volatile__ (
		"test %4, %4\n\t" /* CF = 0 にする */
		"jz 1f\n\t"
		"stc\n" /* c != 0 ならば、CF = 1 にする */
		"1:\n\t"
		"adc %%dl, %%al\n\t"
		"mov %%eax, %1\n\t"
		"pushf\n\t"
		"mov (%%rsp), %0\n\t"
		"add $8, %%rsp\n\t"
	: "=r"(flags), "=r"(sum) : "a"(a), "d"(b), "r"(c));
	return (sum & 0xff) | (flags & 0x0800 ? 0x200 : 0) | (flags & 1 ? 0x100 : 0);
}

int adc(int a, int b, int c) {
	int sum = (a & 0xff) + (b & 0xff) + c;
	int overflow = (a & 0x80) == (b & 0x80) && (a & 0x80) != (sum & 0x80);
	return (sum & 0x1ff) | (overflow ? 0x200 : 0);
}

/* aの下位8bit - (bの下位8bit + c) を計算する */
/* [OF][CF][差8bit] を返す */
int sbb_asm(int a, int b, int c) {
	int diff, flags;
	__asm__ __volatile__ (
		"test %4, %4\n\t" /* CF = 0 にする */
		"jz 1f\n\t"
		"stc\n" /* c != 0 ならば、CF = 1 にする */
		"1:\n\t"
		"sbb %%dl, %%al\n\t"
		"mov %%eax, %1\n\t"
		"pushf\n\t"
		"mov (%%rsp), %0\n\t"
		"add $8, %%rsp\n\t"
	: "=r"(flags), "=r"(diff) : "a"(a), "d"(b), "r"(c));
	return (diff & 0xff) | (flags & 0x0800 ? 0x200 : 0) | (flags & 1 ? 0x100 : 0);
}

int sbb(int a, int b, int c) {
	int diff = (a & 0xff) + (~b & 0xff) + !c;
	int overflow = (a & 0x80) != (b & 0x80) && (a & 0x80) != (diff & 0x80);
	return ((diff ^ 0x100) & 0x1ff) | (overflow ? 0x200 : 0);
}

int main(void) {
	int a, b, c;
	for (a = 0; a <= 0xff; a++) {
		for (b = 0; b <= 0xff; b++) {
			for (c = 0; c <= 1; c++) {
				int r1 = adc_asm(a, b, c);
				int r2 = adc(a, b, c);
				int r3 = sbb_asm(a, b, c);
				int r4 = sbb(a, b, c);
				if (r1 != r2) {
					printf("adc error (a, b, c) = (0x%02x, 0x%02x, %d) expected = 0x%03x, actual = 0x%03x\n", a, b, c, r1, r2);
				}
				if (r3 != r4) {
					printf("sbb error (a, b, c) = (0x%02x, 0x%02x, %d) expected = 0x%03x, actual = 0x%03x\n", a, b, c, r3, r4);
				}
			}
		}
	}
	return 0;
}

このコードを実行した結果、違いは検出されなかった。