[C语言题解]《算法零基础100讲》(第16讲) 变量交换算法

• 概念定义
• 课后练习
• • 面试题 05.07. 配对交换

  交换变量，就是把两个数据的变量进行一次交换。如：a = 1，b = 2，交换后a = 2，b = 1。
对于交换的方法，可以看一下这篇博客变量交换

这道题较笨的思路就是先将其转化为二进制，然后进行奇偶位的交换，再将交换后的二进制数转化为十进制。
代码如下：

int Mypower(int x, int n){
    if(n == 0){
        return 1;
    }
    int v = Mypower(x, n / 2);
    return n % 2 == 0 ? v * v : x * v * v;
}

int exchangeBits(int num){
    int BinarySystem[32];
    int len = 0;
    //转换二进制
    while(num){
        int k = num % 2;
        num /= 2;
        BinarySystem[len++] = k;
    }
    if(len % 2){
        BinarySystem[len] = 0;
    }
    //交换奇偶位
    for(int i = 1; i <= len; i += 2){
        if(len % 2 == 0 && i == len){
            break;
        }
        int temp = BinarySystem[i];
        BinarySystem[i] = BinarySystem[i - 1];
        BinarySystem[i - 1] = temp;
    }
    int ret = 0;
    //转换十进制
    for(int i = 0; i <= len; i++){
        if(len % 2 == 0 && i == len){
            break;
        }
        ret += BinarySystem[i] * Mypower(2, i);
    }
    return ret;
}

另外一种算法的代码就十分简便，几行就能搞定，他是通过位运算进行的。
再此之前，我们需先知道两个比较特别的二进制数0xaaaaaaaa和0x55555555 。

0xaaaaaaaa = 10101010101010101010101010101010(奇数位为0，偶数位为1)
0x55555555 = 1010101010101010101010101010101 (奇数位为1，偶数为为0)

然后我们分别将num与0xaaaaaaaa和0x55555555进行按位与(&)计算，然后再分别进行<<1和>>1计算即可。
用这种方法做这道题前可以先看看190. 颠倒二进制位

代码如下：

#define EVEN_BIT_MASK 0x55555555
#define ODD_BIT_MASK 0xaaaaaaaa 

int exchangeBits(int num){
    return ((num & ODD_BIT_MASK) >> 1) | ((num & EVEN_BIT_MASK) << 1);
}