用位运算实现求绝对值

整数的平均值

对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:

#define AVE(x,y) ((x)&(y))+(((x)^(y))>>1)

判断一个整数是不是2的幂

对于一个数 x >= 0,判断他是不是2的幂

#define POWER2(x) ((((x)&((x)-1))==0)&&((x)!=0))

不用temp交换两个整数 int x,y; swap(x,y) void swap(int &x , int &y) { x ^= y; y ^= x; x ^= y;

}

求浮点数的绝对值 double abs(double y) { double x = y; *(((int *) &x) + 1) &= 0x7fffffff; return x;

}

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

T abs_Normal(T tNum)

{

if(tNum > 0.0)

return tNum;

else

return -tNum;

}

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

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

大家可以看到第一个与最后一个数只有符号位不同,也就实现了求其绝对值。

整数的平均值

对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:

#define AVE(x,y) ((x)&(y))+(((x)^(y))>>1)

判断一个整数是不是2的幂

对于一个数 x >= 0,判断他是不是2的幂

#define POWER2(x) ((((x)&((x)-1))==0)&&((x)!=0))

不用temp交换两个整数 int x,y; swap(x,y) void swap(int &x , int &y) { x ^= y; y ^= x; x ^= y;

}

求浮点数的绝对值 double abs(double y) { double x = y; *(((int *) &x) + 1) &= 0x7fffffff; return x;

}

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

T abs_Normal(T tNum)

{

if(tNum > 0.0)

return tNum;

else

return -tNum;

}

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

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

大家可以看到第一个与最后一个数只有符号位不同,也就实现了求其绝对值。


相关文章

  • 长整数的加减运算
  • ******************* 实践教学 ******************* 兰州理工大学 技术工程学院 2013年春季学期 课程设计 题 目: 长整数的加减运算 专业班级:计算机科学与技术一班 姓 名: 郭利强 学 号: 11 ...查看


  • 运算放大器_参数详解
  • 运算放大器 参数详解 技术 2010-12-19 22:05:36 阅读80 评论0 字号:大中小 订阅 运算放大器(常简称为"运放")是具有很高放大倍数的电路单元.在实际电路中,通常结合反馈网络共同组成某种功能模块.由 ...查看


  • [有理数加法运算]说课稿
  • <有理数加法运算>说课稿 课题:有理数加法运算 尊敬的各位评委.老师大家好! 我是来自115初等教育一班的卓伟润!今天我要说课的内容是有理数加法运算! 下面我将从四个方面来阐述我对这节课的理解与教学设想: 说课人:卓伟润 一.教 ...查看


  • 有理数乘法说课稿 文档
  • "有理数的乘法"说课 张苏:清华附中 中学高级 我今天说课的内容是新人教版的七年级<数学>上册第一章第四节<有理数的乘法>第一课时.我将从教材和学情分析.教学目标.教学重点和难点.教学方法与学法指 ...查看


  • 第一章 有理数单元备课
  • 第一章 有理数 单元备课 七年级数学备课组 撰稿人:郑强 审稿人:蔡晓东 周锦华 教材分析 本章教材是在学生已学过整数和分数的基础上构建的,主要内容是有理数的有关概念及其运算.首先,从实例出发引入负数, 接着引进关于在理数的一些概念,在此基 ...查看


  • [有理数]集体备课
  • 人教版数学七年级上<有理数>集体备课 主备课人:陈开军 参与人; 陈林 王正伟 孙谢阳 一.通读单元教材 提出学习本单元至关重要的几个问题: (1)由于学生刚刚接触代数,对于负数绝对值的理解感到困难,常常出现符号错误 (2)有理 ...查看


  • 电工电子技术课程设计1
  • 景德镇陶瓷学院 电工电子技术课程设计任务书 目录 1. 总体方案与原理说明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 2. 运算放大器. . . . ...查看


  • 巧妙地移位运算
  • 恰当的移位运算总是能够让代码显得很简洁.很优雅,下面,就让我们来看一下编程中使用频率比较高的一些移位运算: 本程序在VS2010编译器下运行,VS2010中,int占4个字节(32位),下面程序也只针对int型变量(常量)进行考虑. Cpp ...查看


  • 广播电视大学[计算机组成形成性考核册]形考作业答案
  • 计算机组成原理A 形考作业一(参考答案) 一.选择题: 1.机器数_____中,零的表示形式是唯一的. A .原码 B .补码 C .移码 D .反码 答案:B ,C 2.某计算机字长16位,采用补码定点小数表示,符号位为1位,数值位为15 ...查看


热门内容