[算法很美](位运算_5)整数的奇偶位互换

5、将一个整数的二进制表达中的奇偶位互换

这题什么意思呢?就是比如一个整数9,二进制表达位1001,如下图所示:

img

如果我们没有接触过位运算,那么第一反应就是暴力解法,将其二进制转换为字符数组,然后对其两两互换,代码如下所示:

#define _CRT_SECURE_NO_WARNINGS
#define BIT_SIZE 32
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{   
    int n;
    scanf("%d", &n);
    //二进制转换
    
    char* binsy;
    binsy = (char*)malloc(sizeof(char) * (BIT_SIZE+1));

   memset(binsy, '0', sizeof(char) * BIT_SIZE);//全部赋0操作
    int i = BIT_SIZE - 1;
    while (1)
    {
        binsy[i] = (n % 2) + '0';
        i--;
        if (n == 1) break;
        n = n / 2;
    }
    binsy[BIT_SIZE] = '\0';

  //交换
    printf("Befroe swap:%s\n", binsy);
    for (int i = 0; i < BIT_SIZE; i += 2) {
        binsy[i] = binsy[i] ^ binsy[i + 1];
        binsy[i + 1] = binsy[i + 1] ^ binsy[i];
        binsy[i] = binsy[i] ^ binsy[i + 1];
    }
    printf("After swap:%s", binsy);
    system("pause");
    return 0;

}

但是接触位运算后,我们用&操作分别保存奇数位和偶数位,然后将奇数位左移一位,偶数位右移一位,进行异或即可,我们可以看下列两个用于保存奇偶位的数

  • 0101 0101 0101 0101 0101 0101 0101 0101

    • 对应十六进制为:0x55555555
  • &运算复习:只有两数都为1的时候,即为1,否则全为0
  • 1010 1010 1010 1010 1010 1010 1010 1010

    • 对应十六进制为:0xaaaaaaaa

则我们拿上面两数对其作与运算,我们拿9为例,则如下图:

img

这个时候我们得到了只含有9二进制的奇数位序列和只含有偶数位序列

这时候异或就派上用场了:同为0,异为1

我们将奇数序列右移,再将偶数序列左移

  • 移动原因:让偶数位对应奇数位,让奇数位对应偶数位,然后用异或将其连接起来。

img

知道原理后我们很容易就能将代码写出来:

n=((n & 0xaaaaaaaa) >> 1) ^ ((n & 0x55555555) << 1);

代码如下所示:

int main()
{   
    int n;
    scanf("%d", &n);
    n=((n & 0xaaaaaaaa) >> 1) ^ ((n & 0x55555555) << 1);
    printf("%d", n);
    return 0;
}

教学视频如下所示:

本文链接:

https://nullcode.fun/103.html
1 + 4 =
快来做第一个评论的人吧~