首页 > 笔记 > 位运算技巧

位运算技巧

写一些常用的位运算的小技巧

其实就是一些简单的常数优化,但可以让程序简单易读,更有逼格

C/C++语言提供的位运算符有:

images

结果

images

初步了解以后,就开始学习一些小技巧吧

1、奇偶性判断

没学位运算前,我们这么写

要知道,上面的代码我们使用的是对2取余,如果操作数value是小数的话,还勉强行得通,但是value是一个上百万的大数,那么这就白白浪费了CPU的大量时间,程序的效率和性能就很差。我们知道任何数在计算机储存中都是以二进制储存的,细心的你就会发现在二进制的最小一位有个特点,为0就是偶数,为1就是奇数,按照这个原理我们根本没必要让CPU白白做那么多的工作,只要一步判断就可以了。接下来就让我们看看位运算的精妙之处!

那么我们的目的就是判断最小位是0还是1,可是我们怎么判断呢?我们要用位运算阿里判断,就是与或非。在上面的复习之中我们只说了位运算的计算方法,并没有说其用处。那么在这里我们用到的就是“与”!与运算特有的一个功能就是判断指定位上的值(0或1)。我们来看下面的表格(与运算)。

images

我们要注意一下这里的 操作数2 ,它只有最低位是1,其余位都是0,这就是关键所在,操作数1是随机值。我们看看结果只会有两种结果:0或1。这个结果就取决于操作数1的最低位,它为1时就为1,为0时就为0.

“那么我要判断的是第二位呢?”

好!那我们就把操作数2改为 00000010 那么结果就只会有 00000000 或 00000010 其结果取决于第二位。

有了这个基础那么我们来看看怎么用位运算判断奇偶性吧:

总结

使用a%2来判断奇偶性和a & 1是一样的作用,但是a & 1要快好多。

2、  判断n是否是2的正整数冪

所谓2的正整数冪就是指 2,4,8,16,32,64,128,256,512,1024,2018………….等数字,若何判断一个数是否是这样的数呢?我们看看不用位运算的计算方法:

在这个算法中,我们使用了一个循环。其原理非常简单就是一一的对比,但是其中还调用了数学函数库,效率大大降低。接下来我们讲讲怎样用位运算来判断。我们首先要研究一下这些数的特性,请看下表(与运算):

images

我们发现 n&(n-1) =  0  我们可以 用逻辑非 !(n&(n-1)) =  1 。那是不是这样就可以了呢,你会发现 !(0&(0-1)) =  1 但是 0并不是 2的正整数冪。我们可以用 逻辑与 !(n&(n-1)) &&  n  = 1;请看下面的代码:

3、获得int最大值(不码字了,累死了)

4、获得int最小值

5、获得long的最大值

6、乘2运算

7、除以2运算

8、乘2的m次方

9、除以2的m次方

10、直接交换两个数

11、取绝对值

12、求两个数的最小值

13、判断符号是否相同

14、对2的n次方取余

15、平均数

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×