BB的面试题-只用&和| 如何reverse a bit string?# JobHunting - 待字闺中
h*g
1 楼
given 10001110
want to get 01110001
只能用 and/or这两种 bit operation
want to get 01110001
只能用 and/or这两种 bit operation
g*s
2 楼
用& | 和 bit shift的方法有，只用& |的还真不知道
unsigned __int32 reversing_bits(unsigned __int32 input)
{
// complixity O(log [no.of.bits]) = O(1)
// On 32 bit machines it takes 5 steps (logical)
// Step 1
// Mask bit positions 0, 2, 4... shift LEFT this masked number by one
// Mask bit positions 1, 3, 5... shift RIGHT this masked number by one
input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1;
// Step 2
// Mask bit positions 01, 45, 89... shift LEFT this masked number by two
// Mask bit positions 23, 67... shift RIGHT this masked number by two
input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2;
// Step 3
input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4;
// Step 4
input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8;
// Sept 5
input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;
return input;
}
unsigned __int32 reversing_bits(unsigned __int32 input)
{
// complixity O(log [no.of.bits]) = O(1)
// On 32 bit machines it takes 5 steps (logical)
// Step 1
// Mask bit positions 0, 2, 4... shift LEFT this masked number by one
// Mask bit positions 1, 3, 5... shift RIGHT this masked number by one
input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1;
// Step 2
// Mask bit positions 01, 45, 89... shift LEFT this masked number by two
// Mask bit positions 23, 67... shift RIGHT this masked number by two
input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2;
// Step 3
input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4;
// Step 4
input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8;
// Sept 5
input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;
return input;
}
g*s
3 楼
没空间开销约束的话好办啊。
就一位一位的&，记录下每一位，再倒过来一位一位or即可。
【在 h*****g 的大作中提到】
: given 10001110
: want to get 01110001
: 只能用 and/or这两种 bit operation
就一位一位的&，记录下每一位，再倒过来一位一位or即可。
【在 h*****g 的大作中提到】
: given 10001110
: want to get 01110001
: 只能用 and/or这两种 bit operation
相关阅读
明年H1B确定要增加到11w了？算了一下一个星期基本上做50道leetcode现在做手机开发，但是想学习网络开发，前台后台都想学Non-PP升级PP寻求referralBroadcom NJ openings不会做进制转换的人能做软件设计吗？找到工作了但是OPT快过期了怎么办什么时候ready去面试H4->H1B, H1B approved with I-797B form, 人在美国，一定要离境再申请签证入境，才能拿到I-94stamping 吗H1B non-pp reg CSC 中发现一个很恶心的基础问题G是不是有任何bug都算fail?求box和dropbox的refer (包子奉上)如何从linkedin要到推荐悲催的g onsite跪求 有关sign on bonus的事J2没wavier能转成F1吗RQ/RP 内牛满面 另外换工作的问题Google SET/TE职位内部推荐