用位运算实现求绝对值-有效避开if-else判断

xiaoxiao2021-02-28  59

By SmartPtr(http://www.cppblog.com/SmartPtr/)

一般情况下,如果要我们写一个求绝对值的函数,我们的实现很有可能会是这样:

template < class  T > T abs_Normal(T tNum) {      if (tNum  >   0.0 )          return  tNum;      else          return   - tNum; }

也就是说我们会用到一个if-else判断来决定是否反转符号位。在3D游戏软件,或一些对性能要求比较高的底层系统中,当大规模的求绝对值时,这个if-else结构会带来性能上的损失,那么,如何来消除if-else结构呢?或许会有人说,我们可以用三元操作符啊:

template < class  T > T abs_Normal(T tNum) {       return  tNum  >   0.0   ?  tNum :  - tNum; }

 但是事实上这是换汤不换药,因为其实质上还是存在if-else的判断的(这应该可以从反汇编代码中看出来)。   我们是通过位操作来消除if-else判断来求绝对值。   因为使用位操作,我们不得不考虑我们操作对象类型的字节数,下面我将以都是4字节得float和int为例实现位操作求绝对值。  首先,我们有必要了解一下float与int在计算机中的内部表示方法。 1) float: float即单精度浮点数,"浮点数"由两部分组成,即尾数和阶码。在浮点表示方法中,小数点的位置是浮动的,阶码可取不同的数值。为了便于计算机中小数点的表示,规定将浮点数写成规格化的形式,即尾数的绝对值大于等于0.1并且小于1,从而唯一规定了小数点的位置。尾数的长度将影响数的精度,其符号将决定数的符号。浮点数的阶码相当于数学中的指数,其大小将决定数的表示范围。一个浮点数在计算机中的表现形式如下: 尾数符号 阶码 尾数有效值   2) int: 用补码表示,因为正整数的原码,反码,补码都是一样的,而负整数的补码则是通过原码->反码->补码转换来的,所以,-3与3的内部表示位差别不仅仅在符号位 其次,这里先列出两个在代码中用到的宏: #define INV_SIGN_BIT 0x7fffffff //用来反转符号位 #define USE_ASM         //是否使用汇编代码   1 float求绝对值  知道了float的内部表示,我们知道要求其绝对值,只要将其尾数符号位置0即可。这又有下面两种方法:  1)与:通过和INV_SIGN_BIT相"与"而将符号位置0

inline  float  Fabs_and( float  fNum) { #ifdef USE_ASM      float  fOut;     __asm     {         MOV EAX, fNum;         AND EAX, INV_SIGN_BIT;  // set the sign bit to 0 by AND         MOV fOut, EAX;     }      return  fOut; #else      int *  temp  =  ( int * ) & fNum;      int   out   =   * temp  &  INV_SIGN_BIT;      return   * (( float * ) & out ); #endif   }

注: 1)这里将float转化成int的原因是C语言不支持float的移位操作。   2)移位:通过先逻辑左移1位,再逻辑右移一位将符号位置0

inline  float  Fabs_shift( float  fNum) { #ifdef USE_ASM      float  fOut  =   0 ;     __asm     {         MOV EAX, fNum;         SHL EAX,  1 // set the sign bit to 0 by shift left then right         SHR EAX,  1 ;         MOV fOut, EAX;     }      return  fOut; #else     unsigned  int *  temp  =  (unsigned  int * ) & fNum;     unsigned  int   out   =   * temp;        out   =   out   <<   1 ;      out   =   out   >>   1 ;        return   * (( float * ) & out ); #endif }

注: 1)这里使用unsigned int的原因是C语言的移位操作对有符号数是算术移位,对无符号数是逻辑移位。而我们需要的是逻辑移位   2 int求绝对值 因为整型的内部表示是反码,我们不能简单的通过符号位置0求绝对值,下面的算法很好的解决了这个问题:

inline  int  Abs_bit( int  iNum ) { #ifdef USE_ASM      int  iOut  =   0 ;     __asm     {         MOV EAX, iNum;         MOV EDX, EAX;         SAR EDX,  31 ;    // all of edx's bit are eax's sign bit: 000.. or 111         XOR EAX, EDX;  // this interesting algorithm help to avoid "if else" structure         SUB EAX, EDX;         MOV iOut, EAX;     }      return  iOut; #else        int   out   =  iNum;      int  temp  =  iNum;     temp  =  temp  >>   31 ;        out   =   out   ^  temp;      out   =   out   -  temp;        return   out ;   #endif }

注: 1)对于代码          temp = temp >> 31;          out = out ^ temp;          out = out - temp; 如果iNum是正数:          temp = temp >> 31; //temp = 0          out = out ^ temp; //与0异或不变          out = out - temp; //减0不变   out的结果就是iNum,即正数的绝对值是其本身,没问题   如果iNum是负数:          temp = temp >> 31; //temp = oxffffffff          out = out ^ temp; //out为iNum求反          out = out - temp; // 此时temp = 0xffffffff = -1, 所以out = out + 1 把一个负数的补码连符号位求反后再加1,就是其绝对值了。比如对于-2来说:

原码  反码 补码 补码全求反 再加1 备注 10000010 11111101  11111110 00000001 00000010  

大家可以看到第一个与最后一个数只有符号位不同,也就实现了求其绝对值。   对于其他类型的数据求绝对值,应该 都是大同小异的。这里就不再列举。

转载请注明原文地址: https://www.6miu.com/read-51720.html

最新回复(0)