微信

使用微信服务,更方便

职友集>程序员面试题 > 位操作技巧面试题

位操作技巧面试题

2015-02-25 06:30:02 阅读( 187 )

2402人 收藏本页

标签:程序员面试题

有关位操作技巧面试题

1,统计一个整数二进制式‘1’的个数:

假如一个数n=0×1110 0010,那么n – 1 = 0×1110 0001, 也就是把最右边的那个1变为0,然后左边的都变成1

如果让他们“与”运算的话,就等于把数n的最右边的1变为0,其余的位不变。这样循环m次(m位1的个数)就可以把n变成0,此时也就可以统计出1的个数了。

 

int  NumOnes(int number)

{

            int cnt = 0;

            while(number != 0)

            {

                    number &= (number – 1);

                    cnt++;

            }

          return cnt;

}

 

2.、给定一个32bit的数值,如果输出比特位反转后的值,如对于4bit的二进制值1011,翻转后为1101。要求复杂度O(lgn),n 为比特位数

 

这道题主要是有时间复杂度的限制,即lgn次,也就是说32bit你只能运算5次就要得出结果出来。

 int GetInverse(int source)
        {
            int target = 0;

            while (source > 0)
            {
                target = (target 1) | (source & 0×01);
                source = source >> 1;
            }
            return target;
        }

这个算法时间复杂度位O(n).不符合题目要求。

 

其实我们可以想想,有32bit,肯定要运用分治的方法

第1次:我们可以先对第0,1位,让他们互换,(2,3), (4,5),。。。,(30,31)这些对调位置如:

0×1001 0001  ==> 0x 0110 0010

第2次:可以对(0,1,2,3),(4,5,6,7),。。。,(28,29,30,31),如:

0x 0110 0010 ==> 0x 10011000

第3次:对(0,1,2,3,4,5,6,7)。。。,让他们对调位置

第4次(0,1,2,。。。,15)

第5次(0,。。。,31)结束.

 

现在要解决怎样处理让第i位和第i+1位对调,像(0,1)

可以这样完成; y = 0×55555555 二进制位:0×0101 0101 0101 0101 0101 0101 0101 0101

x = (((x >> 1) & y) | ((x & y) << 1));

现 在来解释一下这个操作:((x>>1)&y) 其实就是先把x右移一位,在和y做“与”运算,得出的结果就是取出了x右移一位后所有的第0,2,4,6,8,…., 30位的数,因为这里y在这位上是1其他位为0,也就是原来x的第1,3,5,7,。。。31位数。

而:(x & y) << 1 是取出x的第1,3,5,7,。。。,31位,然后把它左移,

最后在把他们“或”运算,这样就达到了(0,1),(2,3),。。。,位对调的效果了。

后面的情况类似,所以最终代码是这样的:

 

   unsigned int reverse_32bit( unsigned int x)

{
     unsigned int y = 0×55555555;
    x = (((x >> 1) & y) | ((x & y) 1));
    y = 0×33333333;
    x = (((x >> 2) & y) | ((x & y) 2));
    y = 0x0f0f0f0f;
    x = (((x >> 4) & y) | ((x LOR: #000000″>& y) ));
    y = 0x00ff00ff;
    x = (((x >> 8) & y) | ((x & y) 8));
    return((x >> 16) | (x 16));
}

 

来自IT公司面试手册

下一篇:如何讲解自己做过的项目

上一篇:程序员面试题整理 欢迎指导

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题