帶符号整數的除法與餘數

Division of Signed Integers

陳碩 giantchen_AT_gmail_DOT_com

最近研究整數到字元串的轉換，讀到了 Matthew Wilson 的《Efficient Integer to String Conversions》系列文章。（http://synesis.com.au/publications.html 搜 conversions）。他的巧妙之處在于，用一個對稱的 digits 數組搞定了負數轉換的邊界條件（二進制補碼的正負整數表示範圍不對稱）。代碼大緻如下，經過改寫：

const char* convert(char buf[], int value)

{

static char digits[19] =

{ '9', '8', '7', '6', '5', '4', '3', '2', '1',

'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

static const char* zero = digits + 9; // zero 指向 '0'

// works for -2147483648 .. 2147483647

int i = value;

char* p = buf;

do {

int lsd = i % 10; // lsd 可能小于 0

i /= 10; // 是向下取整還是向零取整？

*p++ = zero[lsd]; // 下标可能為負

} while (i != 0);

if (value < 0) {

*p++ = '-';

}

*p = '/0';

std::reverse(buf, p);

return p; // p - buf 即為整數長度

}

這段簡短的代碼對 32-bit int 的全部取值都是正确的（從 -2147483648 到 2147483647）。可以視為 itoa() 的參考實作，面試的标準答案。

讀到這份代碼，我心中頓時升起一個疑慮：《C Traps and Pitfalls》第7.7節講到，C 語言中的整數除法(/)和取模(%)運算在操作數為負的時候，結果是 implementation-defined。（網上能下載下傳到的一份簡略版也有相同的内容，http://www.literateprogramming.com/ctraps.pdf 第7.5節。）

也就是說，如果 m、d 都是整數，

int q = m / d;

int r = m % d;

那麼C語言隻保證 m == q*d + r。如果 m、d 當中有負數，那麼 q 和 r 的正負号是由實作決定的。比如 (-13)/4 == (-3)或 (-13)/4 == (-4) 都是合法的。如果采用後一種實作，那麼這段轉換代碼就錯了（因為将有 (-1) % 10 == 9）。隻有商向 0 取整，代碼才能正常工作。

為了弄清這個問題，我研究了一番。

語言标準怎麼說

• C89

我手頭沒有 ANSI C89 的文稿，隻好求助于 K&R88，此書第 41 頁第 2.5 節講到 The direction of truncation for / and the sign of the result for % are machine-dependent for negative operands, ...。确實是實作相關的。為此，C89 專門提供了 div() 函數，這個函數算出的商是向 0 取整的，便于編寫可移植的程式。我得再去查 C++ 标準。

• C++98

第 5.6.4 節寫到 If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined. C++也沒有規定餘數的正負号（C++03 的叙述一模一樣）。

不過這裡有一個注腳，提到 According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero. 即 C 語言的修訂标準會采用和 Fortran 一樣的取整算法。我又去查了 C99。

• C99

第 6.5.5.6 節說 When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. (腳注：This is often called "truncation toward zero".) C99 明确規定了商是向0取整，也就意味着餘數的符号與被除數相同，前面的轉換算法能正常工作。C99 Rationale (http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf) 提到了這個規定的原因，In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. 既然 Fortran 在數值計算領域都做了如此規定，說明開銷（如果有的話）是可以接受的。

• C++0x （x已經确定無疑是個十六進制數了）

最近的 n2800 草案第 5.6.4 節采用了與 C99 類似的表述：For integeral operands the / operator yields the algebraic quotient with any fractional part discarded; (This is often called truncation towards zero.) 可見 C++ 還是盡力保持與 C 的相容性。

小結：C89 和 C++98 都留給實作去決定，而 C99 和 C++0x 都規定商向0取整，這算是語言的進步吧。

C/C++編譯器的表現

我主要關心 G++ 和 VC++ 這兩個編譯器。需要說明的是，用代碼案例來探查編譯器的行為是靠不住的，盡管前面的代碼在兩個編譯器下都能正常工作。除非在文檔裡有明确表述，否則編譯器可能會随時更改實作--畢竟我們關心的就是 implementation-defined 行為。

• G++ 4.4

http://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html

GCC always follows the C99 requirement that the result of division is truncated towards zero.

G++ 一直遵循 C99 規範，商向0取整，算法能正常工作。

• Visual C++ 2008

http://msdn.microsoft.com/en-us/library/eayc4fzk.aspx

The sign of the remainder is the same as the sign of the dividend.

這個說法與商向0取整是等價的，算法也能正常工作。

其他語言的規定

既然 C89/C++98/C99/C++0x 已經很有多樣性了，索性弄清楚其他語言是怎麼定義整數除法的。這裡隻列出我（陳碩）接觸過的幾種常用語言。

• Java

http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.17.2

Java 語言規範明确說 Integer division rounds toward 0. 另外對于 int 整數除法溢出，特别規定不抛異常，且 -2147483648 / -1 = -2147483648 （以及相應的long版本）。

• C#

http://msdn.microsoft.com/en-us/vcsharp/aa336809.aspx

C# 3.0 語言規定 The division rounds the result towards zero. 對于溢出的情況，規定在 checked 上下文中抛 ArithmeticException 異常；在 unchecked 上下文裡沒有明确規定，可抛可不抛。(據了解，C# 1.0/2.0 可能有所不同。）

• Python

Python 在語言參考手冊的顯著位置标明，商是向負無窮取整。Plain or long integer division yields an integer of the same type; the result is that of mathematical division with the `floor' function applied to the result.

http://docs.python.org/reference/expressions.html#binary-arithmetic-operations

• Ruby

Ruby 的語言手冊沒有明說，不過庫的手冊說到也是向負無窮取整。The quotient is rounded toward -infinity.

http://www.ruby-doc.org/docs/ProgrammingRuby/html/ref_c_numeric.html#Numeric.divmod

• Perl

Perl 語言預設按浮點數來計算除法，是以沒有這個問題。Perl 的整數取模運算規則與Python/Ruby一緻。

http://perldoc.perl.org/perlop.html#Multiplicative-Operators

不過要注意，use integer; 有可能會改變運算結果，例如。

print -10 % 3; // => 2

use integers;

print -10 % 3; // => -1

• Lua

Lua 預設沒有整數類型，除法一律按浮點數來算，是以不涉及商的取整問題。

可以看出，在整數除法的取整問題上，語言分為兩個陣營，腳本語言彼此是相似的，C99/C++0x/Java/C# 則屬于另一個陣營。既然 Python 和 Ruby 都是用 C 實作的，但是運算規則又自成一體，那麼必定能從代碼中找到證據。

Python 的代碼很好讀，我很快就找到了 2.6.4 版實作整數除法和取模運算的函數 i_divmod()

http://svn.python.org/view/python/tags/r264/Objects/intobject.c?revision=75707&view=markup

注意到這段代碼甚至考慮了 -2147483648 / -1 在32-bit下會溢出這個特殊情況，讓我大吃一驚。宏定義UNARY_NEG_WOULD_OVERFLOW 和函數 int_mul() 前面的注釋也值得一讀。

Ruby 的代碼要混亂一些，花點時間還是能找到，這是 1.8.7-p248 的實作，注意 fixdivmod() 函數。

http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/tags/v1_8_7_248/numeric.c?view=markup

注意到 Ruby 的 Fixnum 整數的表示範圍比機器字長小1bit，直接避免了溢出的可能。

硬體實作

既然 C/C++ 以效率著稱，那麼應該是貼近硬體實作的。我考察了幾種熟悉的硬體平台，它們基本都支援 C99/C++0x 的語意，也就是說新規定沒有額外開銷。列舉如下。（其實我們隻關系帶符号除法，不過為了完整性，這裡一并列出 unsigned/signed 整數除法指令。）

• Intel x86/x64

Intel x86 系列的 DIV/IDIV 指令明确提到是向0取整，與 C99/C++0x/Java/C# 一緻。

• MIPS

很奇怪，我在 MIPS 的參考手冊裡沒有查到 DIV/DIVU 指令的取整方向，不過根據 Patternson&Hennessy 的講解，似乎向0取整硬體上實作起來比較容易。或許我沒找對地方？

• ARM/Cortex-M3

ARM 沒有硬體除法指令，是以不存在這個問題。Cortex-M3 有硬體除法，SDIV/UDIV 指令都是向0取整。Cortex-M3 的除法指令不能同時算出餘數，這很特殊。

• MMIX

MMIX 是 Knuth 設計的 64-bit CPU，替換原來的 MIX 機器。DIV 和 DIVU 都是向負無窮取整（依據 TAOCP 第1.2.4節的定義，在第一卷 40 頁頭幾行），這是我知道的惟一支援 Python/Ruby 語義的"硬體"平台。

總結：想不到小小的整數除法都有這麼大名堂。一段隻涉及整數運算的代碼，即便能在各種文法相似的語言裡運作，結果也可能完全不同。