C++求余用的「%」有與它效率相同的其它演算法嗎？

12-30

如果右側為常數，可轉換成乘法、右移和減法[1]。現代的編譯器都會做這個優化，例如

// mod.c unsigned a = 123; int main() { return a % 13; }

使用 clang -c -S mod.c 輸出彙編

movl $13, %eax movl $0, -4(%rbp) movl _a(%rip), %ecx movl %eax, -8(%rbp) ## 4-byte Spill movl %ecx, %eax xorl %edx, %edx movl -8(%rbp), %ecx ## 4-byte Reload divl %ecx movl %edx, %eax

這是直接翻譯，用 divl 做除數，這指令同時能獲得餘數（edx ），但 divl 是很慢的。

然而，使用優化的話 clang -c -S -O3 mod.c

movl _a(%rip), %eax imulq $1321528399, %rax, %rcx ## imm = 0x4EC4EC4F shrq $34, %rcx imull $13, %ecx, %ecx subl %ecx, %eax

解釋一下，因為 1321528399 / 2^34 ≈ 1 / 13

a % 13 = a - (a / 13) * 13 = a - uint32_t((uint64_t(a) * 1321528399ULL) &>&> 34) * 13

我在 RapidJSON 代碼剖析（四）：優化 Grisu - Milo的編程 - 知乎專欄也提過怎樣利用編譯器的這個功能來優化一段代碼。

有其他答案說到用 and 來做 2^N 的餘數，如果 2^N 為常數，編譯器當然是會自動做優化的，例如 a / 16：

movl _a(%rip), %eax andl $15, %eax

但如果不是常數，而又是 2^N，就可以自行 a ((1&<&[1] Warren, Henry S. Hacker"s delight. Chapter 10. Pearson Education, 2013.

一樓說的有缺陷,求余雖然只有一條指令但這條指令要耗費100多個周期.

任意的"%"有簡便方法,較為複雜,好久不用忘了..不好意思,

不過先來看看一個數對2的N次方整型求余的簡便方法吧:

正如樓上所說,是個bit trick:

x%A == x(A-1); (注意,A必須是2的N次方).

同理的,檢查x是否為2的N次方:

x(x-1)==0

實際上如果你用MSVC或者GCC的話,如果A是個2的N次方,你會發現編譯器很可能

就是按這個方法做的.

像這種細微的優化,最好還是從演算法本身來優化,比如實現一個ring buffer,

與其找一個快速的mod方法,還不如保證ring buffer的尺寸永遠是2的N次方,然後

使用上述bit trick.

據我所知一般對大數取模才會用其他演算法，形如(a^b)%k的運算(a、b都很大時)可以使用蒙哥馬利快速冪模演算法(Montgomery reduction algorithm)

Montgomery reduction

數字有規律，就有可能用bit trick。即使有指令直接支持%，畢竟每條指令花的時間是不一樣的，%是很耗時的吧。

大部分平台上（ARM比較奇葩），整數求余操作可以用一條CPU指令實現，有什麼演算法能比這效率高？...

magic number，補充一個更詳細的連接：Labor of Division (Episode I)

在最新的silvermont上，做一條DIV 64要30-120個cycle，所以能用and代替最好