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
相关阅读
求指点：HR要以前面试纪录才约下次面试是什么原因？LinkedIn的Infra组如何？亚马逊西雅图长期内推（直接递给hiring manager）如果你符合下面任何两个情况，还是辞职吧！(转载)google seti onsite据说是去年山东蒲松龄墓出土的聊斋志异残卷 (转载)请问有了解VMwares performance engineering group of ESXi?其实业余时间带badge出门还不是最SB的组里每年20%turn over 是不是有点高啊？最近读《聊斋志异》，发现几个让人细思恐极的细节 (转载)阿三说中国蒸饺有毒，并让人上瘾 (转载)看到新闻地铁清洁工底薪11万，马工的工资确实不高请教一个跳槽签合约的问题帮助一个朋友询问G家的team match贾跃亭绝对是顶级大师阿三又立功了烙印组太NB了Re: 国内封了狗和脸书， 为什么不封领因？ (转载)Google NYC还是Mountain View?怎样能在网上找到计算机类的工作?