必知必会位运算技巧手册

元数据

作者: labuladong
标题: 必知必会位运算技巧手册
分类: #dotnet
地址: https://mp.weixin.qq.com/s/4vHfaNnn1OpWQJcsssWWdQ

笔记

利用或操作|和空格将英文字符转换为小写 跳转

('a' | ' ') = 'a'
('A' | ' ') = 'a'

利用与操作&和下划线将英文字符转换为大写 跳转

('b' & '_') = 'B'
('B' & '_') = 'B'

利用异或操作^和空格进行英文字符大小写互换 跳转

('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

不用临时变量交换两个数 跳转

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1

加一 跳转

int n = 1;
n = -~n;
// 现在 n = 2

减一 跳转

int n = 2;
n = ~-n;
// 现在 n = 1

判断两个数是否异号 跳转

int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false

index & (arr.length - 1) 的运用 跳转

取模做法:

int[] arr = {1,2,3,4};
int index = 0;
while (true) {
	// 在环形数组中转圈
	print(arr[index % arr.length]);
	index++;
}
// 输出：1,2,3,4,1,2,3,4,1,2,3,4...

位运算:

int[] arr = {1,2,3,4};
int index = 0;
while (true) {
	// 在环形数组中转圈
	print(arr[index & (arr.length - 1)]);
	index++;
}
// 输出：1,2,3,4,1,2,3,4,1,2,3,4...
n & (n-1) 的运用 跳转

n & (n-1)这个操作在算法中比较常见，作用是消除数字n的二进制表示中的最后一个 1
img

计算汉明权重 跳转

这是力扣第 191 题「位 1 的个数」：
就是让你返回n的二进制表示中有几个 1。因为n & (n - 1)可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到n变成 0 为止

int hammingWeight(int n) {
	int res = 0;
	while (n != 0) {
		n = n & (n - 1);
		res++;
	}
	return res;
}
判断一个数是不是 2 的指数 跳转

力扣第 231 题「2 的幂」就是这个问题。
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1

2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100

如果使用n & (n-1)的技巧就很简单了

boolean isPowerOfTwo(int n) {
	if (n <= 0) return false;
	return (n & (n - 1)) == 0;
}
查找只出现一次的元素 跳转

这是力扣第 136 题「只出现一次的数字」
对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素

int singleNumber(int[] nums) {
	int res = 0;
	for (int n : nums) {
		res ^= n;
	}
	return res;
}