上海网站建设网站游戏,汕头网站排名推广,网站欣赏公司网站案例,淮安企业网站建设以下全部用c举例
int a[10] {0,1,2,3,4,5,6,7,8,9};我们想交换数组a中第5个和第6个的值#xff0c;通常想到的做法是创建一个中间变量作为中转#xff0c;如下#xff1a;
#includestdio.hvoid swap2num(int a[], int i, int j) {int tmp a[i];a[i] a[j];a[j] …以下全部用c举例
int a[10] {0,1,2,3,4,5,6,7,8,9};我们想交换数组a中第5个和第6个的值通常想到的做法是创建一个中间变量作为中转如下
#includestdio.hvoid 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%d\n, a[4], a[5]);swap2num(a, 4, 5);printf(after swap:a4%d, a5%d, a[4], a[5]);return 0;
}有种略显高明的做法使用三次异或就可以实现同样的交换效果如下:
#includestdio.hvoid 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%d\n, 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]完成交换
深度解读
异或操作又叫做 “无进位相加“即相加的两个数的各个位相加但不产生进位 然后我们从信息的角度再来审视一下代码发现这其实是信息的叠加和分离在这种思想下我们可以用普通的加法也可以实现交换当然是在不产生进位溢出的情况下进位溢出意味着信息的丢失 (乘除也可以的,在乘积没有溢出的情况下)
#includestdio.hvoid 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%d\n, 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了 当然可以略作修改做个判断如下
#includestdio.hvoid 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%d\n, 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) __tmp; } while (0)
