C 实现零空间开销交换两个数的值

C 实现的不引入新变量交换两数的方法.

最近看到一个问题感觉很有意思:

“如何在不申请临时变量的情况下交换两个数的值?”

思考许久没有思路,查阅一番发现方法不少,在这里介绍四种方法:

方法一

1
2
3
4
5
6
void swap(int *a, int *b)
{
*a = *a ^ *b;
*b = *b ^ *a;
*a = *a ^ *b;
}

提示:异或运算符 ^ 也称 XOR 运算符,它的规则是若参加运算的两个二进位同号,则结果为 0 (假);异号为 1(真)。即 0 ^ 0 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 1 ^ 1 = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
计算实例:

a = 3 -> 0000 0011
b = 4 -> 0000 0100

step1:
a = a ^ b
-> 0000 0011
^ 0000 0100
= 0000 0111 -> 7

step2:
b = b ^ a
-> 0000 0100
^ 0000 0111
= 0000 0011 -> 3

step3:
a = a ^ b
-> 0000 0111
^ 0000 0011
= 0000 0100 -> 4

方法二

1
2
3
4
5
6
void swap(int *p, int *q)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}

方法三

1
2
3
4
void swap(int *p, int *q)
{
*a = *a + *b - (*b = *a);
}

C/C++ 中 ( A = B ) 返回得到是赋值号( = )的左面的值

1
2
3
4
5
6
7
8
9
10
11
计算实例:

a = 3;
b = 4;

a = 3 + 4 - (b = 3)
= 3 + 4 - 3
= 4;

-> a = 4;
-> b = 3;

方法四

1
2
3
4
void swap(int *p, int *q)
{
*a ^= *b ^= *a ^= *b;
}
1
2
3
4
5
6
7
8
9
10
11
计算实例:

a = 3;
b = 4;

a = 3 ^ 4 = 7;
b = 4 ^ 7 = 3;
a = 7 ^ 3 = 4;

-> a = 4;
-> b = 3;

参考文献


C 实现零空间开销交换两个数的值
https://www.frytea.com/post/20211103144831.html
作者
Tianlun Song
发布于
2021年11月3日
更新于
2024年6月10日
许可协议