高效的模 255 计算
Efficient modulo-255 computation
我正在尝试找到计算 32 位无符号整数的 modulo 255 的最有效方法。我的主要关注点是找到一种在 x86 和 ARM 平台上运行良好的算法，并着眼于超越该平台的适用性。首先，我试图避免内存操作（这可能很昂贵），所以我正在寻找有点复杂的方法，同时避免使用表格。我也在努力避免潜在的昂贵操作，例如分支和乘法，并尽量减少使用的操作和寄存器的数量。
下面的 ISO-C99 代码捕获了我迄今为止尝试过的八个变体。它包括一个用于详尽测试的框架。我将一些 粗略的 执行时间测量值附加到这个上，它似乎工作得很好，可以获得第一印象。在我尝试过的几个平台上（所有平台都具有快速整数乘法），变体 WARREN_MUL_SHR_2、WARREN_MUL_SHR_1 和 DIGIT_SUM_CARRY_OUT_1 似乎是性能最高的。我的实验表明，我在 Compiler Explorer 尝试过的 x86、ARM、PowerPC 和 MIPS 编译器都很好地利用了特定于平台的功能，例如三输入 LEA、字节扩展指令、乘法累加, 和指令谓词。
变体NAIVE_USING_DIV使用整数除法，反乘除数，然后减法。这是基准案例。现代编译器知道如何有效地实现无符号整数除以 255（通过乘法），并将在适当的情况下使用离散替换反乘。要计算 modulo base-1，可以对 base 位求和，然后折叠结果。例如3334 mod 9：求和3+3+3+4 = 13，折叠1+3 = 4。如果折叠后的结果是base-1，我们需要生成0来代替。 DIGIT_SUM_THEN_FOLD 使用此方法。
一个。 Cockburn，“使用 8/16 位算法有效实现 OSI 传输协议校验和算法”，ACM SIGCOMM 计算机通信评论，卷。 17，第 3 期，July/Aug。 1987 年，第 13-20 页
展示了在校验和计算的上下文中有效地添加数字 modulo base-1 的不同方法 modulo 255。计算数字的字节总和，以及每次添加后，还要添加添加项中的任何结转物。所以这将是一个 ADD a, b, ADC a, 0 序列。使用 base 256 数字为此写出加法链，很明显计算基本上是与 0x0101 ... 0101 的乘法。结果将位于最重要的数字位置，除了需要从该位置的加法中单独捕获进位。此方法仅在 base 位包含 2k 位时有效。这里我们有 k=3。我尝试了三种不同的方法将 base-1 的结果重新映射为 0，从而产生变体 DIGIT_SUM_CARRY_OUT_1、DIGIT_SUM_CARRY_OUT_2、DIGIT_SUM_CARRY_OUT_3.
Joe Keane 于 1995 年 07 月 9 日在新闻组 comp.lang.c 中演示了一种有效计算 modulo-63 的有趣方法。虽然线程参与者 Peter L. Montgomery 证明了该算法是正确的，但不幸的是，Keane 先生没有回应解释其推导的请求。 H. Warren 的 Hacker's Delight 第 2 版 中也复制了该算法。我能够以纯机械方式将它扩展到modulo-127 和modulo-255。这是（适当命名的）KEANE_MAGIC 变体。 更新： 自从我最初发布这个问题后，我发现 Keane 的方法基本上是以下内容的巧妙定点实现：return (uint32_t)(fmod (x * 256.0 / 255.0 + 0.5, 256.0) * (255.0 / 256.0));。这使它成为下一个变体的近亲。
Henry S. Warren，Hacker's Delight 第 2 版。，第 3 页。 272 显示了一个“乘右移”算法，大概是作者自己设计的，它基于数学 属性 即 n mod 2k-1 = floor (2k / 2k-1 * n) mod 2k.定点计算用于乘以因数 2k / 2k-1。我构造了两个变体，它们在处理 base-1 到 0 的初步结果映射的方式上有所不同。这些是变体 WARREN_MUL_SHR_1 和 WARREN_MUL_SHR_2.
是否存在比我目前确定的三个顶级竞争者更高效的 modulo-255 计算算法，特别是对于整数乘法较慢的平台？在这种情况下，对 Keane 的无乘法算法进行有效的 mod 化以求和四个 base 256 数字似乎特别令人感兴趣。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define NAIVE_USING_DIV (1)
#define DIGIT_SUM_THEN_FOLD (2)
#define DIGIT_SUM_CARRY_OUT_1 (3)
#define DIGIT_SUM_CARRY_OUT_2 (4)
#define DIGIT_SUM_CARRY_OUT_3 (5)
#define KEANE_MAGIC (6) // Joe Keane, comp.lang.c, 1995/07/09
#define WARREN_MUL_SHR_1 (7) // Hacker's Delight, 2nd ed., p. 272
#define WARREN_MUL_SHR_2 (8) // Hacker's Delight, 2nd ed., p. 272
#define VARIANT (WARREN_MUL_SHR_2)
uint32_t mod255 (uint32_t x)
{
#if VARIANT == NAIVE_USING_DIV
return x - 255 * (x / 255);
#elif VARIANT == DIGIT_SUM_THEN_FOLD
x = (x & 0xffff) + (x >> 16);
x = (x & 0xff) + (x >> 8);
x = (x & 0xff) + (x >> 8) + 1;
x = (x & 0xff) + (x >> 8) - 1;
return x;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_1
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
if (t == 255) t = 0;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_2
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x) + 1;
t = (t & 0xff) + (t >> 8) - 1;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_3
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
t = t & ((t - 255) >> 8);
return t;
#elif VARIANT == KEANE_MAGIC
x = (((x >> 16) + x) >> 14) + (x << 2);
x = ((x >> 8) + x + 2) & 0x3ff;
x = (x - (x >> 8)) >> 2;
return x;
#elif VARIANT == WARREN_MUL_SHR_1
x = (0x01010101 * x + (x >> 8)) >> 24;
x = x & ((x - 255) >> 8);
return x;
#elif VARIANT == WARREN_MUL_SHR_2
x = (0x01010101 * x + (x >> 8)) >> 24;
if (x == 255) x = 0;
return x;
#else
#error unknown VARIANT
#endif
}
uint32_t ref_mod255 (uint32_t x)
{
volatile uint32_t t = x;
t = t % 255;
return t;
}
// timing with microsecond resolution
#if defined(_WIN32)
#if !defined(WIN32_LEAN_AND_MEAN)
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
double second (void)
{
LARGE_INTEGER t;
static double oofreq;
static int checkedForHighResTimer;
static BOOL hasHighResTimer;
if (!checkedForHighResTimer) {
hasHighResTimer = QueryPerformanceFrequency (&t);
oofreq = 1.0 / (double)t.QuadPart;
checkedForHighResTimer = 1;
}
if (hasHighResTimer) {
QueryPerformanceCounter (&t);
return (double)t.QuadPart * oofreq;
} else {
return (double)GetTickCount() * 1.0e-3;
}
}
#elif defined(__linux__) || defined(__APPLE__)
#include <stddef.h>
#include <sys/time.h>
double second (void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;
}
#else
#error unsupported platform
#endif
int main (void)
{
double start, stop;
uint32_t res, ref, x = 0;
printf ("Testing VARIANT = %d\n", VARIANT);
start = second();
do {
res = mod255 (x);
ref = ref_mod255 (x);
if (res != ref) {
printf ("error @ %08x: res=%08x ref=%08x\n", x, res, ref);
return EXIT_FAILURE;
}
x++;
} while (x);
stop = second();
printf ("test passed\n");
printf ("elapsed = %.6f seconds\n", stop - start);
return EXIT_SUCCESS;
}
以下是我对最快答案的理解。我还不知道基恩是否可以改进或容易推广。
给定一个整数 x ≥ 0，令 q = ⌊x/255⌋（在 C 中，q = x / 255;）和 r = x − 255 q（在 C 中，r = x % 255;）所以q ≥ 0 和 0 ≤ r < 255 是整数并且 x = 255 q + r.
Adrian Mole 的方法
此方法计算 (x + ⌊x/255⌋) mod 28（在 C 中，(x + x / 255) & 0xff），它等于 ( 255 q + r + q) mod 28 = (28 q + r) mod 28 = r.
Henry S. Warren 的方法
注意 x + ⌊x/255⌋ = ⌊x + x/255⌋ = ⌊(28/255) x⌋，其中第一个步骤遵循 x 是一个整数。此方法使用乘数 (20 + 2−8 + 2−16 + 2−24 + 2−32) 而不是 28/255，这是无限级数的和20 + 2−8 + 2−16 + 2−24 + 2−32 + ….由于近似略欠，该方法必须检测残数 28 − 1 = 255.
乔基恩的方法
这个方法的直觉是计算 y = (28/255) x mod 28,等于 (28/255) (255 q + r) mod 28 = (28 q+(28/255)r)mod28=(2 8/255) r，和 return y − y/28，等于 r.
因为这些公式不使用⌊(28/255) r⌋ = r，基恩可以从 28 到 210 用于两个保护位。理想情况下，它们始终为零，但由于定点截断和 210/255 的近似值，它们不是。 Keane 加 2 以从截断切换到舍入，这也避免了 Warren 中的特殊情况。
这种方法有点使用乘数 22 (20 + 2−8 + 2−16 + 2−24 + 2−32 + 2 −40) = 22 (20 + 2−16 + 2 −32) (20 + 2−8)。 C 语句 x = (((x >> 16) + x) >> 14) + (x << 2); 计算 x′ = ⌊22 (20 + 2−16 + 2−32) x⌋ mod 232.那么 ((x >> 8) + x) & 0x3ff 就是 x′′ = ⌊(20 + 2−8) x′⌋ mod 210.
我现在没有时间正式做错误分析。非正式地，第一次计算的错误区间宽度 < 1；第二，宽度 < 2 + 2−8；第三，width < ((2 − 2−8) + 1)/22 < 1，这允许正确舍入。
关于改进，近似的2−40项似乎没有必要（？），但我们还是有它，除非我们能去掉2−32项。丢弃 2−32 将近似质量推到规范之外。
我猜您可能不是在寻找需要快速 64 位乘法的解决方案，但郑重声明：
return (x * 0x101010101010102ULL) >> 56;
对于任意无符号整数，x 和 n，求模表达式 x % n 涉及（至少在概念上） , 三个运算：除法、乘法和减法：
quotient = x / n;
product = quotient * n;
modulus = x - product;
但是，当n是2的幂时（n = 2p） , 可以更快地 much 确定模数，只需屏蔽除较低 p 位以外的所有位。
在大多数 CPU 中，加法、减法和位掩码是非常 'cheap'（快速）的运算，乘法更 'expensive' 和除法 非常 昂贵——但请注意，大多数优化编译器会将编译时常量的除法转换为乘法（通过不同的常量）和位移（见下文） .
因此，如果我们可以将我们的模 255 转换为模 256，而无需太多开销，我们可能会加快这个过程。我们可以通过注意到 x % n 等价于 (x + x / n) % (n + 1)† 来做到这一点。因此，我们现在的概念操作是：除法、加法和掩码。
在屏蔽低 8 位的 特定 情况下，x86/x64-based CPUs（和其他人？）将可能能够执行进一步的操作优化，因为它们可以访问（大多数）寄存器的 8 位版本。
这是 clang-cl 编译器为一个简单的模 255 函数生成的内容（参数在 ecx 中传递并在 eax 中返回）：
unsigned Naive255(unsigned x)
{
return x % 255;
}
mov edx, ecx
mov eax, 2155905153 ;
imul rax, rdx ; Replacing the IDIV with IMUL and SHR
shr rax, 39 ;
mov edx, eax
shl edx, 8
sub eax, edx
add eax, ecx
这是使用上述 'trick' 生成的（明显更快的）代码：
unsigned Trick255(unsigned x)
{
return (x + x / 255) & 0xFF;
}
mov eax, ecx
mov edx, 2155905153
imul rdx, rax
shr rdx, 39
add edx, ecx
movzx eax, dl ; Faster than an explicit AND mask?
在 Windows-10（64 位）平台（英特尔® 酷睿™ i7-8550U CPU）上测试此代码表明它显着（但不是很大）优于问题中提出的其他算法。
† 说明 how/why 这个等价是有效的。
这种方法（自上次编辑以来略有改进）融合了沃伦和基恩。在我的笔记本电脑上，它比 Keane 快，但不如 64 位乘法和移位快。它避免了乘法，但受益于单个循环指令。不像原来的版本，在RISC-V上应该没问题。
和Warren一样，这个方法在8.24不动点上近似⌊(256/255) x mod 256⌋。 Mod 256，每个字节b贡献一个项(256/255) b，大约是b.bbb base 256。这个方法的原始版本只是将所有四个字节旋转求和。 （我稍后会讲到修订版。）这个总和总是低估实际值，但排在最后不到 4 个单位。通过在截断之前添加 4/2−24，我们保证了 Keane 中的正确答案。
修订版通过放宽近似质量来节省工作。我们写 (256/255) x = (257/256) (65536/65535) x，在 16.16 定点计算 (65536/65535) x（即，将 x 添加到它的 16 位旋转），然后乘以 257 /256 和 mod 由 256 变成 8.24 定点。第一次乘法在16.16的最后一位误差小于2个单位，第二次是精确的（！）。总和低估了小于（2/216）（257/256），所以514/224的常数项就足以修正截断。如果不同的立即数操作数更有效，也可以使用更大的值。
uint32_t mod255(uint32_t x) {
x += (x << 16) | (x >> 16);
return ((x << 8) + x + 514) >> 24;
}
如果我们要有一个针对单指令 addc 优化的内置函数、内部函数或方法，可以按以下方式使用 32 位算术：
uint32_t carry = 0;
// sum up top and bottom 16 bits while generating carry out
x = __builtin_addc(x, x<<16, carry, &carry);
x &= 0xffff0000;
// store the previous carry to bit 0 while adding
// bits 16:23 over bits 24:31, and producing one more carry
x = __builtin_addc(x, x << 8, carry, &carry);
x = __builtin_addc(x, x >> 24, carry, &carry);
x &= 0x0000ffff; // actually 0x1ff is enough
// final correction for 0<=x<=257, i.e. min(x,x-255)
x = x < x-255 ? x : x - 255;
在Arm64中至少常规的add指令可以采用add r0, r1, r2 LSL 16的形式；使用立即数或清除连续位的掩码是单个指令 bfi r0, wzr, #start_bit, #length.
对于并行计算，不能使用有效扩大乘法。相反，在计算进位时可以分而治之——从 16 uint32_t 个元素开始解释为 16+16 uint16_t 个元素，然后转向 uint8_t 算术，可以计算一个结果略少于一条指令。
a0 = vld2q_u16(ptr); // split input to top16+bot16 bits
a1 = vld2q_u16(ptr + 8); // load more inputs
auto b0 = vaddq_u16(a0.val[0], a0.val[1]);
auto b1 = vaddq_u16(a1.val[0], a1.val[1]);
auto c0 = vcltq_u16(b0, a0.val[1]); // 8 carries
auto c1 = vcltq_u16(b1, a1.val[1]); // 8 more carries
b0 = vsubq_u16(b0, c0);
b1 = vsubq_u16(b1, c1);
auto d = vuzpq_u8(b0, b1);
auto result = vaddq_u8(d.val[0], d.val[1]);
auto carry = vcltq_u8(result, d.val[1]);
result = vsubq_u8(result, carry);
auto is_255 = vceqq_u8(result, vdupq_n_u8(255));
result = vbicq_u8(result, is_255);
我正在尝试找到计算 32 位无符号整数的 modulo 255 的最有效方法。我的主要关注点是找到一种在 x86 和 ARM 平台上运行良好的算法，并着眼于超越该平台的适用性。首先，我试图避免内存操作（这可能很昂贵），所以我正在寻找有点复杂的方法，同时避免使用表格。我也在努力避免潜在的昂贵操作，例如分支和乘法，并尽量减少使用的操作和寄存器的数量。
下面的 ISO-C99 代码捕获了我迄今为止尝试过的八个变体。它包括一个用于详尽测试的框架。我将一些 粗略的 执行时间测量值附加到这个上，它似乎工作得很好，可以获得第一印象。在我尝试过的几个平台上（所有平台都具有快速整数乘法），变体 WARREN_MUL_SHR_2、WARREN_MUL_SHR_1 和 DIGIT_SUM_CARRY_OUT_1 似乎是性能最高的。我的实验表明，我在 Compiler Explorer 尝试过的 x86、ARM、PowerPC 和 MIPS 编译器都很好地利用了特定于平台的功能，例如三输入 LEA、字节扩展指令、乘法累加, 和指令谓词。
变体NAIVE_USING_DIV使用整数除法，反乘除数，然后减法。这是基准案例。现代编译器知道如何有效地实现无符号整数除以 255（通过乘法），并将在适当的情况下使用离散替换反乘。要计算 modulo base-1，可以对 base 位求和，然后折叠结果。例如3334 mod 9：求和3+3+3+4 = 13，折叠1+3 = 4。如果折叠后的结果是base-1，我们需要生成0来代替。 DIGIT_SUM_THEN_FOLD 使用此方法。
一个。 Cockburn，“使用 8/16 位算法有效实现 OSI 传输协议校验和算法”，ACM SIGCOMM 计算机通信评论，卷。 17，第 3 期，July/Aug。 1987 年，第 13-20 页
展示了在校验和计算的上下文中有效地添加数字 modulo base-1 的不同方法 modulo 255。计算数字的字节总和，以及每次添加后，还要添加添加项中的任何结转物。所以这将是一个 ADD a, b, ADC a, 0 序列。使用 base 256 数字为此写出加法链，很明显计算基本上是与 0x0101 ... 0101 的乘法。结果将位于最重要的数字位置，除了需要从该位置的加法中单独捕获进位。此方法仅在 base 位包含 2k 位时有效。这里我们有 k=3。我尝试了三种不同的方法将 base-1 的结果重新映射为 0，从而产生变体 DIGIT_SUM_CARRY_OUT_1、DIGIT_SUM_CARRY_OUT_2、DIGIT_SUM_CARRY_OUT_3.
Joe Keane 于 1995 年 07 月 9 日在新闻组 comp.lang.c 中演示了一种有效计算 modulo-63 的有趣方法。虽然线程参与者 Peter L. Montgomery 证明了该算法是正确的，但不幸的是，Keane 先生没有回应解释其推导的请求。 H. Warren 的 Hacker's Delight 第 2 版 中也复制了该算法。我能够以纯机械方式将它扩展到modulo-127 和modulo-255。这是（适当命名的）KEANE_MAGIC 变体。 更新： 自从我最初发布这个问题后，我发现 Keane 的方法基本上是以下内容的巧妙定点实现：return (uint32_t)(fmod (x * 256.0 / 255.0 + 0.5, 256.0) * (255.0 / 256.0));。这使它成为下一个变体的近亲。
Henry S. Warren，Hacker's Delight 第 2 版。，第 3 页。 272 显示了一个“乘右移”算法，大概是作者自己设计的，它基于数学 属性 即 n mod 2k-1 = floor (2k / 2k-1 * n) mod 2k.定点计算用于乘以因数 2k / 2k-1。我构造了两个变体，它们在处理 base-1 到 0 的初步结果映射的方式上有所不同。这些是变体 WARREN_MUL_SHR_1 和 WARREN_MUL_SHR_2.
是否存在比我目前确定的三个顶级竞争者更高效的 modulo-255 计算算法，特别是对于整数乘法较慢的平台？在这种情况下，对 Keane 的无乘法算法进行有效的 mod 化以求和四个 base 256 数字似乎特别令人感兴趣。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define NAIVE_USING_DIV (1)
#define DIGIT_SUM_THEN_FOLD (2)
#define DIGIT_SUM_CARRY_OUT_1 (3)
#define DIGIT_SUM_CARRY_OUT_2 (4)
#define DIGIT_SUM_CARRY_OUT_3 (5)
#define KEANE_MAGIC (6) // Joe Keane, comp.lang.c, 1995/07/09
#define WARREN_MUL_SHR_1 (7) // Hacker's Delight, 2nd ed., p. 272
#define WARREN_MUL_SHR_2 (8) // Hacker's Delight, 2nd ed., p. 272
#define VARIANT (WARREN_MUL_SHR_2)
uint32_t mod255 (uint32_t x)
{
#if VARIANT == NAIVE_USING_DIV
return x - 255 * (x / 255);
#elif VARIANT == DIGIT_SUM_THEN_FOLD
x = (x & 0xffff) + (x >> 16);
x = (x & 0xff) + (x >> 8);
x = (x & 0xff) + (x >> 8) + 1;
x = (x & 0xff) + (x >> 8) - 1;
return x;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_1
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
if (t == 255) t = 0;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_2
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x) + 1;
t = (t & 0xff) + (t >> 8) - 1;
return t;
#elif VARIANT == DIGIT_SUM_CARRY_OUT_3
uint32_t t;
t = 0x01010101 * x;
t = (t >> 24) + (t < x);
t = t & ((t - 255) >> 8);
return t;
#elif VARIANT == KEANE_MAGIC
x = (((x >> 16) + x) >> 14) + (x << 2);
x = ((x >> 8) + x + 2) & 0x3ff;
x = (x - (x >> 8)) >> 2;
return x;
#elif VARIANT == WARREN_MUL_SHR_1
x = (0x01010101 * x + (x >> 8)) >> 24;
x = x & ((x - 255) >> 8);
return x;
#elif VARIANT == WARREN_MUL_SHR_2
x = (0x01010101 * x + (x >> 8)) >> 24;
if (x == 255) x = 0;
return x;
#else
#error unknown VARIANT
#endif
}
uint32_t ref_mod255 (uint32_t x)
{
volatile uint32_t t = x;
t = t % 255;
return t;
}
// timing with microsecond resolution
#if defined(_WIN32)
#if !defined(WIN32_LEAN_AND_MEAN)
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
double second (void)
{
LARGE_INTEGER t;
static double oofreq;
static int checkedForHighResTimer;
static BOOL hasHighResTimer;
if (!checkedForHighResTimer) {
hasHighResTimer = QueryPerformanceFrequency (&t);
oofreq = 1.0 / (double)t.QuadPart;
checkedForHighResTimer = 1;
}
if (hasHighResTimer) {
QueryPerformanceCounter (&t);
return (double)t.QuadPart * oofreq;
} else {
return (double)GetTickCount() * 1.0e-3;
}
}
#elif defined(__linux__) || defined(__APPLE__)
#include <stddef.h>
#include <sys/time.h>
double second (void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;
}
#else
#error unsupported platform
#endif
int main (void)
{
double start, stop;
uint32_t res, ref, x = 0;
printf ("Testing VARIANT = %d\n", VARIANT);
start = second();
do {
res = mod255 (x);
ref = ref_mod255 (x);
if (res != ref) {
printf ("error @ %08x: res=%08x ref=%08x\n", x, res, ref);
return EXIT_FAILURE;
}
x++;
} while (x);
stop = second();
printf ("test passed\n");
printf ("elapsed = %.6f seconds\n", stop - start);
return EXIT_SUCCESS;
}
以下是我对最快答案的理解。我还不知道基恩是否可以改进或容易推广。
给定一个整数 x ≥ 0，令 q = ⌊x/255⌋（在 C 中，q = x / 255;）和 r = x − 255 q（在 C 中，r = x % 255;）所以q ≥ 0 和 0 ≤ r < 255 是整数并且 x = 255 q + r.
Adrian Mole 的方法
此方法计算 (x + ⌊x/255⌋) mod 28（在 C 中，(x + x / 255) & 0xff），它等于 ( 255 q + r + q) mod 28 = (28 q + r) mod 28 = r.
Henry S. Warren 的方法
注意 x + ⌊x/255⌋ = ⌊x + x/255⌋ = ⌊(28/255) x⌋，其中第一个步骤遵循 x 是一个整数。此方法使用乘数 (20 + 2−8 + 2−16 + 2−24 + 2−32) 而不是 28/255，这是无限级数的和20 + 2−8 + 2−16 + 2−24 + 2−32 + ….由于近似略欠，该方法必须检测残数 28 − 1 = 255.
乔基恩的方法
这个方法的直觉是计算 y = (28/255) x mod 28,等于 (28/255) (255 q + r) mod 28 = (28 q+(28/255)r)mod28=(2 8/255) r，和 return y − y/28，等于 r.
因为这些公式不使用⌊(28/255) r⌋ = r，基恩可以从 28 到 210 用于两个保护位。理想情况下，它们始终为零，但由于定点截断和 210/255 的近似值，它们不是。 Keane 加 2 以从截断切换到舍入，这也避免了 Warren 中的特殊情况。
这种方法有点使用乘数 22 (20 + 2−8 + 2−16 + 2−24 + 2−32 + 2 −40) = 22 (20 + 2−16 + 2 −32) (20 + 2−8)。 C 语句 x = (((x >> 16) + x) >> 14) + (x << 2); 计算 x′ = ⌊22 (20 + 2−16 + 2−32) x⌋ mod 232.那么 ((x >> 8) + x) & 0x3ff 就是 x′′ = ⌊(20 + 2−8) x′⌋ mod 210.
我现在没有时间正式做错误分析。非正式地，第一次计算的错误区间宽度 < 1；第二，宽度 < 2 + 2−8；第三，width < ((2 − 2−8) + 1)/22 < 1，这允许正确舍入。
关于改进，近似的2−40项似乎没有必要（？），但我们还是有它，除非我们能去掉2−32项。丢弃 2−32 将近似质量推到规范之外。
我猜您可能不是在寻找需要快速 64 位乘法的解决方案，但郑重声明：
return (x * 0x101010101010102ULL) >> 56;
对于任意无符号整数，x 和 n，求模表达式 x % n 涉及（至少在概念上） , 三个运算：除法、乘法和减法：
quotient = x / n;
product = quotient * n;
modulus = x - product;
但是，当n是2的幂时（n = 2p） , 可以更快地 much 确定模数，只需屏蔽除较低 p 位以外的所有位。
在大多数 CPU 中，加法、减法和位掩码是非常 'cheap'（快速）的运算，乘法更 'expensive' 和除法 非常 昂贵——但请注意，大多数优化编译器会将编译时常量的除法转换为乘法（通过不同的常量）和位移（见下文） .
因此，如果我们可以将我们的模 255 转换为模 256，而无需太多开销，我们可能会加快这个过程。我们可以通过注意到 x % n 等价于 (x + x / n) % (n + 1)† 来做到这一点。因此，我们现在的概念操作是：除法、加法和掩码。
在屏蔽低 8 位的 特定 情况下，x86/x64-based CPUs（和其他人？）将可能能够执行进一步的操作优化，因为它们可以访问（大多数）寄存器的 8 位版本。
这是 clang-cl 编译器为一个简单的模 255 函数生成的内容（参数在 ecx 中传递并在 eax 中返回）：
unsigned Naive255(unsigned x)
{
return x % 255;
}
mov edx, ecx
mov eax, 2155905153 ;
imul rax, rdx ; Replacing the IDIV with IMUL and SHR
shr rax, 39 ;
mov edx, eax
shl edx, 8
sub eax, edx
add eax, ecx
这是使用上述 'trick' 生成的（明显更快的）代码：
unsigned Trick255(unsigned x)
{
return (x + x / 255) & 0xFF;
}
mov eax, ecx
mov edx, 2155905153
imul rdx, rax
shr rdx, 39
add edx, ecx
movzx eax, dl ; Faster than an explicit AND mask?
在 Windows-10（64 位）平台（英特尔® 酷睿™ i7-8550U CPU）上测试此代码表明它显着（但不是很大）优于问题中提出的其他算法。
†
这种方法（自上次编辑以来略有改进）融合了沃伦和基恩。在我的笔记本电脑上，它比 Keane 快，但不如 64 位乘法和移位快。它避免了乘法，但受益于单个循环指令。不像原来的版本，在RISC-V上应该没问题。
和Warren一样，这个方法在8.24不动点上近似⌊(256/255) x mod 256⌋。 Mod 256，每个字节b贡献一个项(256/255) b，大约是b.bbb base 256。这个方法的原始版本只是将所有四个字节旋转求和。 （我稍后会讲到修订版。）这个总和总是低估实际值，但排在最后不到 4 个单位。通过在截断之前添加 4/2−24，我们保证了 Keane 中的正确答案。
修订版通过放宽近似质量来节省工作。我们写 (256/255) x = (257/256) (65536/65535) x，在 16.16 定点计算 (65536/65535) x（即，将 x 添加到它的 16 位旋转），然后乘以 257 /256 和 mod 由 256 变成 8.24 定点。第一次乘法在16.16的最后一位误差小于2个单位，第二次是精确的（！）。总和低估了小于（2/216）（257/256），所以514/224的常数项就足以修正截断。如果不同的立即数操作数更有效，也可以使用更大的值。
uint32_t mod255(uint32_t x) {
x += (x << 16) | (x >> 16);
return ((x << 8) + x + 514) >> 24;
}
如果我们要有一个针对单指令 addc 优化的内置函数、内部函数或方法，可以按以下方式使用 32 位算术：
uint32_t carry = 0;
// sum up top and bottom 16 bits while generating carry out
x = __builtin_addc(x, x<<16, carry, &carry);
x &= 0xffff0000;
// store the previous carry to bit 0 while adding
// bits 16:23 over bits 24:31, and producing one more carry
x = __builtin_addc(x, x << 8, carry, &carry);
x = __builtin_addc(x, x >> 24, carry, &carry);
x &= 0x0000ffff; // actually 0x1ff is enough
// final correction for 0<=x<=257, i.e. min(x,x-255)
x = x < x-255 ? x : x - 255;
在Arm64中至少常规的add指令可以采用add r0, r1, r2 LSL 16的形式；使用立即数或清除连续位的掩码是单个指令 bfi r0, wzr, #start_bit, #length.
对于并行计算，不能使用有效扩大乘法。相反，在计算进位时可以分而治之——从 16 uint32_t 个元素开始解释为 16+16 uint16_t 个元素，然后转向 uint8_t 算术，可以计算一个结果略少于一条指令。
a0 = vld2q_u16(ptr); // split input to top16+bot16 bits
a1 = vld2q_u16(ptr + 8); // load more inputs
auto b0 = vaddq_u16(a0.val[0], a0.val[1]);
auto b1 = vaddq_u16(a1.val[0], a1.val[1]);
auto c0 = vcltq_u16(b0, a0.val[1]); // 8 carries
auto c1 = vcltq_u16(b1, a1.val[1]); // 8 more carries
b0 = vsubq_u16(b0, c0);
b1 = vsubq_u16(b1, c1);
auto d = vuzpq_u8(b0, b1);
auto result = vaddq_u8(d.val[0], d.val[1]);
auto carry = vcltq_u8(result, d.val[1]);
result = vsubq_u8(result, carry);
auto is_255 = vceqq_u8(result, vdupq_n_u8(255));
result = vbicq_u8(result, is_255);