以下全部用c举例
int a[10] = {0,1,2,3,4,5,6,7,8,9};
我们想交换数组a中第5个和第6个的值,通常想到的做法是创建一个中间变量作为中转,如下:
#include
void swap2num(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int main() {
int a[10] = {0,1,2,3,4,5,6,7,8,9};
printf("before swap:a4=%d, a5=%dn", a[4], a[5]);
swap2num(a, 4, 5);
printf("after swap:a4=%d, a5=%d", a[4], a[5]);
return 0;
}
有种略显高明的做法,使用三次异或就可以实现同样的交换效果,如下:
#include
void swap2num(int a服务器托管网[], int i, int j) {
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
}
int main() {
int a[10] = {0,1,2,3,4,5,6,7,8,9};
printf("before swap:a4=%d, a5=%dn", a[4], a[5]);
swap2num(a, 4, 5);
printf("after swap:a4=%d, a5=%d", a[4], a[5]);
return 0;
}
解读:
先谈谈异或的规则:
(1)相同为0,相异为1
(2) 异或满足交换律,即 a ^ b ^ c = a ^ ( b ^ c) = a ^ c ^ b
(3) N ^ N = 0, N ^ 0 = N;
那么,假设 a[i] = 甲, a[j] = 乙, 则第一次执行完 “a[i] = a[i] ^ a[j];”后:
a[i] = 甲 ^ 乙;
a[j] = 乙;
执行完 “a[j] = a[i] ^ a[j];” 后:
a[i] = 甲 ^ 乙;
a[j] =甲 ^ 乙 ^ 乙;
根据异或规则得到: a[j] = 甲 ^ (乙 ^ 乙) = 甲 ^ 0 = 甲; a[i] = 甲 ^ 乙;
再次执行完 “a[i] = a[i] ^ a[j];” 后:
a[i] = 甲 ^ 乙 ^ 甲 = 乙, a[j] = 甲;
至此,a[i]和a[j]完成交换;
深度解读:
异或操作又叫做 “无进位相加“,即相加的两个数的各个位相加但不产生进位;
然后我们从信息的角度再来审视一下代码,发现这其实是信息的叠加和分离,在这种思想下,我们可以用普通的加法也可以实现交换,当然是在不产生进位溢出的情况下,进位溢出意味着信息的丢失! (乘除也可以的,在乘积没有溢出的情况下)
#include
void swap2num(int a[], int i, int j) {
//本函数的局限性--和不能产生进位溢出,所以这只是为了举例说明,现实中可不能这样写
a[i] = a[i] + a[j]; // 以和的形式将两个数字叠加在一起,信息的叠加
a[j] = a[i] - a[j]; //和减去其中一个必然得到另一个,信息的分离
a[i] = a[i] - a[j]; //和减去其中一个必然得到另一个,信息的分离
}
int main() {
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
printf("before swap:a4=%d, a5=%dn", a[4], a[5]);
swap2num(a, 4, 5);
printf("after swap:a4=%d, a5=%d", a[4], a[5]);
return 0;
}
同理,上面的异或交换也是信息的叠加和分离,但它的操作不产生进位,也就不会有溢出导致的信息丢失问题;
但是! 这个异或交换有个巨大的隐患!!即 i 和 j不能相等, 即不能让数组中相同位置的数进行交换,会发生什么问题呢?
记得上面的异或规则吗? N ^ N = 0,任意数和自己异或都等于0, 所以经历了异或交换以后,a[i] = 0, a[j] = 5, 完蛋了,没交换成功反而还让其中一个等于0了!
当然可以略作修改,做个判断,如下:
#include
void swap2num(int a[], int i, int j) {
if (i == j)return; //i等于j,即同一个位置交换时直接返回
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
}
int main() {
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
printf("before swap:a4=%d, a5=%dn", a[4], a[5]);
swap2num(a, 4, 4);
printf("after swap:a4=%d, a5=%d", a[4], a[5]);
return 0;
}
plus:
linux源码中swap的实现方法,它就是用新建一个变量中转的方式实现的交换:
#define swap(a, b)
do { typeof(a) __tmp = (a); (a) = (b); (b) = __t服务器托管网mp; } while (0)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 应用报错:java.lang.OutOfMemoryError: unable to create new native thread
上个月生产环境忽然出现部分交易处理缓慢甚至超时,查看对应应用日志发现一直在刷报错日志,报错信息如下 java.lang.OutOfMemoryError: unable to create new native thread 从报错上来看是说不能创建本地线程了…