位运算之位标志
位运算之位标志位运算就像C语言的指针,易学难精。因此本文只是介绍自己掌握的一些小例子。
基本知识
且运算
即保留两个数字相同的二进制位
0000 1100
& 0001 1000
= 0000 1000
或运算
即保留两者所有的 1 二进制位
0000 1100
| 0001 1000
= 0001 1100
异或
即两者不一样的位为 1
0000 1100
^ 0001 1000
= 0001 0100
非运算
即对位取反
! 0000 1100
= 1111 0011
其他二进制知识如 补码,反码,原码就不介绍了,是对二进制运算的一种应用
栗子
标志位用途
场景:
某个字段需要具有多种标识场景。
比如电商场景下,一个商品可能支持多种支付方式,京东钱包,白条,花呗,微信,支付宝余额等五种可供选择。
那么商家端的前端需要提供多种支付方式,提供商家打勾支持,
而用户端前端可能需要根据支付方式,展示对应支付方式的图标选择。
解决方案
方案一
假设支付方式是一个枚举字段,那么五种支付方式的组合就有32种,光写这个枚举字段代码就够累死人了。
方案二
假设支付方式是一个数组字段,里面是商家打勾的组合支付方式,则是比较简单的,虽然丑了点,但容易理解,只是空间上的开销是比较大的,而且数据库查询运算也有点不方便。
方案三
在方案二的基础上,把数字的二进制位 作为对应的数组
位标志
我们可以把一个整数类型,假设8个位的情况下。字段的二进制如下:
0000 0000
那么支付方式对应如下的标志位:
以 js 代码举例,这样可以边看边打开浏览器console验证
let jdpay = 0b00000001 // 京东钱包 =》1
let baitiao = 0b00000010 // 京东白条 =》2
let huabei = 0b00000100 // 花呗 =》4
let alipay = 0b00001000 // 支付宝余额 =》8
let wechat = 0b00010000 // 微信 =》16
可以看到,每种支付方式,对应一个 bit。相当于我们使用这个整数类型字段作为长度为 8 的数组用,数组上每个元素代表一种支付方式。
或运算:
如上所述,我们需要提供支付方式给商家选择,我们用 method 变量作用商家的选择。
let method = 0 // 商家没有选择支付方式
method = method | jdpay // 商家打勾了京东钱包 method: 00000000 | 000000001 = 00000001
method |= alipay // 商家打勾了支付宝 method: 00000001 | 00001000 = 00001001
如上,通过或运算,我们可以把对应的支付方式赋值到最终的结果上
且运算:
如上所述,用户端的前端,需要根据商品支持的多种支付方式,提供相应的选择
// 由于商家打勾了京东钱包和支付宝,所以我们的支付方式 method 是 0000 1001
if (method & jdpay) { // 9 true, 支持
console.log("支持京东钱包")
}
if (method & baitiao) { // 0 false 不支持
console.log("支持白条")
}
// if ....
非运算:
扩展点,我们提供了 多选项的支付方式给商家选择,商家选择了,我们通过 或运算 赋值到支付方式上,但是商家选择又取消了呢,这就涉及到位的清除操作了。
假设商家取消了 支付宝余额 ,那么我们需要清除支付方式 0000 1001 上面的 0000 1000 标志位
首先,我们对 支付宝余额 标志位做按位取反操作
let clear_alipay = !alipay // clear_alipay: 1111 0111
这样就是一个熟悉的界面了, 我们对支付方式做 且运算
method = method & clear_alipay
// method: 0000 1001
// clear_alipay: 1111 0111
// &
// 0000 0001
很明显,我们清除了 支付宝余额 这种支付方式的标志位。
一步到位的做法:
method &= !alipay
方案对比:
方案一明显是最糟糕的做法。灵活性太低。
方案二是最容易理解业务代码,但不够简洁,方便。
方案三不好理解,但代码简洁性高,性能也会更好。
如 android sdk 中,有大量地方地方需要用到 Flag 标志,Google 便是采用这种位标志的方式,使得代码看起来简洁高效。
如我们在数据库中查询该字段,查询多种支付方式的支持情况。
方案一 自不必说,把想要查询的枚举值拿来过滤就行。
方案二 应该是 JSON 语法操作,但这段 JSON 的可读性和语法不是很好上手,依赖于具体的数据库工具,语法特性。比如 5.7 版本之前的mysql 不支持 JSON 运算。并且性能上需要解析JSON的耗费。
方案三 灵活度极高,例如查询支持京东钱包但不支持花呗
where (method & 1) and not (method & 4)
交换值
入门计算机原理的时候,我们就会接触到排序算法的实现,而排序少不了要交换两个位置数字的值。
简单的举例如下:
let a = 5
let b = 10
let temp = a
a = b
b = temp
而 异或 运算,会保留两个不一致的位,试想,一个数字如果异或自己,会是怎样呢,答案是0,因为异或左右两边数字的位一模一样。
那么,两个不一样的数字(a, b)异或,会保留他们差异的位(c),这时候再异或其中一个数字(a),会把上面(c)有关于该数字的位清除了。
那么,我们得到的就是另一个数字(b)了。
举例如此:
let a = 5
let b = 10
a = a ^ b
b = a ^ b
a = a ^ b
重复值
题目:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
利用 两次异或,可以清除重复值,因此我们可以直接将数组数字做异或,出现两次的数字会被两次异或清除掉,最后的结果则为只出现一次的数字。
代码如下:
python 比较简洁些
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(xor, nums)