一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 531|回复: 10
收起左侧

[CareerCup] 【第三轮】7.24-7.31 CareerCup 5.6

[复制链接] |试试Instant~ |关注本帖
林微熙 发表于 2014-7-25 06:32:45 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


jyh橘子 发表于 2014-7-26 07:19:56 | 显示全部楼层
【解题思路】   return ((input & 0x55555555) << 1) | ((input & 0xaaaaaaaa)>>1);
【时间复杂度】 O(1)
【空间复杂度】O(1)
【gist link】 https://gist.github.com/jyhjuzi/70a45225c8a06007fb89
-
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-27 01:38:49 | 显示全部楼层
【解题思路】   swap i and j by adding or subsracting pattern ..1100..
【时间复杂度】 O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/Noahsark/8ee698db693da7d50ea6
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-27 12:06:49 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-27 21:25:50 | 显示全部楼层
【解题思路】
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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-30 03:08:10 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-7-30 04:47:04 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

 楼主| 林微熙 发表于 2014-8-3 09:58:05 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-8-5 08:45:36 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

jetfish1900 发表于 2014-8-6 16:27:08 | 显示全部楼层
方法:

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

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

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




时间复杂度:

O(1)

空间复杂度:

O(1)

不知道可不可以引进一个互相评改的机制?这样子写完之后,也不知道对不对?
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-8-7 04:23:32 | 显示全部楼层
【解题思路】
use mask 0x55555555 to reset all even bits to 0 to get number A, and use 0xAAAAAAAA to reset all odd bits to 0 to get number B, then A<<1 | B >> 1
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/iwilbert/a4e99864f471aa41f899
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-18 13:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表