SmartPtr
本博客已搬至:http://www.cnblogs.com/baiyanhuang/
posts - 29,comments - 176,trackbacks - 0
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

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

posted on 2007-07-05 17:56 SmartPtr 阅读(7828) 评论(13)  编辑 收藏 引用

FeedBack:
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 18:33 | SuperPlayeR
大人是搬家了吧,一下子贴了这么多文章上来了。呵呵~
受教了~~  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 19:37 | SmartPtr
对,就是搬家:)  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 20:21 | DC
inline int Abs_bit(int iNum )
{
int out = iNum;
int temp = iNum;
temp = temp >> 31;

out = out ^ temp;
out = out - temp;

return out;
}

上面代码的步骤比下面这个还多,何来多此一举?

template<class T>
T abs_Normal(T tNum)
{
return tNum > 0.0 ? tNum : -tNum;
}  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 20:51 | SmartPtr
代码数量少, 并不代表其后执行的指令少; 当然,对于现在的编译器,我们有理由相信它会帮我们优化的很好,我不敢保证我的消除了if-else的代码会比其优化后的更好, 但至少我们知道了这其中优化有可能是这么做的。  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 21:35 | DC
其实我指的不是代码数量的问题。

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

就这个而言,对于正数,只需一个比较步骤就可返回,
对于负数,则需两个步骤:比较和取负值,就可返回。

对于比较和取负值的机器代码因该很小,
类似于一般计算,所以最终编译后相对CPU的total steps,
应该少于下面这个

inline int Abs_bit(int iNum )
{
int out = iNum;
int temp = iNum;
temp = temp >> 31;

out = out ^ temp;
out = out - temp;

return out;
}  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 21:52 | Corner Zhang
@DC
不一定的。具体的还得看在目标平台上的测试结果。
影响性能的因素不只是指令所占的cpu周期,在现代的cpu上由于超标量体系的引入,跳转指令会影响cpu的分支预测功能,从而使得cache hit rate又说下降。  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-05 22:30 | DC
@Corner Zhang
你说的还是有些道理,看来具体的结果只有在特定的平台上测试后才能知晓!
  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-09 19:15 | 橙子
这样的优化有意义吗?  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-17 19:09 | abware
感觉没有太大必要。
temp>>31 ,如果int类型不是占用4个字节呢?  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2007-07-17 21:13 | Corner Zhang
这样的研究、尝试是有意义的。
不过在实际项目中,还是产出可理解的代码为先。

原则:
Keep it work
Keep it work, and right
Keep it work、right and fast  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2008-05-04 14:35 | basilwang
支持一下  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2009-03-26 23:54 | polisan
优化是有意义的,流水线很怕分支预测,尤其是流水级数很大的情况下.  回复  更多评论
  
# re: 用位运算实现求绝对值-有效避开if-else判断
2012-05-25 14:58 | tttt
这样优化是有意义的,但是,做绝对值一般会用? : 操作符,这样其实不是 if else实现的(会用比较高效的位操作实现)

但是直接这样写abs的位操作比? :的通用操作还是会少用那么2,3个操作符,但意义不是特别大  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理