我用汇编语言和 C ++ 语言为 Euler Q14 项目编写了这两种解决方案。他们采用相同的蛮力方法来测试Collatz 猜想。组装解决方案通过以下方式组装：
nasm -felf64 p14.asm && gcc p14.o -o p14C ++ 使用以下命令进行编译：
g++ p14.cpp -o p14汇编， p14.asm ：
section .data
fmt db "%d", 10, 0
global main
extern printf
section .text
main:
mov rcx, 1000000
xor rdi, rdi ; max i
xor rsi, rsi ; i
l1:
dec rcx
xor r10, r10 ; count
mov rax, rcx
l2:
test rax, 1
jpe even
mov rbx, 3
mul rbx
inc rax
jmp c1
even:
mov rbx, 2
xor rdx, rdx
div rbx
c1:
inc r10
cmp rax, 1
jne l2
cmp rdi, r10
cmovl rdi, r10
cmovl rsi, rcx
cmp rcx, 2
jne l1
mov rdi, fmt
xor rax, rax
call printf
retC ++， p14.cpp ：
#include <iostream>
int sequence(long n) {
int count = 1;
while (n != 1) {
if (n % 2 == 0)
n /= 2;
else
n = 3*n + 1;
++count;
}
return count;
}
int main() {
int max = 0, maxi;
for (int i = 999999; i > 0; --i) {
int s = sequence(i);
if (s > max) {
max = s;
maxi = i;
}
}
std::cout << maxi << std::endl;
}我知道可以提高速度和所有方面的编译器优化，但是我看不出有很多方法可以进一步优化我的汇编解决方案（以编程的方式，而不是数学的方式）。
C ++ 代码每项使用模，每隔项使用除法，而汇编代码每隔项仅使用一个除法。
但是，汇编程序比 C ++ 解决方案平均要花费 1 秒钟的时间。为什么是这样？我主要是出于好奇而问。
我的系统：1.4 GHz Intel Celeron 2955U（Haswell 微体系结构）上的 64 位 Linux。
g++ (unoptimized): avg 1272 ms.g++ -O3: avg 578 ms.asm (div) (original): avg 2650 ms.asm (shr): avg 679 ms.-O3, 305 ms with -O0.如果您认为 64 位 DIV 指令是除以 2 的好方法，那么即使使用-O0 ，编译器的 asm 输出也会击败您的手写代码（编译速度快，没有额外的优化，并且存储 / 重装到内存中）每个 C 语句之后 / 之前，以便调试器可以修改变量）。
请参阅Agner Fog 的 “优化程序集” 指南以了解如何编写高效的 asm。他还提供了指令表和 Microarch 指南，以了解特定 CPU 的特定详细信息。有关更多性能链接，另请参见x86 标签 Wiki。
另请参阅有关用手写 asm 击败编译器的更一般的问题：内联汇编语言是否比本机 C ++ 代码慢？ 。 TL：DR：是的，如果您做错了（像这个问题）。
通常，您可以让编译器执行其工作，尤其是当您尝试编写可以高效编译的 C ++ 时。还可以看到汇编语言比编译语言要快吗？ 。答案之一链接到这些整洁的幻灯片，这些幻灯片显示了各种 C 编译器如何使用很酷的技巧优化一些非常简单的功能。 Matt Godbolt 在 CppCon2017 上的演讲 “最近我的编译器为我做了什么？解开编译器的盖子也与此类似。
even:
mov rbx, 2
xor rdx, rdx
div rbx在 Intel Haswell 上， div r64为 36 oups，延迟为32-96 个周期，每 21-74 个周期为一个吞吐量。 （加上 2 个指令来设置 RBX 和 0 个 RDX，但是乱序执行可以使它们早点运行）。像 DIV 这样的高计数指令是经过微码处理的，这也可能导致前端瓶颈。在这种情况下，延迟是最相关的因素，因为它是循环承载的依赖链的一部分。
shr rax, 1执行相同的无符号除法：这是 1 uop，延迟为 1c ，并且每个时钟周期可以运行 2 次。
相比之下，32 位除法速度更快，但与移位相比仍然可怕。 idiv r32在 Haswell 上的吞吐量为 9 oups，延迟为 22-29c，每 8-11c 吞吐量为 1。
从查看 gcc 的-O0 asm 输出（ Godbolt 编译器浏览器）可以看出，它仅使用 shifts 指令。 clang -O0确实像您想的那样天真地编译，即使两次使用 64 位 IDIV。 （优化时，如果源完全使用 IDIV，则当源使用相同的操作数进行除法和模数运算时，编译器会同时使用 IDIV 的两个输出）
GCC 没有完全天真的模式。它总是通过 GIMPLE 进行转换，这意味着不能禁用某些 “优化” 。这包括识别分割逐常数和使用移位（2 的幂）或定点乘法逆（2 非功率），以避免 IDIV（参见div_by_13在上述 godbolt 链接）。
gcc -Os （大小优化）的确将 IDIV 用于非 2 的幂次除法，不幸的是，即使在乘法逆代码仅稍大而又快得多的情况下也是如此。
（这种情况的摘要：使用uint64_t n ）
首先，查看优化的编译器输出只是很有趣。 （ -O3 ）。 -O0速度基本上是没有意义的。
查看您的 asm 输出（在 Godbolt 上，或参阅如何从 GCC / clang 程序集输出中消除 “噪音”？ ）。当编译器一开始没有编写最佳代码时：以一种指导编译器编写更好代码的方式编写 C / C ++ 源代码通常是最好的方法。您必须了解 asm，并知道有效的方法，但是您可以间接应用此知识。编译器也是一个很好的想法来源：有时 clang 会做一些很酷的事情，并且您可以让 gcc 进行相同的操作：请参见以下答案以及我对 @Veedrac 的代码中的非展开循环所做的操作。）
这种方法是可移植的，并且在 20 年后，将来的编译器可以将其编译为在将来的硬件（无论是否为 x86）上有效的东西，也许使用新的 ISA 扩展或自动向量化。 15 年前的手写 x86-64 asm 通常不会针对 Skylake 进行最佳调整。例如，compare＆branch 宏融合当时还不存在。对于一个微体系结构而言，现在对于手工组装的 asm 的最佳选择可能不适用于当前和将来的其他 CPU。 @johnfound 答案的注释讨论了 AMD Bulldozer 和 Intel Haswell 之间的主要差异，这对这段代码有很大的影响。但是从理论上讲， g++ -O3 -march=bdver3和g++ -O3 -march=skylake会做正确的事情。 （或-march=native 。）或-mtune=...仅进行调整，而无需使用其他 CPU 可能不支持的指令。
我的感觉是，将编译器引导到对您关心的当前 CPU 有利的 asm 不会对将来的编译器造成问题。希望它们比当前的编译器在寻找转换代码的方法方面更好，并且可以找到适用于将来的 CPU 的方法。无论如何，将来的 x86 可能不会对当前的 x86 产生任何好处，并且将来的编译器在实现 C 语言中的数据移动之类的东西时，如果看不到更好的东西，它将避免任何特定于 asm 的陷阱。
手写的 asm 是优化程序的黑匣子，因此当内联使输入成为编译时常量时，常量传播不起作用。其他优化也会受到影响。使用 asm 之前，请先阅读https://gcc.gnu.org/wiki/DontUseInlineAsm。 （并避免使用 MSVC 风格的嵌入式 asm：输入 / 输出必须通过内存，这会增加开销。）
在这种情况下：您的n具有带符号的类型，并且 gcc 使用 SAR / SHR / ADD 序列给出正确的舍入。 （对于负输入，IDIV 和算术移位 “回合” 有所不同，请参见SAR insn set ref 手动输入）。 （IDK 如果 gcc 尝试并未能证明n不能为负或类似的结果。Signed-overflow 是未定义的行为，因此它应该能够。）
您应该使用uint64_t n ，所以它只能是 SHR。因此，它可移植到long系统（例如 x86-64 Windows）上。
顺便说一句， gcc 的优化的asm 输出看起来不错（使用unsigned long n ） ：内联到main()的内部循环可以做到这一点：
# from gcc5.4 -O3 plus my comments
# edx= count=1
# rax= uint64_t n
.L9: # do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
mov rdi, rax
shr rdi # rdi = n>>1;
test al, 1 # set flags based on n%2 (aka n&1)
mov rax, rcx
cmove rax, rdi # n= (n%2) ? 3*n+1 : n/2;
add edx, 1 # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)
cmp/branch to update max and maxi, and then do the next n内部循环是无分支的，循环进行的依赖链的关键路径是：
总计：每次迭代 5 个周期，延迟瓶颈。乱序执行会与此同时进行其他所有工作（理论上：我尚未使用 perf 计数器进行测试，以查看它是否真的以 5c / iter 的速度运行）。
cmov的 FLAGS 输入（由 TEST 生产）比 RAX 输入（来自 LEA-> MOV）的生产速度更快，因此它不在关键路径上。
同样，产生 CMOV 的 RDI 输入的 MOV-> SHR 也偏离了关键路径，因为它也比 LEA 快。 IvyBridge 及更高版本上的 MOV 具有零延迟（在寄存器重命名时处理）。 （它仍然需要一个 uop 和一个管道中的插槽，因此它不是免费的，只是零延迟）。 LEA dep 链中额外的 MOV 是其他 CPU 瓶颈的一部分。
cmp / jne 也不是关键路径的一部分：它不是循环携带的，因为控制依赖项是通过分支预测 + 推测执行来处理的，这与关键路径上的数据依赖项不同。
GCC 在这里做得很好。 inc edx而不是add edx, 1可以节省一个代码字节，因为没有人关心 P4 及其对部分标志修改指令的虚假依赖。
它还可以保存所有 MOV 指令，并且 TEST：SHR 将 CF = 设置为移出的位，因此我们可以使用cmovc代替test / cmovz 。
### Hand-optimized version of what gcc does
.L9: #do{
lea rcx, [rax+1+rax*2] # rcx = 3*n + 1
shr rax, 1 # n>>=1; CF = n&1 = n%2
cmovc rax, rcx # n= (n&1) ? 3*n+1 : n/2;
inc edx # ++count;
cmp rax, 1
jne .L9 #}while(n!=1)请参阅 @johnfound 的答案，这是另一个巧妙的技巧：通过分支 SHR 的标志结果以及将其用于 CMOV 来删除 CMP：仅当 n 为 1（或 0）时才为零。 （有趣的事实：如果您读取标志结果，Nehalem 或更早的计数为！= 1 的 SHR 会导致停顿。这就是它们使它成为单 UOP 的方式。不过，采用 shift-by-1 特殊编码还是可以的。）
避免使用 MOV 根本无法解决 Haswell 上的延迟问题（ x86 的 MOV 真的可以 “免费” 吗？为什么我根本无法重现此内容？ ）。它对诸如 MOV 不是零延迟的 Intel pre-IvB 和 AMD Bulldozer 系列的 CPU 确实有很大帮助。编译器浪费的 MOV 指令确实会影响关键路径。 BD 的 complex-LEA 和 CMOV 都具有较低的延迟（分别为 2c 和 1c），因此它是延迟的较大部分。同样，吞吐量瓶颈也成为一个问题，因为它只有两个整数 ALU 管道。 请参阅 @johnfound 的答案，其中他具有 AMD CPU 的计时结果。
即使在 Haswell 上，此版本也可以通过避免一些偶尔的延迟而有所帮助，在这种情况下，非关键的 uop 会从关键路径上的某个人窃取执行端口，从而将执行延迟 1 个周期。 （这称为资源冲突）。它还可以保存一个寄存器，这n值时可能会有所帮助（请参见下文）。
LEA 的等待时间取决于英特尔 SnB 系列 CPU 的寻址模式。 3c 用于 3 个组件（ [base+idx+const] ，需要两个单独的加法），但只有 1c 具有两个或更少的组件（一个加法）。某些 CPU（例如 Core2）甚至可以在一个周期内完成 3 组件 LEA，但 SnB 系列却不这样做。更糟糕的是，英特尔 SnB 系列对延迟进行了标准化，因此没有 2c uops ，否则 3 分量 LEA 就像 Bulldozer 一样只有 2c。 （三分量 LEA 在 AMD 上也较慢，只是幅度不那么快）。
因此，在像 Haswell 这样的 Intel SnB 系列 CPU 上lea rcx, [rax + rax*2] / inc rcx仅 2c 延迟，比lea rcx, [rax + rax*2 + 1] BD 上的收支平衡，而 Core2 上更差。它确实需要额外的 uop，通常不值得节省 1c 的延迟，但是延迟是这里的主要瓶颈，Haswell 拥有足够宽的管道来处理额外的 uop 吞吐量。
gcc，icc 或 clang（在 godbolt 上）都未使用 SHR 的 CF 输出，始终使用 AND 或 TEST 。愚蠢的编译器。 ：P 它们是复杂机械的重要组成部分，但是聪明的人经常可以在小规模问题上击败它们。 （当然，考虑到这要花费数千到数百万倍！编译器不会使用穷举算法来搜索每种可能的做事方式，因为在优化许多内联代码时这将花费很长时间。他们最擅长。他们也没有在目标微体系结构中对管道建模，至少没有与IACA或其他静态分析工具相同的细节；它们只是使用了一些启发式方法。）
简单的循环展开将无济于事；此循环瓶颈取决于循环承载的依赖链的延迟，而不是循环开销 / 吞吐量。这意味着它与超线程（或任何其他类型的 SMT）配合得很好，因为 CPU 有很多时间来交织来自两个线程的指令。这将意味着并行化main的循环，但这很好，因为每个线程只能检查n值的范围并产生一对整数。
手工在单个线程中进行交织也是可行的。也许可以并行计算一对数字的序列，因为每个数字只需要几个寄存器，并且它们都可以更新相同的max / maxi 。这会产生更多的指令级并行性。
诀窍是决定是否要等到所有n值都达到1后再获取另一对起始n值，或者是否要中断并获得仅一个到达结束条件的新起点，而不用触碰寄存器中的寄存器。其他顺序。也许最好让每个链都在处理有用的数据，否则您将不得不有条件地增加其计数器。
您甚至可以使用 SSE 打包比较的东西来执行此操作，以有条件地增加n尚未达到1矢量元素的计数器。然后，要隐藏 SIMD 条件增量实现的更长等待时间，您需要让更多n值的向量悬而未决。也许只值 256b 向量（4x uint64_t ）才值得。
我认为，检测到1 “粘滞” 的最佳策略是屏蔽添加来增加计数器的全 1 的向量。因此， 1后，增量矢量将为零，而 + = 0 为无操作。
# starting with YMM0 = [ n_d, n_c, n_b, n_a ] (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1): increment vector
# ymm5 = all-zeros: count vector
.inner_loop:
vpaddq ymm1, ymm0, xmm0
vpaddq ymm1, ymm1, xmm0
vpaddq ymm1, ymm1, set1_epi64(1) # ymm1= 3*n + 1. Maybe could do this more efficiently?
vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit
vpsrlq ymm0, ymm0, 1 # n /= 2
# FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
vpblendvpd ymm0, ymm0, ymm1, ymm3 # variable blend controlled by the sign bit of each 64-bit element. I might have the source operands backwards, I always have to look this up.
# ymm0 = updated n in each element.
vpcmpeqq ymm1, ymm0, set1_epi64(1)
vpandn ymm4, ymm1, ymm4 # zero out elements of ymm4 where the compare was true
vpaddq ymm5, ymm5, ymm4 # count++ in elements where n has never been == 1
vptest ymm4, ymm4
jnz .inner_loop
# Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero
vextracti128 ymm0, ymm5, 1
vpmaxq .... crap this doesn't exist
# Actually just delay doing a horizontal max until the very very end. But you need some way to record max and maxi.您可以并且应该使用内部函数而不是手写的 asm 来实现。
除了仅以更有效的 asm 实现相同的逻辑外，还寻求简化逻辑或避免重复工作的方法。例如记住以检测序列的共同结尾。甚至更好的是，一次查看 8 个尾随位（咬咬人的答案）
@EOF 指出tzcnt （或bsf ）可用于n/=2迭代。这可能比 SIMD 向量化更好。没有 SSE 或 AVX 指令可以做到这一点。不过，它仍然与在不同的整数寄存器中并行n
因此循环看起来像这样：
goto loop_entry; // C++ structured like the asm, for illustration only
do {
n = n*3 + 1;
loop_entry:
shift = _tzcnt_u64(n);
n >>= shift;
count += shift;
} while(n != 1);这样可以减少迭代次数，但是在没有 BMI2 的 Intel SnB 系列 CPU 上，可变计数移位很慢。 3 oups，2c 延迟。 （它们对 FLAGS 具有输入依赖关系，因为 count = 0 表示未修改标志。它们将其作为数据依赖关系进行处理，并且由于 uop 只能具有 2 个输入（无论如何，HSU / BDW 仍然如此），因此需要多个 uops）。抱怨 x86 疯狂的 CISC 设计的人们指的是这种类型。它使 x86 CPU 的速度比如果今天从头开始设计 ISA 的速度要慢，即使是采用类似的方式也是如此。 （即，这是 “x86 税” 的一部分，它消耗了速度 / 功率。）SHRX / SHLX / SARX（BMI2）是一个巨大的胜利（1 uop / 1c 延迟）。
它还将 tzcnt（在 Haswell 和更高版本上为 3c）放在关键路径上，因此，它显着延长了循环依赖链的总延迟。但是，它确实不需要 CMOV 或准备保存n>>1的寄存器。 @Veedrac 的答案通过将 tzcnt / shift 推迟多次迭代来克服了所有这些问题，这非常有效（请参阅下文）。
我们可以安全地互换使用 BSF或TZCNT ，因为此时n永远不能为零。 TZCNT 的机器代码在不支持 BMI1 的 CPU 上解码为 BSF。 （无意义的前缀将被忽略，因此 REP BSF 作为 BSF 运行）。
在支持它的 AMD CPU 上，TZCNT 的性能要比 BSF 好得多，因此使用REP BSF是一个好主意，即使您不关心将输入设置为零而不是将输出设置为 ZF 的情况。即使使用-mno-bmi __builtin_ctzll时，某些编译器也会执行此操作。
它们在 Intel CPU 上执行相同的操作，因此仅需保留字节就可以了。就像 BSF 一样，Intel（在 Skylake 之前）上的 TZCNT 仍然对所谓的仅写输出操作数具有虚假依赖关系，以支持无记录的行为，即输入 = 0 的 BSF 使其目标保持不变。因此，除非您仅针对 Skylake 进行优化，否则您需要解决此问题，因此，多余的 REP 字节没有任何好处。 （英特尔经常超越 x86 ISA 手册的要求，以避免破坏依赖于不应使用的东西或被追溯禁止的广泛使用的代码。例如， Windows 9x 假定 TLC 条目没有任何推测性的预取，这是安全的在编写代码时，是在 Intel 更新 TLB 管理规则之前。）
无论如何，Haswell 上的 LZCNT / TZCNT 具有与 POPCNT 相同的错误深度：请参阅此问答。这就是为什么在 @Veedrac 的代码的 gcc 的 asm 输出中，您会看到它在不使用 dst = src 的情况下将用作 TZCNT 的寄存器的xor-zeroing 破坏了 dep 链。由于 TZCNT / LZCNT / POPCNT 永远不会使目标保持未定义或未修改的状态，因此对 Intel CPU 输出的这种虚假依赖性是性能错误 / 限制。大概值得一些晶体管 / 电源使它们表现得像进入同一执行单元的其他微控制器一样。唯一的好处是与另一个 uarch 限制相互作用：它们可以在 Haswell 上使用索引寻址模式对存储器操作数进行微融合，但是在 Skylake 上，Intel 删除了 LZCNT / TZCNT 的伪装，他们 “取消分层” 了索引寻址模式。 POPCNT 仍可以微熔合任何加法器模式。
@hidefromkgb 的答案很好地说明了您可以保证在 3n + 1 之后可以进行一次右移。您可以比仅省去步骤之间的检查更加有效地计算出该值。但是，该答案中的 asm 实现被破坏了（它取决于 OF，在 SHRD 后计数 > 1 时未定义），并且运行缓慢： ROR rdi,2比SHRD rdi,rdi,2快，并且使用两个 CMOV 指令关键路径上的速度比可以并行运行的额外 TEST 慢。
我将经过整理 / 改进的 C（引导编译器生成更好的 asm），并在 Godbolt 上测试并运行了更快的 asm（在 C 下方的注释中）：请参见@hidefromkgb 的答案中的链接。 （此答案从大型 Godbolt URL 达到了 3 万个字符限制，但短链接可能会腐烂，反而对于 goo.gl 来说太长了。）
还改进了输出打印，以将其转换为字符串并执行一个write()而不是一次写入一个 char。这样可以最大程度地减少对使用perf stat ./collatz计时整个程序的影响（以记录性能计数器），并且我消除了对一些非关键性 asm 的混淆。
@Veedrac 的代码
我有一个小加速从右移一样，我们知道需要做什么，并检查继续循环。在 Core2Duo（Merom）上，极限 = 1e8 的 7.5s 降至 7.275s，展开系数为 16。
代码 + 关于 Godbolt 的注释。不要将此版本与 clang 一起使用；它对延迟循环做一些愚蠢的事情。使用 tmp 计数器k ，然后将其添加到count更改 clang 的功能，但这会稍微损害 gcc。
请参阅评论中的讨论：Veedrac 的代码在带有 BMI1 的 CPU（即非 Celeron / Pentium）上非常出色。
声称 C ++ 编译器比有能力的汇编语言程序员可以生成更多的最佳代码是一个非常严重的错误。特别是在这种情况下。人总是可以使代码比编译器更好，并且这种特殊情况很好地说明了这一主张。
您看到的时间差异是因为问题中的汇编代码与内循环中的最佳代码相差甚远。
（以下代码是 32 位，但可以轻松转换为 64 位）
例如，序列功能可以优化为仅 5 条指令：
.seq:
inc esi ; counter
lea edx, [3*eax+1] ; edx = 3*n+1
shr eax, 1 ; eax = n/2
cmovc eax, edx ; if CF eax = edx
jnz .seq ; jmp if n<>1整个代码如下所示：
include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"
start:
InitializeAll
mov ecx, 999999
xor edi, edi ; max
xor ebx, ebx ; max i
.main_loop:
xor esi, esi
mov eax, ecx
.seq:
inc esi ; counter
lea edx, [3*eax+1] ; edx = 3*n+1
shr eax, 1 ; eax = n/2
cmovc eax, edx ; if CF eax = edx
jnz .seq ; jmp if n<>1
cmp edi, esi
cmovb edi, esi
cmovb ebx, ecx
dec ecx
jnz .main_loop
OutputValue "Max sequence: ", edi, 10, -1
OutputValue "Max index: ", ebx, 10, -1
FinalizeAll
stdcall TerminateAll, 0为了编译此代码，需要FreshLib。
在我的测试中（1 GHz AMD A4-1200 处理器），以上代码比问题中的 C ++ 代码快四倍（当使用-O0编译时：430 ms 与 1900 ms），并且快两倍以上-O3编译 C ++ 代码时（430 ms 与 830 ms）。
这两个程序的输出是相同的：i = 837799 时，最大序列 = 525。
为了获得更高的性能：一个简单的变化就是观察 n = 3n + 1 之后，n 将为偶数，因此您可以立即除以 2。 n 不会为 1，因此您不需要测试。因此，您可以保存一些 if 语句并编写：
while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
n = (3*n + 1) / 2;
if (n % 2 == 0) {
do n /= 2; while (n % 2 == 0);
if (n == 1) break;
}
}这是一个巨大的胜利：如果查看 n 的最低 8 位，那么除以 2 八次之前的所有步骤完全取决于这 8 位。例如，如果最后八位是 0x01（即二进制），则您的数字是???? 0000 0001，接下来的步骤是：
3n+1 -> ???? 0000 0100
/ 2 -> ???? ?000 0010
/ 2 -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2 -> ???? ???0 0010
/ 2 -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2 -> ???? ???? ?010
/ 2 -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2 -> ???? ???? ???0
/ 2 -> ???? ???? ????因此可以预测所有这些步骤，并用 81k + 1 代替 256k + 1。因此，您可以使用大的 switch 语句进行循环：
k = n / 256;
m = n % 256;
switch (m) {
case 0: n = 1 * k + 0; break;
case 1: n = 81 * k + 1; break;
case 2: n = 81 * k + 1; break;
...
case 155: n = 729 * k + 425; break;
...
}循环运行直到 n≤128，因为在那一刻，n 可能会变成 1，而除以 2 的次数将少于 8，那么执行一次八步或更多步将使您错过第一次达到 1 的点。然后继续 “正常” 循环 - 或准备一张表，告诉您要达到 1 还需要多少步骤。
PS。我强烈怀疑彼得 · 科德斯（Peter Cordes）的建议会使其更快。除了一个条件分支外，将没有条件分支，除非循环实际结束，否则将正确预测一个条件分支。所以代码会像
static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }
while (n > 128) {
size_t lastBits = n % 256;
n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}在实践中，您将测量一次处理 n 的最后 9、10、11、12 位是否更快。对于表的每一位，表中的条目数将增加一倍，当表不再适合 L1 缓存时，我会发现速度变慢。
PPS。如果您需要操作数：在每次迭代中，我们将精确地除以 8 除以 2，并有可变数量的（3n +1）个操作，因此计算操作数的一个显而易见的方法是使用另一个数组。但是我们实际上可以计算步骤数（基于循环的迭代数）。
我们可以稍微重新定义问题：如果奇数为 n，则用（3n +1）/ 2 替换 n；如果偶数为 n，则将 n 替换为 n / 2。然后，每个迭代将精确地执行 8 个步骤，但是您可以考虑作弊:-) 因此，假设存在 r 个操作 n <-3n + 1 和 s 个操作 n <-n / 2。结果将非常精确地为 n'= n * 3 ^ r / 2 ^ s，因为 n <-3n + 1 意味着 n <-3n *（1 + 1 / 3n）。取对数，我们得出 r =（s + log2（n'/ n））/ log2（3）。
如果我们进行循环直到 n≤1,000,000，并有一个预先计算的表，则从任何 n≤1,000,000 的起始点需要进行多少次迭代，然后按上述方法计算 r（四舍五入为最接近的整数）将得到正确的结果，除非 s 确实很大。