另辟蹊径，next power of two新解法

June 5, 2019

0x0 什么是next power of 2?

给定正整数n， 求比n大的最小的2的幂次的数m

例如：

3 ->4

5->8

19->32

0x01 常规解法

unsigned int next_power_of_two_log(unsigned int v)
{
        double next = pow(2, ceil(log2(v)));
        return (int)next;
}

通俗易懂，但是慢。

0x02 快速解法

unsigned long upper_power_of_two(unsigned long v){
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;

}

仅使用了位移和位操作， 巧妙 ，快速。

0x03 float解法(新解法)

思路：利用float的数据存储特性，直接提取指数部分。

IEEE 754单精度浮点数格式

浮点数数值的计算方法

因为我们的条件是正整数， 因此sign可以不看， 其次小数(fraction)部分，并不会影响我们的计算结果因为

$$ 2^{(e-127)}\times \left ( 1+\sum_{i=1}^{23}b_{23-i}2^{-i} \right ) < 2^{(e-127 +1)} $$

因此我们只需要重点关注exponent中的数据，这里记录了浮点数的指数部分，实际指数的值是偏移了127的，因此实际指数是e-127(PS:有一个例外， 下面会讲到)。

实际代码实现

unsigned int next_power_of_two(unsigned int v)
{
        if(v == 1) return 2;    //1 is an exception
        v--;
        float f = (float)v;
        unsigned int* pf = reinterpret_cast<unsigned int *>(&f);
        *pf = *pf << 1;         //remove sign bit
        *pf = *pf >> 24;        //move to least significant byte
        *pf = *pf - 127 + 1;
        return 1 << *pf;
}

为什么1是例外？

算法中需要先减一，因此实际操作的float值为0， 而IEEE754的float值为0的时候其指数部分(exponent)也为0，而不是127， 这就无法使用后面算法统一计算了。

0x04 运行效率大PK float解法是否能威胁到快速解法的擂主地位？！！

运行效率比较

float解法比快速解法慢了80.4%！！！ logf解法最慢，比快速解法慢了889.1%！！！

g++ -O2 汇编代码比较

00000690 <float方法>:
690:   83 ec 14                sub    $0x14,%esp
693:   8b 44 24 18             mov    0x18(%esp),%eax
697:   c7 44 24 04 00 00 00    movl   $0x0,0x4(%esp)
69e:   00
69f:   83 e8 01                sub    $0x1,%eax
6a2:   89 04 24                mov    %eax,(%esp)
6a5:   df 2c 24                fildll (%esp)
6a8:   d9 1c 24                fstps  (%esp)
6ab:   8b 04 24                mov    (%esp),%eax
6ae:   83 c4 14                add    $0x14,%esp
6b1:   8d 0c 00                lea    (%eax,%eax,1),%ecx
6b4:   b8 01 00 00 00          mov    $0x1,%eax
6b9:   c1 e9 18                shr    $0x18,%ecx
6bc:   83 e9 7e                sub    $0x7e,%ecx
6bf:   d3 e0                   shl    %cl,%eax
6c1:   c3                      ret


000006d0 <快速方法>:
6d0:   8b 44 24 04             mov    0x4(%esp),%eax
6d4:   8d 50 ff                lea    -0x1(%eax),%edx
6d7:   89 d0                   mov    %edx,%eax
6d9:   d1 e8                   shr    %eax
6db:   09 d0                   or     %edx,%eax
6dd:   89 c2                   mov    %eax,%edx
6df:   c1 ea 02                shr    $0x2,%edx
6e2:   09 d0                   or     %edx,%eax
6e4:   89 c2                   mov    %eax,%edx
6e6:   c1 ea 04                shr    $0x4,%edx
6e9:   09 c2                   or     %eax,%edx
6eb:   89 d0                   mov    %edx,%eax
6ed:   c1 e8 08                shr    $0x8,%eax
6f0:   09 c2                   or     %eax,%edx
6f2:   89 d0                   mov    %edx,%eax
6f4:   c1 e8 10                shr    $0x10,%eax
6f7:   09 d0                   or     %edx,%eax
6f9:   83 c0 01                add    $0x1,%eax
6fc:   c3                      ret

相比快速方法更慢的原因

0x05 后记

快速算法在加载了数据之后全部都在寄存器内操作完成， 确实非常厉害。

float算法是刚毕业时做合图工具时想到的解法，虽然性能上比不上快速算法， 但是折腾起来倒还是挺有意思的:P

参考

Comments

comments powered by Disqus