算法100讲第16天

跟着大哥学算法

今天的主题看来是位运算啊。朴实无华and看不懂
第一道题交换数字，这个位运算见过，直接就呈现了
交换数字

class Solution {
public:
    vector swapNumbers(vector& numbers) {
        numbers[0]=numbers[0]^numbers[1];
        numbers[1]=numbers[1]^numbers[0];
        numbers[0]=numbers[0]^numbers[1];
        return numbers;
    }
};

首先需要了解异或基本性质

可交换性：a ^ b = b ^ a
可结合性：a ^ b ^ c = (a ^ b) ^ c = a ^ (b^c)
自身进行异或运算值为零：a^a=0
与 0 异或时结果不变：a^0=a

有了这个基础后我们再来分析代码，数组两个元素设为a,b；

a = a ^ b;
b = b ^ a = b ^ a ^ b =b ^ b ^ a = 0 ^ a = a;
a = a ^ a = a ^ a ^ b = 0 ^ b = b;

然后就是第二题眼花缭乱的位运算，本人不太熟悉位运算，但我会二进制！！；
基本思路就是将十进制转换成二进制，注意数组位置反转，因为c++容器性的优秀，我依然放开手中被我按在地上的c，看了一眼站在地上的c++;
所以我开始用c++打代码了。。
我们要注意的是 5转换成二进制为101；
运算结果是10 = 1010，说明处理上对0101转变成1010，因此我们在处理二进制数组的过程中，如果数组长度为奇数位，我们就得再末尾加0（反转前！！）

class Solution {
public:
    int exchangeBits(int num) 
    {
    vectorans;
	int ret = 0;
	while (num / 2 != 0||num%2!=0)//前一个条件处理num>2 后一个条件处理 num<2
	{
		ans.push_back(num % 2);
		num /= 2;
	}	
	if (ans.size() % 2 != 0
	{
		ans.push_back(0);//奇数末尾加0
	}
    reverse(ans.begin(), ans.end());//反转了哦
	for (int i = 0; i < ans.size() - 1; i += 2)
	{
		swap(ans[i], ans[i + 1]);
	}
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++)
	{
		ret += ans[i] * pow(2, i);
	}
	return ret;
    }
};