首页 > 试题广场 >

奇偶位交换

[编程题]奇偶位交换

热度指数：8066 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int x，交换其二进制的奇数位和偶数位，并返回交换后的数int。

测试样例：

返回：5

算法知识视频讲解

念润

思路

用0xAAAAAAAA与x相与求的奇数位上数字(偶数位上数字为0)

用0x 55555555 与x相与求的偶数位上数字(奇数位上数字为0)

oddVal右移一位 even左移一位相加即可。

代码

class Exchange {
public:
    int exchangeOddEven(int x) {
        // write code here
        int oddVal = (x & 0xAAAAAAAA); // bit 1 3 5 ... 31
        int evenVal = (x & 0x55555555); // bit 0 2 4 ... 30
        return (oddVal >> 1) + (evenVal << 1);
    }
};

发表于 2015-08-18 22:51:16 回复(7)

notlie

class Exchange {
public:
    int exchangeOddEven(int x) {
        // write code here
        int odd  = ((x&0x55555555)<<1);
        int even = ((x&0xAAAAAAAA)>>1)&0x7fffffff;  
        return even|odd;
    }
};

楼上很多没有&0xfffffffe与 &0x7fffffff这两步，可能能通过，却是不严谨的，因为int是有符号整型，所以如果x的最高位为1，那么取偶数位得到的数even的最高位也为1，如果此时右移，那么最高位补1而不是0，后面或的时候就有可能出问题，因为1|0等于1，改变了不该变的值。

举个例子：

x为1000.....0(总共31个0）

取偶数位得 even = 1000....0

取奇数位得 odd = 0000.....0

因为int为整型，最高位为1的为负数，右移将在左边添1

即even右移后为1100....0

even | odd = 1100....0

很明显不正确，结果应该为0100.......0才对

所以要把even的最高位置为0，即让even与 0x7fffffff相与。

发表于 2015-11-18 17:44:30 回复(3)

nailperry

补充一点，该题要想对负数依然成立，需将右移操作>>改成无符号右移>>>

	public int exchangeOddEven(int x) {
		int odd = x & (0x55555555);
		int even = x & (0xaaaaaaaa);
		return (odd << 1) + (even >>> 1);// 无符号右移，高位补0
	}

编辑于 2015-09-07 17:24:11 回复(3)

Java

大闲人柴毛毛

思路

首先要保证二进制的位数为偶数才能对换，所以若二进制位数为奇数，则需在开头添加0.

public int exchangeOddEven(int x) {
    // 将十进制int转换成二进制字符串
    String binStr = Integer.toBinaryString(x);
    // 若二进制位数为奇数，则在最前端补0
    if ( binStr.length()%2 == 1 )
        binStr = "0"+binStr;

    char[] charArray = binStr.toCharArray();
    for ( int i=1; i<charArray.length; i+=2 ) {
        char temp = charArray[i-1];
        charArray[i-1] = charArray[i];
        charArray[i] = temp;
    }

    // 将二进制字符串转换成十进制整数
    return Integer.valueOf( new String(charArray), 2 );
}

二进制字符串转换成十进制整数：Integer.valueOf( str, 2 )
十进制int转成二进制字符串：Integer.toBinaryString(int x)

发表于 2017-03-31 17:41:05 回复(0)

Ron

	/*
	 * 题目意思是数中奇偶位位数相等，而位上对应数字互换
	 * (x&0xaaaaaaaa)>>>1就是把奇数位清0，偶数位移到奇数位
	 * (x&0x55555555)<<1就是把偶数位清0，奇数位移到偶数位
	 */ 
    public int exchangeOddEven(int x) {
        // write code here
    	return ((x & 0xaaaaaaaa) >>> 1 | (x & 0x55555555) << 1);
    }

发表于 2015-10-19 12:10:24 回复(1)

C/C++

痞子丐

class Exchange {
public:
    int exchangeOddEven(int x) {
        // write code here
        //找出01 \10 对调的差值
        int a = 1;
        int iAdd = 0;
        for(int i=0; i<32; i=i+2){
            if(x & a){
                if(!( x & (2*a)))
                    iAdd += a;
            }else if( x & (2*a) ){
                iAdd -= a;
            }
            a = a << 2;
        }
        return x+iAdd;
    }
};

发表于 2020-08-01 00:57:55 回复(0)

ID84848484

import java.util.*;

public class Exchange {
    public int exchangeOddEven(int x) {
        // write code here
        int[] before=new int[32];
        int i=0;
        while(x!=0){
            before[i++]=x%2;
            x/=2;
        }
        if(i%2!=0)
            before[i++]=0;
        for(int j=0;j<i;j+=2){
            int tem=before[j];
            before[j]=before[j+1];
            before[j+1]=tem;
        }
        int ret=0;
        for(int j=0;j<i;j++){
            ret+=before[j]*Math.pow(2,j);
        }
        return ret;
    }
}

发表于 2019-05-26 23:20:48 回复(0)

C/C++

但求八月九月好运！

//略微复杂了一丝，不过时间复杂度还是可观的
/*思路：
设置两个位变量a和tempa，其中tempa=a<<1
举个例子：当x=5=0101
a从1开始，如果a&x与tempa&x的取零值不同，就说明奇数位和偶数位是不同的，
此时需要交换（如果相同则不需要处理）。
交换就非常简单了直接将x与a和tempa求异或即可！
然后将a与tempa分别向左移2位，开始下一对奇偶位比较
*/
class Exchange {
public:
    int exchangeOddEven(int x) {
        int a=1;
        int tempx=x<<1;//防止x的最高位1是奇数位
        while(a<=tempx)
        {
            int tempa=a<<1;
            if(((tempa&x)==0)&&((a&x)!=0)||((tempa&x)!=0)&&((a&x)==0))
            {
                x=x^a;
                x=x^tempa;
            }
            a=tempa<<1;
        }
        return x;
    }
};

	运行时间：3ms



	占用内存：460k

编辑于 2019-05-05 11:10:08 回复(0)

木然猫猫

Python不用位运算：

# -*- coding:utf-8 -*-
class Exchange:
    def exchangeOddEven(self, x):
        n = bin(x)[2:]
        n = list(n.rjust((len(n)+1)//2*2, '0'))
        for i in range(0, len(n), 2):
            n[i], n[i+1] = n[i+1], n[i]
        return int(''.join(n), 2)

发表于 2018-12-27 09:58:38 回复(0)

Python

华科平凡

python 两行解法。

先把它转为二进制，再交换即可。

class Exchange:
    def exchangeOddEven(self, x):
        string = bin(x).replace("0b", "").rjust(32, "0")
        return int("".join(map(lambda c: string[c + 1] + string[c], range(0, 32, 2))), 2)

还可以使用移位操作来解。没仔细研究过

编辑于 2017-10-31 16:15:08 回复(2)

Targettracking

import java.util.*;

public class Exchange {
    public int exchangeOddEven(int x) {
        // write code here
        ArrayList<Integer> list1=new ArrayList<Integer>();
        ArrayList<Integer> list2=new ArrayList<Integer>();//存储交换后的二进制
        while(x!=0){
            list1.add(x%2);      
            x/=2;
        }
        if(list1.size()%2!=0){           //将二进制位数强制为偶数
            list1.add(0);
        }
        for(int i=list1.size()-1;i>=0;i=i-2){   //list1中的最后一个数为二进制数的首位
            int temp=list1.get(i);
            list2.add(list1.get(i-1));
            list2.add(temp);
        }
        int result=0;
        for(int j=0;j<list2.size();j++){
            if(list2.get(j)==1){
                result+=Math.pow(2,list2.size()-1-j); //二进制转换为十进制
            }
        }
        return result;
    }
}

发表于 2017-07-24 21:35:07 回复(0)

Java

村长，那人偷牛！

//奇数位左移一位+偶数位右移一位 
public int exchangeOddEven(int x) {
       return (x&0x55555555)<<1|((x&0xaaaaaaaa)>>>1);
    }

发表于 2017-05-14 01:18:40 回复(1)

冯伟龙

这种思路确实没想到，先取出奇数位，再取出偶数位，然后对应的奇数位左移，偶数位右移（因为偶数位右移，所以要考虑特殊情况，为负数时，当右移时最高位补1） class Exchange { public: int exchangeOddEven(int x) { // write code here int odd=(x&0x55555555); //取奇数 int eve=(x&0xAAAAAAAA)&0x7fffffff; //取出偶数 return ((odd<<1)+(eve>>1)); } };

发表于 2016-10-07 01:38:18 回复(0)

OnePiece~~

class Exchange {
public:
    int exchangeOddEven(int x) {
        int ans=0;
        for(int i=0;i<32;i+=2){
            int bit1,bit2;
            if((1<<i)&x)
                bit1=1;
            else
                bit1=0;
           if((1<<(i+1))&x)
                bit2=1;
           else
           	   bit2=0;
           ans+=(bit1<<(i+1))+(bit2<<i); 
        }
        return ans;
    }
};

发表于 2016-10-06 17:05:18 回复(0)

Python

Yannyezixin

思路：

提取奇数位并右移一位，提取偶数位并左移一位。两结果相或

# -*- coding:utf-8 -*-
class Exchange:
    def exchangeOddEven(self, x):
        return ((x & 0xaaaaaaaa) >> 1) | ((x & 0x555555555) << 1)

发表于 2016-08-03 21:42:32 回复(0)

Java

一个小小小小萌新

/**
         * 0xaaaaaaaa=10101010101010101010101010101010(偶数位为1,奇数位为0)
         * 0x55555555=1010101010101010101010101010101(偶数位为0,奇数位为1)
         */
        int odd = x & 0x55555555;// 将偶数位全部清零，奇数位1保留
        int even = x & 0xaaaaaaaa;// 将奇数位全部清零，偶数位1保留
        return (odd<<1) + (even>>1);
        // 将odd全部往左移一位，即将偶数位0全部变为奇数位0，原奇数位的1变为偶数位的1
        // 将even全部往右移位一位，即将奇数位0全部变为偶数位0，原偶数位1变为奇数位1
        // 两者相加，得到交换二进制的奇数位和偶数位的值

发表于 2021-08-04 14:56:57 回复(0)

C/C++

漫漫云天自翱翔

class Exchange {
public:
int exchangeOddEven(int x) {
// write code here
int temp=x&0xaaaaaa;//拿到偶数位值
int temp1=x&0x555555;//奇数位
return x=(temp1<<1)|(temp>>1);
}
};

发表于 2020-09-06 00:12:02 回复(0)

杨希妍

考场哪个人会背 0xAAAAAAAA 和 0x55555555 这些东西

模拟大法好！！！

class Exchange {
public:
    int exchangeOddEven(int x) {
        // write code here
        int n = 0 , m = 0 , x1 = x;//jishu
        for(int i = 0 ; (1 << i) <= x ; i += 2)
            if(x & (1 << i))
                n += (1 << i);
        for(int i = 1 ; (1 << i) <= x ; i += 2)
            if(x & (1 << i))
                m += (1 << i);
        return (n << 1) + (m >> 1);
    }
};

发表于 2020-08-19 20:51:40 回复(0)

Dayanghe

使用map函数把把字符串的奇偶交换

# -*- coding:utf-8 -*-
class Exchange:
    def exchangeOddEven(self, x):
        # write code here
        x = bin(x).replace('0b','').rjust(32,'0')
        x = map(lambda a:x[a+1]+x[a],range(0,32,2))
        x = ''.join(x)
        return int(x,2)

发表于 2019-07-13 19:03:40 回复(0)

cpppppp

class Exchange {
public:
    int exchangeOddEven(int x) {
        // write code here
        int odds = x & 0x55555555;
        int rights = x & 0xAAAAAAAA;
        return  (odds << 1) | (rights >> 1);
    }
};

发表于 2019-07-02 17:01:47 回复(0)