有关位操作技巧面试题

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) << 4));
y = 0x00ff00ff;
x = (((x >> 8) & y) | ((x & y) << 8));
return((x >> 16) | (x << 16));
}