位运算之位标志

Author Avatar
呃哦 9月 20, 2020

位运算之位标志位运算就像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)