选择合适的整数运算方法

【简单移位】

大家都知道对于整数乘以2的幂可以通过位左移完成，整数除以2的幂可以通过位右移完成。

实际上现在的编译很聪明，即使不显式地用移位的方式优化，编译器也会自动帮忙完成优化，不过前提是这个数是2的幂且是常量。

【整数除&求余】

整数除法和求模往往成对的出现，如：

quotient = dividend  / divisor 

remainder = dividend  % divisor

因为除法操作比乘法要慢很多，所以很自然的优化成如下的形式：

quotient = dividend  / divisor 

remainder = dividend - divisor * quotient 

但是这种“优化”未必真的管用，下面进行分析：

Gcc –O2的情况：

【除数为变量】

1.       使用remainder = dividend  % divisor

    int dividend;

    int divisor；

    int quotient = dividend  / divisor;

    int remainder = dividend  % divisor;

printf("dividend=%d, divisor=%d, quotient=%d, remainder=%dn", dividend, divisor, quotient, remainder);

汇编：

.LFB771:

        movl    %esi, %edx

        movl    %esi, %eax

        subq    $8, %rsp

.LCFI0:

        sarl    $31, %edx

        movl   $.LC0, %edi

        idivl    %esi

        movl    %edx, %r8d

        movl    %eax, %ecx

        movl    %esi, %edx

        xorl    %eax, %eax

        call    printf

2.       使用remainder = dividend - divisor * quotient

    int dividend;

    int divisor；

    int quotient = dividend  / divisor;

    int remainder = dividend - divisor * quotient

printf("dividend=%d, divisor=%d, quotient=%d, remainder=%dn", dividend, divisor, quotient, remainder);

汇编：

.LFB771:

        movl    %esi, %edx

        movl    %esi, %eax

        movl    %esi, %r8d

        sarl     $31, %edx

        subq    $8, %rsp

.LCFI0:

        movl    $.LC0, %edi

        idivl    %esi

        movl    %esi, %edx

        movl    %eax, %ecx

        movl    %esi, %eax

        imull   %ecx, %eax

        subl    %eax, %r8d

        xorl    %eax, %eax

        call    printf

对比：第二种方式使用了一次除法，一次乘法，一次减法。第一种方式只使用了一次除法！

      也就是说remainder = dividend % divisor这种原始的方式效率更高！

         原因分析：汇编代码的idiv(div一样)操作可以同时获取到商和余数。

         EDX:EAX / divisor 得到 (EAX, EDX)。除之前EDX:EAX对应被除数，除之后EAX对应商，EDX对应余数。

【除数为常量】

3.       使用remainder = dividend  % divisor

    int dividend;

    int divisor = 100；

    int quotient = dividend  / divisor;

    int remainder = dividend  % divisor;

printf("dividend=%d, divisor=%d, quotient=%d, remainder=%dn", dividend, divisor, quotient, remainder);

汇编：

.LFB771:

        movl    %esi, %eax

        movl    $1374389535, %edx

        movl    $100, %ecx

        imull    %edx

        movl    %esi, %eax

        movl    %esi, %r8d

        sarl     $31, %eax

        subq    $8, %rsp

.LCFI0:

        movl    $.LC0, %edi

        sarl    $5, %edx

        subl    %eax, %edx

        movl    %edx, %eax

        imull   %ecx, %eax

        movl    %edx, %ecx

        movl    $100, %edx

        subl    %eax, %r8d

        xorl    %eax, %eax

        call    printf

从以上汇编可以看出：

quotient = dividend / 100优化成了quotient = (((dividend * 1374389535) >> 32) >> 5) - (dividend >> 31) 

可以用python验证两者的等价性：

>>> dividend=65332324

>>> (((dividend * 1374389535) >> 32) >> 5) - (dividend >> 31); dividend / 100

653323

653323

dividend % 100 优化成了dividend – 100 * quotient

4.       使用remainder = dividend  - divisor * quotient

    int dividend;

    int divisor = 100；

    int quotient = dividend  / divisor;

    int remainder = dividend - divisor * quotient

printf("dividend=%d, divisor=%d, quotient=%d, remainder=%dn", dividend, divisor, quotient, remainder);

汇编：

.LFB771:

        movl    %esi, %eax

        movl    $1374389535, %edx

        movl    $100, %ecx

        imull    %edx

        movl    %esi, %eax

        movl    %esi, %r8d

        sarl     $31, %eax

        subq    $8, %rsp

.LCFI0:

        movl    $.LC0, %edi

        sarl    $5, %edx

        subl    %eax, %edx

        movl    %edx, %eax

        imull   %ecx, %eax

        movl    %edx, %ecx

        movl    $100, %edx

        subl    %eax, %r8d

        xorl    %eax, %eax

        call    printf

对比：两种方式的结果完全一样。

Gcc不使用优化选项的情况：

【除数为变量】

1.       使用remainder = dividend  % divisor

汇编：idivl + idivl

2．使用remainder = dividend  - divisor * quotient

汇编：idivl + imull + subl

【除数为常量】

3.       使用remainder = dividend  % divisor

汇编：idivl + idivl

4.       使用remainder = dividend  - divisor * quotient

汇编：idivl + imull + subl

对比：除数为常量和变量都一样（这个常量非2的幂）

【有符号vs 无符号】

以 intvar / 137 和uintvar / 137为例

intvar / 137汇编：

.LFB771:

        movl    %esi, %eax

        movl    $125400505, %edx

        subq    $8, %rsp

.LCFI0:

        imull   %edx

        movl    %esi, %eax

        movl    $.LC0, %edi

        sarl    $31, %eax

        sarl    $2, %edx

        subl    %eax, %edx

        xorl    %eax, %eax

        call    printf

intvar / 137优化成了(((intvar * 125400505) >> 32) >> 2) - (intvar >> 31)

python验证：

>>> intvar=434325

>>> (((intvar * 125400505) >> 32) >> 2) - (intvar >> 31); intvar / 137

3170

3170

uintvar / 137汇编：

.LFB771:

        movl    %esi, %eax

        movl    $125400505, %edx

        subq    $8, %rsp

.LCFI0:

        mull    %edx

        movl    $.LC0, %edi

        xorl    %eax, %eax

        shrl    $2, %edx

        call    printf

uintvar / 137优化成了(((uintvar * 125400505) >> 32) >> 2)

python 验证：

>>> uintvar=434325

>>> (((uintvar * 125400505) >> 32) >> 2); uintvar / 137

3170

3170

对比：有符号的操作比无符号的操作多一次符号修正：- (intvar >> 31)。

            如果intvar为负数，(intvar >> 31)为-1，结果相当于+1。

            如果intvar非负，(intvar >> 31)为0，结果相当于-0。

【结论】

1.       Gcc不加优化选项时，对非2的幂作除法和求模运算不会作任何优化，汇编代码只是简单翻译

2.       Gcc加优化选项时（比如-O2），对于整数除法和求模，应该用：

   int quotient = dividend / divisor;

   int remainder = dividend % divisor;

而不是

      int quotient = dividend / divisor;

      int remainder = dividend - divisor * quotient

3.       如果确定整数不会有负数，使用无符号类型性能更好。

最后

以上就是凶狠长颈鹿为你收集整理的选择合适的整数运算方法的全部内容，希望文章能够帮你解决选择合适的整数运算方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。