注册

简单回顾位运算

前言


位运算其实是一个比较常用的操作,有的人可能说,并没有啊,我好像基本就没怎么用过位运算,但如果你经常看源码,你就会发现源码里面有很多位运算的操作,而且这些操作我个人觉得确实是有很意思,所以位运算很重要,平时用不多,也需要经常去回顾复习。


因为临时写的,有些源码的操作我不太记得是出自哪里了,如果以后碰到了,会在评论区进行补充。比如会有一些取反计算再取反回来的操作,比如左移和右移,我现在不太记得是出自哪里了,反正比较经典的。我的个人可能就记得用位运算来表示状态,因为我会经常用这个。


位运算基础


简单来回顾一下基础的计算,位运算会分为一元运算和二元运算。


一元有左移<<,右移>>,无符号右移动>>>和取反~


左移是是什么?比如 0010 左移动一位就变成 0100 (注意这里是二进制的表示),右移动就是 0100 变成 0010。 当然没这么简单啦,二进制也有表示正负值的标志位,右移之后,左边会补标志位的数。而无符号右移动是左边补0。也就是说正数的右移和无符号右移动的结果相同,而负数就不同了。这样说应该好理解吧?那思考一下为什么没有无符号左移


还是不好懂,没关系,我们讲慢些,假如8转成2进制是00001000

而-8就是先取反码,反码就是取反,所以8的反码是11110111,然后再用反码取补码,补码就是+1,所以这里得到补码1111000。即-8转成二进制是11111000

先看看我们对11111000取反码,得00000111,再取补码得00001000,看到从-8到8也是同样的操作。


然后我们看右移一位和无符号右移一位的效果。

-8的二进制11111000,右移一位是11111100,这是多少啊?我们可以用上面的计算看它的正数是多少,反码00000011,补码00000100,这是4吧,所以11111100是-4。

同理看无符号右移,得01111100,反码10000011,补码10000100,这是多少?2的7次方+4,所以是不同的。


取反就好理解了,取反就是逻辑非,比如0010取反就是1101


二元有与&&、或||、异或^


这些都好理解吧,与运算 1010 && 1001 = 1000 , 或运算 1010 || 1001 = 1010 , 异或 1010 ^ 1001 = 0011 ,这没什么好讲的,很基础。


位运算很简单?


一看,哎哟,真的简单,就这?1分钟学会了。学会?那会用吗?


没关系,我们来看一题算法:


一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。例如:


输入:


[1,4,1,6]

返回值:


[4,6]

明确说了,这题是用位运算,但是怎么做?


开发中位运算的使用


这个我因为临时写的,android源码里确实是有些比较经典的位运算使用场景,我现在不完全记得,只能先列举几个,其它的如果以后想起来,会在评论区中做补充。


用来表示状态

位运算可以用来表示状态,我之前也写过一篇文章 juejin.cn/post/715547… 差不多也是这个意思。


比如window的flags,看看它的定义


public static final int FLAG_LAYOUT_IN_SCREEN   = 0x00000100;
public static final int FLAG_LAYOUT_NO_LIMITS = 0x00000200;
public static final int FLAG_FULLSCREEN = 0x00000400;
public static final int FLAG_FORCE_NOT_FULLSCREEN = 0x00000800;
......

那他这样做有什么好处,他能一个变量表示多个维度的状态。比如FLAG_LAYOUT_IN_SCREEN|FLAG_LAYOUT_NO_LIMITS|FLAG_FULLSCREEN|FLAG_FORCE_NOT_FULLSCREEN就是 1111 (二进制表示)


如果你要判断这个window是不是同时设置了这4个flag,要怎么判断,就直接if(flags == 15)啊,多简单


但是如果你用多个变量存flag要怎么判断, if(isScreen && isNoLimits && usFullscreen && isForceNot),这样写就很难看,很不方便,我window的flag多着呢,难道你要排火车?


数组扩容

来看看ArrayList的扩容源码


private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

这里的int newCapacity = oldCapacity + (oldCapacity >> 1);就是阔人操作,这个右移是什么?看不懂也没关系,自己套一个数字进去算就知道了,是除2吧,那ArrayList的扩容就是旧容量的一半。


看着简单是吧?那有没有想过一个问题,他写这个代码,为什么不写oldCapacity/2,而写oldCapacity >> 1


那既然右移一位 >> 1 是除2,那左移一位 << 1 是什么操作呢?是什么计算呢?


总结


我这里确实是很久没有用位运算,所以需要复习一下。这个东西对开发来说很重要,比如你是开发应用层的,你觉得这个是底层用到的,你用不到,并不是这样。就拿那个表示状态的来说,自从我看到源码用这一招之后,只要有合适的场景,我也会这样用。


不管是做数学运算,还是逻辑运算,位运算都能适用,它是很简单就能学会,但是学会用,那就是另外一回事,当然不是说看完我这篇文章就开始瞎用,能在合适的场合去使用,那效果十分的好,用不上也没关系,至少要有个意识,这样不管在看源码还是其它时候,都是能帮到你的。


作者:流浪汉kylin
链接:https://juejin.cn/post/7205508171524128828
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

0 个评论

要回复文章请先登录注册