Fork me on GitHub
ookamiAntD's Blog

位运算以及常用场景

Preface

位运算以及常用场景(装X)…

符号解释

位运算符描述运算规则
<<左移各二进制全部左移, 高位丢弃, 低位补0
>>右移各二进制全部右移, 正数高位补0, 附属高位补1
>>>无符号右移各二进制全部右移, 高位补0
&位与两个为1, 结果才为1
``位或两个为0, 结果才为0
~位非1变0, 0变1
^位异或两个相同为0, 相异为1

基础运用

获取或修改a的第k位

获取第k位: a >> k & 1

将第k位清0: a = a & ~(1 << k)

将第k为设置为1: a = a | (1 << k)

判断第k位是否是1

1
2
int flag = 1 << k
return (a & flag) == flag

1
(a >> k & 1) == 1

乘除运算

a * (2 ^ n)a / (2 ^ n) 可以使用左移或右移代替.

判断奇偶数

偶数的第一位是0, 可是使用 (a & 1) == 0 来代替 a % 2 == 0 判断是否为偶数.

判断a是否2的幂

1
(a != 0) && (a & (a - 1)) == 0

交换两个数

位异或有下面几个特性:

  • a ^ a = 0
  • a ^ 0 = a
  • (a ^ b) ^ c = a ^ (b ^ c)

a 与 b 交换位置可以这样实现:

1
2
3
a ^= b;
b ^= a;
a ^= b;

上面三步可以这样理解:

1
2
3
a = a ^ b;
b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a;
a = a ^ b = (a ^ b) ^ b = (a ^ a) ^ b = b ^ 0 = b;

求余

a % (2^n) 等价于 a & (2^n - 1)

求相反数

~a + 1

求平均值

(x & y) + ((x ^ y) >> 1)

综合运用

多状态位

将多个开关合并到一个二进制中, 主要用到上面基础运用中的 获取或修改a的第k位判断第k位是否是1.

1
2
3
4
5
6
7
8
9
10
11
12
13
int DISPLAY_H5 = 1 << 0;
int DISPLAY_MINI_PROGRAM = 1 << 1;
int DISPLAY_APP = 1 << 2;

int displayAllInOne;

// 生成所有开关二进制
displayAllInOne |= displayH5 ? DISPLAY_H5 : 0;
displayAllInOne |= displayMiniProgram ? DISPLAY_MINI_PROGRAM : 0;
displayAllInOne |= displayApp ? DISPLAY_APP : 0;

// 判断某个端是否展示(其他类似)
(displayAllInOne & DISPLAY_H5) == DISPLAY_H5

加密

主要运用到位异或的特性:

1
A ^ B = C => C ^ A = B => C ^ B = A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
String raw = "yangbingdong";
String key = "thisIsPasswo";

char[] xChars = raw.toCharArray();
char[] yChars = key.toCharArray();
char[] encodeChars = new char[yChars.length];
for (int i = 0; i < xChars.length; i++) {
encodeChars[i] = (char)(xChars[i] ^ yChars[i]);
}

System.out.println(String.copyValueOf(encodeChars));
char[] decodeChars = new char[yChars.length];
for (int i = 0; i < encodeChars.length; i++) {
decodeChars[i] = (char)(encodeChars[i] ^ yChars[i]);
}
System.out.println(String.copyValueOf(decodeChars));

高低位交换

34520的二进制表示: 10000110 11011000.

将其高8位与低8位进行交换, 得到一个新的二进制数: 11011000 10000110, 其十进制为55430.

假设下面a是16位二进制(实际上int是32位), a >> 8 将高8位移动到低8位, 高位补0. 将 a << 8 & 0xff00 将a左移8位地位补0并获取前16位:

1
2
int a =  34520;
int exchange = (a << 8 & 0xff00) | (a >> 8);

生成第一个大于a的满足2^n的数

这个场景经典运用是在 HashMap 中, 因为 HashMap 通过 key 计算 hash 桶的位置就是用到上面的位移求余, 所以 hash 桶的数量必须2^n.

1
2
3
4
5
6
7
8
9
public static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
---------------- The End ----------------
ookamiAntD wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
谢谢大爷~

Author:ookamiAntD Yang
Link:http://yangbingdong.com/2020/bit-operation/
Contact:yangbingdong1994@gmail.com
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
转载请注明出处,谢谢!

分享到: