计算机说到底就是 0 和 1,所有的数在内存中都是以二进制的形式储存的。
而位操作,或者说位运算,就是直接对内存中的二进制位进行操作。
位运算可以说是我们的基本功,今天这篇文章就从以下角度和大家一起玩转位运算。
当然了,位运算还有很多奇技淫巧,如果大家还想看进阶篇,记得给我点赞或者留言告诉我哦~
位运算的作用
位运算可能并不会降低复杂度的等级,但是可以把复杂度前面的系数降下来。
举个例子。
大家都知道堆,或者叫优先队列,一般来说是用完全二叉树来实现的,叫做二叉堆。
最小堆
二叉堆插入、删除元素的时间复杂度都是 O(logn),如果这个不清楚的同学赶紧在公众号内回复「堆」复习一下,或者点击这里~
但是有另一种堆,它能够做到 O(1) 的时间插入元素,O(logn) 的时间删除元素,我在堆这篇文章里也提到过,就是斐波那契堆。
但为什么不用呢?
就是因为 O(1) 前面的系数非常大。
我们说 O(logn) 比 O(1) 好,是有个条件的,那就是 n 非常非常大的情况下,但是实际上,如果 n 是在 int 范围内,那么取个 log 也不过就是 32 了,反而这个 O(1) 的时间复杂度可能系数达到几百几千。
一般来说实际应用中时间的测量并不是像我们做算法题时用时间复杂度这么简单,有的时候就需要你把两个算法都实现出来,去跑去测量它的时间,才能决定哪个好。
那么二进制一次能够作用于 32 位上(假设是一个 int),如果数据表示的巧妙,这完全可以优化 32 倍,多用几个 int 就多优化了好几个 32 倍,不香吗?
除了优化时间,还可以优化空间。
比如在网站发布新版本时,一般都会附上支持该版本的浏览器列表,不然有些老掉牙的浏览器看不到我的新功能还算我的锅么?
那么怎么有效的表示这个浏览器列表呢?
全世界所有浏览器都有个国际标准编号,这里我就简单假设一下:
那么我们就可以用一个 int 表示是否支持这些浏览器的状态,如果这个浏览器能用,那么这一位上就设为 1,不能用就设为 0,这样用一个 int 就能表示 32 个网站。
那么国内的某个网站可以表示为:
所以位操作在很多代码里都很常用,比如网络协议、操作系统等等。
这就是位运算的两大优势,接下来我们说说具体的知识点。
原码 反码 补码
数字有正有负,Java 中用的是 signed type,就是有正有负的。
虽然在 Java 8 之后,也用了个工具来实现 unsigned type,但是其实底层实现是没有的。
二进制最左边的一位是符号位,
对了,最左边的一位英文叫做 most significant bit,别说错了。。。
正数
正数的原码反码补码相同,没啥好说的。
比如:
负数:
原码:把相应的正数的符号位设为 1。
反码 ones' complement:
符号位是 1,其余位取反。
补码 two's complement :
反码 + 1。
而计算机中真正用来存储数据的是用补码。
这里稍微注意下反码和补码的英文,ones' 的这个 ' 在后面,two's 的这个 ' 在中间。。
为什么计算机要用补码来存储数据呢?
可能有同学会说正零负零的原因,但这只是表面现象。
实际上通过补码这样精巧的设计,计算机做加减乘除运算就不用考虑符号,就可以让硬件里 CPU 的设计变得异常简单。
最初计算机只有加法器没有减法器,所以它用这么一种方式用加法完成了减法。
int 的最大值是多少?
正是因为最左边一位是符号位,所以正数的表示就少了一位能用的,那么 int 的最大值就是:
0111111...11 (31 ones) = 2^31 - 1 = 2147483647
7 种位运算
运算符 | 中文 | 英文 | 运算规则 |
---|---|---|---|
<< | 左移 | left shift | 右边补充 0 |
>> | 右移 | signed right shift | 左边补充符号位 |
>>> | 无符号右移 | unsighed right shift | Java 特有,左边补充 0 |
~ | 位非 | NOT | 每位取反 |
& | 位与 | bitwise AND | 每位做与操作,都是 1 则为 1,否则为 0 |
I | 位或 | OR | 每一位做或操作,有 1 则为 1,否则为 0 |
^ | 异或 | XOR | 相同为 0,不同为 1 |
要注意的是前 4 个运算符是对 1 个数进行操作的,且操作完成后这个数本身的值不变(与 i++ 不同);后 3 个操作是两个数的运算。
我们一一来看。
为了书写方便,下面的数值虽然是 int 类型,但我只写 8 位,大家都能理解的噢!
1. <<
左移操作就是把这些零啊壹啊的整体往左移动 n 位,右边缺的就补充 0。
诶,大家发现没有,左移 1 位之后这个数相当于乘2。
但是这只适用于左边溢出的高位中不包含 1 时。
如果把 1 扔了,那就肯定不是 2 倍了嘛。
2. >>
右移操作就是整体往右移动 n 位,左边缺的补充符号位。
同理,正数右移操作的效果是这个数除以 2。
如果是负数呢?
因为 Java 是向零取整,所以奇数时会有问题,就不再是除以 2 的结果。
总结一下,
3. >>>
和 >> 的不同之处在于,这个的左边空缺的不论正负,一律补充 0。
所以对于正数来说,和 >> 的效果一样,但是负数不同。
4. ~
取反操作,就是每一位取反,1变成0,0变成1。
5. &
这个符号其实和逻辑与运算 && 意思一样,只不过作用在每一位上。
对于每一位来说,两个数都是真,则为真,否则为假。
6. |
同理,和逻辑或运算 || 意思一样,只不过作用在每一位上。
对于每一位来说,但凡有个真的就是真,否则为假。
7. ^
最后一个异或操作,相同为 0,不同为 1。
好啦,以上就是位运算的基本操作了,由这些运算做些巧妙的组合还可以得到很多有趣的结果,大家喜欢的话记得点赞评论哦~
本文转载自微信公众号「码农田小齐」,可以通过以下二维码关注。转载本文请联系码农田小齐公众号。
科技会使城市变得智能吗?您可能会想阅读大多数有关智慧城市的文章和书籍。这似乎...
医药卫生机构管理数字化主要是指医药卫生机构因行政管理、业务流程管理等需求而...
『看看论文』是一系列分析计算机和软件工程领域论文的文章,我们在这个系列的每...
早安!8月份又悄咪咪的从指缝溜走了,我们已迎来全新的9月,今天是全国大中小学...
早上好,2020年已成为历史,让我们展望2021,继续前行。愿 所求皆如愿,所行化坦...
缓存是什么?(没听说过你可以走了) 哪些场景需要用到缓存呢? 缓存可以分类吗? 缓...
云、本地数据中心、SaaS、多样化商业服务、多供应商和劳动力迁移不断涌现,这就...
最近,我在YouTube上看了一个非常出色的开发人员的视频。 它的标题是无服务器毫...
2021年3月1日,中国北京-北京忆恒创源科技有限公司(Memblaze)今天宣布完成数亿元...
在疫情改变我们的工作方式之前,对员工的支持主要是提供现代化的办公空间、职业...