1.4 将整数的二进制奇偶位互换

2019-03-22 本文已影响0人 Aurochsy

Chapter1: 位运算的奇技淫巧

4. 将整数的二进制奇偶位互换

问题

将整数的二进制奇偶位互换

算法

算法1：用 & 运算分别取出奇偶位的数再交错异或(或用`|` 运算)

使用位运算 & 分别取出该整数 N 二进制的奇数和偶数位,
将得到奇数位的数向右移一位得到数字 a,将得到的偶数位向左移一位得到数字 b
a^b (a|b也可)就是答案

int swap1(int num){
    
    //分别提取奇数位和偶数位 
    int even = num&0xaaaaaaaa;//0xaaaaaaaa=1010...1010(二进制1010 x8)
    int odd = num&0x55555555;//0x55555555=0101...0101(二进制0101 x8)
    
    //移位合并
    int newEven = odd<<1;//这样移动才不会丢失有效数字(只是丢失0) 
    int newOdd = even>>1; 
    
    int result = newEven^newOdd;//与有效位相^的都是0，所以等价于 newEven|newOdd 
    return result;
}

算法2：交替存储到数组再转为数字输出

可参考 [3] 用字符数组的解法 ,这是用java 实现的

用C++实现的话(太麻烦了)

将数值转为二进制字符串(string类型)[1]
在循环里调换相邻奇偶位的字符(string类型也可以直接用下标索引的方式操作)[5]
string 类型转 char[] 类型
将字符串输出为十进制数字( string 直接转无有效方法[2]，网上给的方案都是针对char[]类型的转换[3]，string类型需要先转为char[]类型[3] [4]，但是将char[]转为数字时又遇到32位数字太长无法存储保证精度的问题，要将其转为十进制输出)

int swap2(int num){
    
    /*将num转为二进制数字*/
    
    //sizeof(type) 返回type类型占多少字节 
    bitset<sizeof(int)*8> binaryNum(num); //#include <bitset> 
    //bitset<32> t(num);//32为输出的位数，可以随意设置，不是2的倍数也行 
    
    /*数字转字符串*/ 
    string binaryStr = binaryNum.to_string();   
    //printf("A%cA",binaryStr[31]);
    
    /*奇偶位互换*/
    for(int i=0;i<binaryStr.length();i+=2){
        char tmp = binaryStr[i];
        binaryStr[i] = binaryStr[i+1];
        binaryStr[i+1]=tmp;
    } 
    /*string 转char* */ 
    const char* str=binaryStr.c_str();
    
    long newNum;
    
    /*char[] 转int，这样会丢失精度，32位数字太长了long也无法存储 */ 
    sscanf( str, "%ld", &newNum );  
    printf("%ld\n",newNum);
    
    //todo:想办法直接将char[]转为数字后直接转为十进制的形式输出 

    return 0;
}