math - 在我的汇编程序中，我试图计算方程 (((((2^0 + 2^1) * 2^2) + 2^3) * 2^4) + 2^5)

您使用静态变量和分支使代码过于复杂。

这些是 2 的幂，您可以（并且应该）只左移n而不是实际构造2^n和使用mul指令。

add eax,eax是乘以 2（也就是左移乘以 1）的最佳方法，但目前尚不清楚为什么要对 EAX 中的值这样做。它要么是乘法结果（您可能应该将其存储回runtotafter mul），要么是在偶数迭代后左移 1。

如果您试图创建一个2^i变量（通过强度降低优化，每次迭代移动 1 而不是移动i），那么您的错误是您在块中使用mul及其设置来破坏 EAX。oddexp

正如 Jester 指出的那样，如果第一个loop loop1通过，它将通过oddexp:. 当您进行循环尾部复制时，请确保您考虑如果循环确实在那里结束，则从每个尾部开始下降。

拥有一个名为的静态变量也是没有意义的，bool它包含 a 1，您只能将其用作的操作数test。这对人类读者来说意味着面具有时需要改变。test ecx,1作为一种检查低位为零/非零的方法要清楚得多。

您也不需要静态存储runtot，只需使用寄存器（例如 EAX，您最终还是希望得到结果）。32 位 x86 有 7 个寄存器（不包括堆栈指针）。

我就是这样做的。未经测试，但我通过展开 2 简化了很多。然后奇数/偶数测试消失了，因为该交替模式被硬编码到循环结构中。

我们在循环中增加和比较/分支两次，所以展开并没有摆脱循环开销，只是将循环分支之一更改为if() break可以从中间离开循环的 an。

这不是最有效的写法；循环中间的增量和提前退出检查可以通过从开始向下计数另一个计数器来优化，n如果剩下的步骤少于 2 则退出循环。（然后在结语中整理）

;; UNTESTED
power proc   ; fastcall calling convention: arg: ECX = unsigned int n
             ; clobbers: ECX, EDX
             ; returns: EAX

    push  ebx           ; save a call-preserved register for scratch space

    mov   eax, 1        ; EAX = 2^0   running total / return value
    test  ecx,ecx
    jz    done

    mov   edx, ecx      ; EDX = n
    mov   ecx, 1        ; ECX = i=1..n loop counter and shift count

loop1:                  ; do{   // unrolled by 2
    ; add 2^odd power
    mov   ebx, 1
    shl   ebx, cl         ; 2^i         ; xor   ebx, ebx; bts   ebx, ecx
    add   eax, ebx        ; total += 2^i

    inc   ecx
    cmp   ecx, edx
    jae   done            ; if (++i >= n) break;

    ; multiply by 2^even power
    shl   eax, cl       ; total <<= i;  // same as total *= (1<<i)

    inc   ecx           ; ++i
    cmp   ecx, edx
    jb    loop1         ; }while(i<n);

done:
    pop  ebx
    ret

我没有检查添加奇功率步骤是否会产生进位。我认为它没有，因此将其实现为bts eax, ecx（设置位i）可能是安全的。实际上是 OR 而不是 ADD，但只要该位先前被清除，这些都是等效的。

为了使 asm 看起来更像源代码并避免晦涩的指令，我实现1<<i了shlto generate 2^ifor total += 2^i，而不是更高效的 Intel xor ebx,ebx/ bts ebx, ecx。（由于 x86 标志处理遗留包袱，英特尔 Sandybridge 系列上的变量计数移位为 3 微秒：如果计数 = 0，则标志必须保持不变）。但在 AMD Ryzen 上情况更糟，bts reg,reg2 微指令shl reg,cl是 1。

更新：添加时i=3 确实会产生进位，因此我们不能在这种情况下对位进行 OR 或 BTS 操作。但是可以通过更多分支进行优化。

使用calc：

; define shiftadd_power(n) { local res=1; local i; for(i=1;i<=n;i++){ res+=1<<i; i++; if(i>n)break; res<<=i;} return res;}
shiftadd_power(n) defined
; base2(2)

; shiftadd_power(0)
        1 /* 1 */
...

前几个输出是：

n          shiftadd(n) (base2)

0                   1
1                  11
2                1100
3               10100     ; 1100 + 1000 carries
4           101000000
5           101100000     ; 101000000 + 100000 set a bit that was previously 0
6     101100000000000
7     101100010000000     ; increasing amounts of trailing zero around the bit being flipped by ADD

剥离前 3 次迭代将启用 BTS 优化，您只需设置位而不是实际创建2^n和添加。

我们可以硬编码更大的 n 的起点，而不是仅仅i=3剥离它们，并优化为案例计算返回值的代码n<3。我提出了一个基于将位模式右移0b11003、2 或 0 的无分支公式。

另请注意，对于 n>=18，最后一个移位计数严格大于寄存器宽度的一半，并且奇数的 2^ii没有低位。所以只有最后 1 或 2 次迭代会影响结果。它归结1<<n为奇数n或0偶数n。这简化为(n&1) << n。

对于n=14..17，最多设置 2 位。从 result=0 开始并进行最后 3 或 4 次迭代应该足以获得正确的总数。事实上，对于 any n，我们只需要进行最后k一次迭代，其中k就足以使从 even 的总移位计数i>= 32。由早期迭代设置的任何位都被移出。（我没有为这种特殊情况添加分支。）

;; UNTESTED
;; special cases for n<3, and for n>=18
;; enabling an optimization in the main loop (BTS instead of add)
;; funky overflow behaviour for n>31: large odd n gives 1<<(n%32) instead of 0
power_optimized proc
     ; fastcall calling convention: arg: ECX = unsigned int n <= 31
     ; clobbers: ECX, EDX
     ; returns: EAX

    mov   eax, 14h      ; 0b10100 = power(3)
    cmp   ecx, 3
    ja    n_gt_3        ; goto main loop or fall through to hard-coded low n
    je    early_ret
    ;; n=0, 1, or 2  =>  1, 3, 12  (0b1, 0b11, 0b1100)

    mov   eax, 0ch      ; 0b1100  to be right-shifted by 3, 2, or 0
    cmp   ecx, 1        ; count=0,1,2 => CF,ZF,neither flag set
    setbe cl            ; count=0,1,2 => cl=1,1,0
    adc   cl, cl        ;                   3,2,0  (cl = cl+cl + (count<1) )
    shr   eax, cl
early_ret:
    ret

large_n:                ; odd n: result = 1<<n.  even n: result = 0
    mov   eax, ecx
    and   eax, 1        ; n&1
    shl   eax, cl       ; n>31 will wrap the shift count so this "fails"
    ret                 ; if you need to return 0 for all n>31, add another check

n_gt_3:
    ;; eax = running total for i=3 already
    cmp   ecx, 18
    jae   large_n

    mov   edx, ecx      ; EDX = n
    mov   ecx, 4        ; ECX = i=4..n loop counter and shift count

loop1:                  ; do{   // unrolled by 2
    ; multiply by 2^even power
    shl   eax, cl       ; total <<= i;  // same as total *= (1<<i)

    inc   edx
    cmp   ecx, edx
    jae   done            ; if (++i >= n) break;

    ; add 2^odd power.  i>3 so it won't already be set (thus no carry)
    bts   eax, edx      ; total |= 1<<i;

    inc   ecx           ; ++i
    cmp   ecx, edx
    jb    loop1         ; }while(i<n);

done:
    ret

通过使用 BTS 在 EAX 中设置一个位，避免了需要额外的暂存寄存器来构建1<<i，因此我们不必保存/恢复 EBX。所以这是一个小的奖金节省。

请注意，这次进入主循环时使用的i=4是偶数，而不是i=1。所以我交换了 add 与 shift。

我仍然没有把cmp/jae拉出循环的中间。类似lea edx, [ecx-2]而不是mov设置循环退出条件，但需要检查是否在 i=4 或 5 时根本不运行循环。对于大计数吞吐量，许多 CPU 可以维持 1 个采取 + 1 个未采取的分支每个2 个时钟，不会造成比循环携带的 dep 链（通过eax和ecx）更糟糕的瓶颈。但是分支预测会有所不同，它使用更多的分支顺序缓冲区条目来记录更多可能的回滚/快速恢复点。

math - 在我的汇编程序中，我试图计算方程 (((((2^0 + 2^1) * 2^2) + 2^3) * 2^4) + 2^5)

问题描述

解决方案

推荐阅读