用位运算实现求绝对值.docxVIP

??整数的平均值对于两个整数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;}一般情况下，如果要我们写一个求绝对值的函数，我们的实现很有可能会是这样：templateclass?TT?abs_Normal(T?tNum){????if(tNum??0.0)????????return?tNum;????else????????return?-tNum;}也就是说我们会用到一个if-else判断来决定是否反转符号位。在3D游戏软件，或一些对性能要求比较高的底层系统中，当大规模的求绝对值时，这个if-else结构会带来性能上的损失，那么，如何来消除if-else结构呢？或许会有人说，我们可以用三元操作符啊:templateclass?TT?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相与而将符号位置0inline?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位，再逻辑右移一位将符号位置0inline?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