零、写在前面
这是打卡的第十六天，今天题目比较简单，我们直接上结果，主要知识点在
《算法零基础100讲》(第16讲) 变量交换算法https://blog.csdn.net/WhereIsHeroFrom/article/details/121155355
https://blog.csdn.net/WhereIsHeroFrom/article/details/121155355
一、主要知识点
1.加法变量交换
主要利用到的思想就是a + b - b = a; a + b - a = b;
void swap(int *a, int *b){ *a = *a + *b; *b = *a - *b; *a = *a - *b; }
2.位运算实现变量交换(补充知识点)
计算机内有一个神奇的操作叫做异或(^)，这个是底层硬件实现的，对应的真值表为
看出来什么规律了么？其实就几个字 同1 异0
这个有个好处是 这个是位运算，不会产生加法那样的溢出。同时有a^b^a = b;a^b^b = a;（可以对这四种输入进行验证）
void jiaohuan(int *a, int *b){ *a = *a ^ *b; //a赋值为a^b *b = *a ^ *b; //b赋值为a^b^b == a *a = *a ^ *b;//a赋值为a^b^a == b }
三条语句后面完全一样，但是结果不同，神奇不？
二、课后习题
面试题 16.01. 交换数字
面试题 16.01. 交换数字https://leetcode-cn.com/problems/swap-numbers-lcci/
https://leetcode-cn.com/problems/swap-numbers-lcci/
交换连个数字。没啥难度。。
主要思想
运用位运算直接交换就行了。
int* swapNumbers(int* numbers, int numbersSize, int* returnSize){ *returnSize = numbersSize; //返回数组大小为2 numbers[0] = numbers[0] ^ numbers[1];// a = a^b numbers[1] = numbers[0] ^ numbers[1];//b = a^b^b = a numbers[0] = numbers[0] ^ numbers[1];//a = a^b^a = b return numbers; }
结果分析
还是可以的。满意了，下一个
面试题 05.07. 配对交换
面试题 05.07. 配对交换https://leetcode-cn.com/problems/exchange-lcci/
https://leetcode-cn.com/problems/exchange-lcci/
将一个数字的奇数位和偶数位进行交换
主要思想
用ans吸收奇数位和偶数位，每次右移两位，迭代求解。
int exchangeBits(int num){ int ans = 0,i = 0; while(num){ ans += (num & 1) << 2*i+1; //偶数位左移2i+1位 ans += (num >> 1 & 1) << 2*i;//奇数位左移2i位完成交换 num >>= 2; //每次右移两位 i++; } return ans; }
结果分析
凑合凑合。
思路2
直接根据位运算取出来奇数位左移，偶数位右移一位相加得到结果。
int exchangeBits(int num){ return ((num & 0x55555555) << 1) + ((num & 0xAAAAAAAA) >> 1); }
三、今日总结
今天的难度不高，但是位运算还是很有意思的0.0
