[C 语言深度分析] 您真的了解 C 语言中的位运算符吗？ 位和、位或、位异或）（代码示例 + 详细图解

文章目录

• 位操作符
• 按位与
• 按位或
• 按位异或
• 综合练习

• 练习题一
• 练习题二
• 练习题三
• 练习题四
• 练习题五
• 奇淫技巧一：`n & 1`
• 奇淫技巧二：`n & (-n)`
• 练习题六

位操作符

分为：

按位与： &，按二进制位与

按位或： |，按二进制位或

按位异或： ^，按二进制位异或

注：他们的操作数必须是整数

按位与

代码示例：

int main()
{
  int a = 3;
  int b = -5;
  
  int c = a & b;
  printf("%d\n", v);

  return 0;
}

运行结果：

为什么会得到这个结果呢？

按位与的规则： 两个都是1才是1，否则0

1、首先求出3和-5的补码

3的补码：0000 0011

-5的补码：1111 1011

a & b的计算方式是：a和b存在内存中的二进制的补码进行计算的

所以相与的结果为：

3的补码：00000011

-5的补码：11111011

相与结果：00000011

但是记住：计算中存储的是补码

所以我们得到的是相与过后的补码：00000011

再转换成原码：

补码：00000011

反码：00000011

原码：00000011

再把原码换算成十进制：00000011=3

这就是按位与的规则

按位或

代码示例：

int main()
{
  int a = 3;
  int b = -5;
  
  int c = a | b;
  printf("%d\n", c);

  return 0;
}

运行结果：

为什么会得到这个结果呢？

按位与的规则： 只要有1就是1，两个同时为0才为0

同样还是先拿出3和-5的补码

3的补码：00000011

-5的补码：11111011

相或结果：11111011

所以我们得到的是相或过后的补码：11111011

再转换成原码：

补码：11111011

反码：11111010

原码：10000101

再把原码换算成十进制：10000101=-5（符号位=1，所以要加负号）

按位异或

代码示例：

int main()
{
  int a = 3;
  int b = -5;
  
  int c = a ^ b;
  printf("%d\n", c);

  return 0;
}

运行结果：

为什么会得到这个结果呢？

按位异或的规则： 相同为0，相异为1

同样还是先拿出3和-5的补码

3的补码：00000011

-5的补码：11111011

相或结果：11111000

所以我们得到的是异或过后的补码：11111000

再转换成原码：

补码：11111000

反码：11110111

原码：10001000

再把原码换算成十进制：10001000=-8（符号位=1，所以要加负号）

综合练习

练习题一

1、写代码实现：交换两个变量(不能创建临时变量)

方法一：

int main()
{
  int a = 3;
  int b = 5;

  int c = 0;//临时变量
  printf("交换前: a=%d b=%d\n", a, b);

  c = a;
  a = b;
  b = c;

  printf("交换后: a=%d b=%d\n", a, b);

  return 0;
}

运行结果：

方法二：

int main()
{
  int a = 3;
  int b = 5;

  int c = 0;//临时变量
  printf("交换前: a=%d b=%d\n", a, b);

  a = a + b;
  b = a - b;
  a = a - b;
  printf("交换后: a=%d b=%d\n", a, b);

  return 0;
}

运行结果：

既然不让我们创建临时变量，那么用这样的方法不是也可以实现了吗？

但是这种方法有个弊端：

如果a和b存储的数字都很大，如果相加超出了**int(整型)**的范围呢？

方法三：异或

先来看个规律：

3 ^ 3 = 0

0 ^ 5 = 5

代码示例：

int main()
{
  int a = 3;
  int b = 5;

  int c = 0;//临时变量
  printf("交换前: a=%d b=%d\n", a, b);

  a = a ^ b;
  b = a ^ b;// a ^ b ^ b：b和b相异或结果为0；a和0相异或还是为a
  a = a ^ b;// a ^ b ^ a
  printf("交换后: a=%d b=%d\n", a, b);

  return 0;
}

运行结果：

代码剖析：

①：a = a ^ b;

②：b = a ^ b;

③：a = a ^ b;

在①中：把a异或b的值赋给a；

在②中：此时a是①中: a ^ b的结果；

所以②可以看成：b = a ^ b ^ b，b ^ b = 0，a ^ 0 = a

注意：a ^ 0中的a是原来的a = 3的值，所以把3赋值给等号左边的b

在③中： 此时a还是①中: a ^ b的结果；b相当于②的结果：a=3

所以③可以看成：a = a ^ b ^ a，a ^ a = 0, b ^ 0 = b

注意：b ^ 0中的b是原来的b = 5的值；所以把5赋值给等号左边的a

练习题二

数组nums包含从0到n的所有整数，但其中缺了一个。

请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

题解:

我们先不看这个顺序乱的数组,而是假设有一个顺序完整的数组

然后还需要知道^的一个特性:

a ^ a = 0

a ^ 0 = 0

异或具有交换律：a ^ b ^ c = c ^ a ^ b

图示：

那么我们把每个下标以及该下标对应的数字进行连续异或；

异或过程就是：0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 5 ^ 5 ^ 6 ^ 6 ^ 7；

我们上面已经说了相同的数字进行异或，结果是0,所以最后就是0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 0 ^ 0 ^ 7；

发现还是有相同的，继续上面步骤，结果就等于：4 ^ 7

运用上面的特性 相同异或为0，我们发现4就是我们需要的结果，但是这里还有个7，怎么办？再次 异或7；

有个小问题，7是什么？7是数组的长度

再比如：

0 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 等于 0

但是我们需要的结果是4，而4是什么？4就是数组长度

好了，现在我们回到练习题，练习题与现在顺序数组有什么区别呢??

对，区别就是顺序乱了！但是影响吗？不会，因为异或具有交换律

比如[0,4,1,2]

异或过程就是：0 ^ 0 ^ 1 ^ 4 ^ 2 ^ 1 ^ 3 ^ 2 ；

等价于： 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4

等于： 3 ^ 4

再给它异或长度4，就是我们求的3

代码示例：

int missingNumber(int* arr, int sz)
{
  int ret = 0;
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    ret = ret ^ i ^ arr[i];
  }
  return ret ^ sz;
}

int main()
{

  int arr[9] = { 9,6,4,2,3,5,7,0,1 };

  int sz = sizeof(arr) / sizeof(arr[0]);

  int a = missingNumber(arr, sz);

  printf("缺少的是:%d ", a);
  return 0;
}

运行结果：

练习题三

代码实现：求一个整数存储在内存中的二进制中1的个数

思路：计算机存储是补码，所以也就是求补码中有多少个1

5的补码为：00000101

4的补码为：00000100

把5和1相与，得到：00000100

所以5 & 4得到的结果就是：00000100，也就是4，抵消了数字5二进制的倒数第一个1

是不是明白了一点规律？

下面以数字251为例子