即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

位操作

编程语言 YF_Li123 23℃ 0评论
位操作

1 最有效的计算一个数x乘以2的n次方的方法
虽然直接进行乘法操作符运算可以进行x乘以2的n次方,但该方法不是最优的,通过移位方法会比较高效,因为CPU直接支持位运算,效率最高。
x<
将一个数左移n位,相当于乘以了2的n次方。
例如:2<<3 相当于2*8=16



引申:如何快速求取一个整数x的7倍?
(x<<3)-x
相当于将此整数乘以8,然后再减去原值,就得到了x的7倍。



2 如何实现位操作求两个数的平均值
一般求解平均数的方法就是将两者相加再除以2。例如:(x+y)/2
当时上述方法会存在一个问题,当两个数比较大时,如两者的和大于了机器位数能够表示的最大值,可能会存在数据溢出的情况,而采用位运算方法就可以避免这一问题。
(x&y)+(x^y)>>1
x&y:表示的是取x与y二进制中都为“1”的所有位;
x^y:表示的是x与y中有一个为“1”的所有位,右移1位相当于执行除以2的运算。
这个表达式分为两部分:
第一部分是都为“1”的部分,因为相同,所以直接相加即可;
第二部分是x为“1”、y不为“1”以及y为“1”、x不为“1”的部分,两部分加起来再除以2,然后跟前面的相加就可以表示两者的平均数了。
例如:

#include 
using namespace std;
int main()
{
       int x = INT_MAX;
       int y = INT_MAX;
       cout << (x + y) / 2 << endl;
       cout << (x&y) + ((x^y) >> 1) << endl;
       return 0;
}
在32位机器上,运行结果为:
-1
2147483647



3 如何利用位运算计算数的绝对值
以x为负数为例。在计算机中,数字都是以补码的形式存放的,求负数的绝对值,应该是不管符号位,执行按位取反,末位加1操作即可
对于一个负数,将其右移31位后变成0xffffffff,而对于一个正数而言,右移31位则为0x00000000,而0xffffffff^x+x=-1。因为1011^1111=0100,任何数与1111异或,其实质都是把x的0和1进行颠倒计算。如果用变量y表示x的右移31位,则(x^y
)-y则表示的是x的绝对值。
#include 
using namespace std;

int MyAbs(int x)
{
 int y = x >> 31;
 return (x^y) - y;
}
int main()
{
 cout << MyAbs(2) << endl;
 cout << MyAbs(-2) << endl;
}
程序输出结果为:
2
2


















参考:何昊,叶向阳,窦浩.程序员面试笔试宝典(第2版)[M].北京:机械工业出版社,2014.12:89-90




转载请注明:CodingBlog » 位操作

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情