位运算实用技巧

本篇介绍一些位运算中的实用技巧

1. 大小写转换

与空格字符进行或操作，可以将大小写字母均转换为小写字母

char c = 'a';
c |= ' ';

与下划线进行与操作，可以将大小写字母均转换为大写字母

char c = 'A';
c &= '_';

与空格字符进行异或操作，可以进行大小写转换

char c = 'a';
c ^= ' ';

2. 交换两个数

ixt a = 1, b = 2;
a ^= b, b ^= a, a ^= b;

3. 判断两个数是否异号

避免用乘法进行判断有可能发生溢出情况，而在位运算里只需要判断符号位是否相同即可。

ixt a = 2, b = -3;
// true 表示异号，false 表示同号
bool f = (a ^ b < 0);

4. 消除 $x$ 的二进制表示中最右边的 $1$

0 0 1 1 0 1 0 -> x 0 0 1 1 0 0 0 -> x & x - 1

ixt x = 6;
x = x & x - 1; // 位运算优先级小于加减运算符，大于关系运算符

此操作实用性非常强！可以应用于以下问题：

• 获取一个数在二进制表示下 $1$ 的个数
• 判断一个数是否为 $2$ 的幂
• 计算两个整数 $a, b$ 在二进制下相互转换需要改变多少个比特位

5. 获取 $x$ 二进制表示中最右边的 $1$

0 0 1 1 0 1 0 得出 10

ixt lowbit(ixt x) {
	returx x & -x;
}

ixt x = 26;
cout << lowbit(x) << '\n';

6. 获取二进制表示中 $1$ 的个数

这也是汉明权重问题。这里介绍以下几种方法：

• 利用第4条，每次消除一个 $1$，直到变为零为止。
• 转换为字符串进行遍历
• 利用第5条，每次减去最右边 $1$ 的影响

int get1(int x) {
	int cnt = 0;
	while(x) {
		x = x & x - 1;
		cnt++;
	}
	return cnt;
}

int get2(int x) {
	int cnt = 0;
	while(x) {
		x -= x & -x;
		cnt++;
	}
	return cnt;
}

7. 判断一个数是否为 $2$ 的幂

方法：由于任意一个 $2$ 的幂在二进制表示中有且仅有一位为 $1$，因此可以利用第四条消除这个 $1$，判断消除之后是否为 $0$ 即可。注意需要对 $0$ 进行特判

bool ok(int x) {
	if(x <= 0) return false;
	return (x & x - 1) == 0;
}

8. 一个数在二进制下转化为另一个数需要改变的位数

• 如果两个数在某一位不同则需要修改
• 就是判断有多少位是不同的
• 因此，可以借助异或，异或之后有多少个 $1$ 就需要改变多少位

int f(int a, int b) {
	int x = a ^ b;
	int cnt = 0;
	while(x) {
		x = x & x - 1;
		cnt++;
	}
	return cnt;
}

9. 把某一位变为1

在这一位与1或即可。