【算法】位运算——常见位运算基础操作总结

位运算基础操作总结，包括基础运算符 + 修改某位bit位

目录

• 1.基础位运算符
• 2.按位基础操作
• • 1.给一个数 n，确定其二进制的第 x 位是 0/1
  • 2.将一个数 n 的二进制标识的第 x 位修改成 1
  • 3.将一个数 n 的二进制标识的第 x 位修改成 0
  • 4.提取一个数 n 二进制中最右侧的 1 (除了最右侧的1，即其他位都置为0)
  • 5.干掉一个数 n 二进制标识中最右侧的 1
  • 6.按位异或^的运算律
• 3.相关思想及运算符优先级问题
• • 位图思想
  • 优先级

1.基础位运算符

基础位运算符有6个，即<<,>>,~,&,|,^

• << 左移
• >> 右移
• ~ 按位取反：全部bit位按位取反(0->1,1->0)，包括符号位
• & 按位与：有0为0
• | 按位或：有1为1
• ^ 按位异或：异为1，同为0 或 (无进位相加)

2.按位基础操作

按位基础操作总计有6点，下面依次进行叙述。

1.给一个数 n，确定其二进制的第 x 位是 0/1

公式：ret = (n >> x) & 1
原理：利用与运算，任何数与1进行按位与都是其数本身，任何数与0按位与都是0
图解：

代码示例：

//1.给一个数 n，确定其二进制的第 x 位是 0/1
void test1()
{
	int n = 106;// 0 1 1 0 1 0 1 0
	int x = 0;

	for (int i = 0; i < 8; i++)
	{
		x = i;
		int ret = (n >> x) & 1;
		printf("n的第%d位(从右往左数)是%d\n", x, ret);
	}
}

效果展示：

2.将一个数 n 的二进制标识的第 x 位修改成 1

公式：ret = n | (1 << x)
原理：利用或运算，0或上任何数都是原数，1或上任何数都为1
图解：

代码示例：

//2.将一个数 n 的二进制标识的第 x 位修改成 1
void test2()
{
	int n = 106;// 0 1 1 0 1 0 1 0
	int x = 0;

	for (int i = 0; i < 8; i++)
	{
		x = i;
		int ret = n | (1 << x);
		printf("将n的第%d位修改为1是%d\n", x, ret);
	}
}

效果展示：

3.将一个数 n 的二进制标识的第 x 位修改成 0

公式：ret = n & ~(1 << x)
原理：利用与运算，任何数与1进行按位与都是其数本身，任何数与0按位与都是0
图解：

代码示例：

//3.将一个数 n 的二进制标识的第 x 位修改成 0
void test3()
{
	int n = 106;// 0 1 1 0 1 0 1 0
	int x = 0;

	for (int i = 0; i < 8; i++)
	{
		x = i;
		int ret = n & (~(1 << x));
		printf("将n的第%d位修改为0是%d\n", x, ret);
	}
}

效果展示：

4.提取一个数 n 二进制中最右侧的 1 (除了最右侧的1，即其他位都置为0)

公式：n & (-n)
原理：先利用 -n全部取反且+1，此时-n与n的相同二进制位为最右侧的1及其右边的二进制位(但是只有最右侧的1是1，最右侧的右侧二进制都是0)。再利用按位与不同为0，同1为1。
图解：

代码示例：

//4.提取一个数 n 二进制中最右侧的 1(除了最右侧的1，即其他位都置为0)
void test4()
{
	int n = 106;// 0 1 1 0 1 0 1 0

	int ret = n & (-n);
	printf("提取最右侧二进制位后的数值为：%d\n", ret);
}

效果展示：

5.干掉一个数 n 二进制标识中最右侧的 1

公式：ret = n & (n-1)
原理：n-1与n的区别在于最右侧的1因为被“借位”不见了，其最右1的右边均不同(总之有0)，此时再利用按位与的同为原数，不同为0的特点即可。
图解：

代码示例：

//5.干掉一个数 n 二进制标识中最右侧的 1
void test5()
{
	int n = 106;// 0 1 1 0 1 0 1 0

	int ret = n & (n - 1);
	printf("将n的最右侧二进制位1修改为0是：%d\n", ret);
}

效果展示：

6.按位异或^的运算律

我们知道：对于按位异或而言，异为1，同为0
那也就是说，1 ^ 0 = 1 ; 0 ^ 0 = 0 ; 1 ^ 1 = 1;
我们将这个规律推广到数的层级(8个比特位)，该规律依旧存在于数的层级上。
即：
1.num ^ 0 = num ;
2.num ^ num = 0;
3.a ^ b ^c = a ^ c ^ b;

3.相关思想及运算符优先级问题

位图思想

与哈希表相类似，只不过里面存的值变成了单个bite位，这个并不在这里进行详细解释。

优先级

运算符优先级不一样，可能会导致符号运算顺序不满足我们预期。
解决：不确定就加括号

当然，我下面也提供了符号优先级表格，可以了解一下常用的几个：

EOF