【第三轮】7.24-7.31 CareerCup 5.6

5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit! are swapped, bit 2 and bit 3 are swapped, and so on).


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】   return ((input & 0x55555555) << 1) | ((input & 0xaaaaaaaa)>>1);
【时间复杂度】 O(1)
【空间复杂度】O(1)
【gist link】 https://gist.github.com/jyhjuzi/70a45225c8a06007fb89
-

【解题思路】   swap i and j by adding or subsracting pattern ..1100..
【时间复杂度】 O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/Noahsark/8ee698db693da7d50ea6

【解题思路】
Get number A by right shifting integer N(move the odd bits to even position) and resetting all odd position to 0
Get number B by left shifting integer N(move the even bits to odd position) and resetting all even position to 0
Then A|B to combine the new odd and even bits to get the final answer

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/61b99ab1015cb05a8cc0

【解题思路】
1. use 0x55555555 as the mask to get all odd bits
2. use 0xAAAAAAAA as the mask to get all even bits
3. right shift even bits  by 1 and left shift odd bits by 1
4. OR the results from the previous step

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/14099aebd3d63a6a380f

【解题思路】
Assume 32-bit integer;
even mask = 0x55555555
odd mask = 0xAAAAAAAA
extract even bits and shift left, extract odd bits and shift right, then OR these two results
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/8d853334ebe6f8da1cae

【解题思路】
0x55555555 -> 01010101010101010101010101010101
0xaaaaaaaa -> 10101010101010101010101010101010
a & 0x55555555 -> 奇数位置为1的全部留下，左移，1全部移动到偶数位置
a & 0xaaaaaaaa -> 偶数位置为1的全部留下，右移，1全部移动到奇数位置
| 一下，就把奇偶位的1和0互换了

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/UncleGarden/7097e827e75ae2b0fc7d

【解题思路】0x55555555 -> 01010101010101010101010101010101
0xaaaaaaaa -> 10101010101010101010101010101010
a & 0x55555555 -> 奇数位置为1的全部留下，左移，1全部移动到偶数位置
a & 0xaaaaaaaa -> 偶数位置为1的全部留下，右移，1全部移动到奇数位置
奇偶位的1和0互换了
【时间复杂度】o(1)
【空间复杂度】o(1)
【gist link】https://gist.github.com/hilda8519/0dac8736e0660fa402a1

【解题思路】use 0x55555555 & input to get the odd bits; 0xaaaaaaaa & input to get the even bits; odd bits left shift 1 bit with even bits right shift 1 bit to get the result
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/8d741b6cad060a205559

方法：

先取偶数位，然后往左移1位，

再取奇数位，然后往右移动1位。

最后将得到的数，进行或运算。




时间复杂度：

O（1）

空间复杂度：

O（1）

不知道可不可以引进一个互相评改的机制？这样子写完之后，也不知道对不对？