位运算试题

---------------------------------------------------------------------------

1. 计算一个整数中比特位值为 1 的位数。

直观解法：
int countOnes(int x)
{
int count = 0;
for(; x; x >>= 1)
{
if (x & 1)
{
++count;
}
}
return count;
}

改进：
/* 说明：每次 x &= x - 1 操作都将 x 最右一位 1 置为 0。 */
int countOnes(int x)
{
int count = 0;
for(; x; x &= x - 1)
{
++count;
}
return count;
}

进一步改进：
/* 分治策略 (参考《Hacker's Delight》) */
int countOnes(int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555); /* 计算相邻 2 位中 1 的个数。 */
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); /* 计算相邻 4 位中 1 的个数。 */
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); /* 计算相邻 8 位中 1 的个数。 */
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); /* 计算相邻 16 位中 1 的个数。 */
x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); /* 计算相邻 32 位中 1 的个数。 */

return x;
}

---------------------------------------------------------------------------

2. 逆转一个整数的二进制位。(比如，01011011 逆转后的结果为 11011010。)

/* 分治策略 (参考《Hacker's Delight》) */
int reverse(int x)
{
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1; /* 交换相邻的 1 位。 */
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2; /* 交换相邻的 2 位。 */
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4; /* 交换相邻的 4 位。 */
x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8; /* 交换相邻的 8 位。 */
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16; /* 交换相邻的 16 位。 */

return x;
}

对上述解法略做改进：
/* 分治策略 (参考《Hacker's Delight》) */
int reverse(int x)
{
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1; /* 交换相邻的 1 位。 */
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2; /* 交换相邻的 2 位。 */
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4; /* 交换相邻的 4 位。 */
x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24);

return x;
}

---------------------------------------------------------------------------

3. 计算一个整数开头的比特位为 0 的位数。(比如，对于 00010101，得到的位数为 3。)

/* 参考《Hacker's Delight》 */
int countLeadingZeros(int x)
{
int count = 0;

if (x == 0) {return 32;}
if ((x & 0x0000FFFF) == 0) {count = count +16; x = x <<16;}
if ((x & 0x00FFFFFF) == 0) {count = count + 8; x = x << 8;}
if ((x & 0x0FFFFFFF) == 0) {count = count + 4; x = x << 4;}
if ((x & 0x3FFFFFFF) == 0) {count = count + 2; x = x << 2;}
if ((x & 0x7FFFFFFF) == 0) {count = count + 1;}

return count;
}

---------------------------------------------------------------------------

4. 计算一个整数结尾的比特位为 0 的位数。(比如，对于 10101000，得到的位数为 3。)

/* 参考《Hacker's Delight》 */
int countTrailingZeros(int x)
{
int count = 0;

if (x == 0) {return 32;}
if ((x & 0x0000FFFF) == 0) {count = count +16; x = x >>16;}
if ((x & 0x000000FF) == 0) {count = count + 8; x = x >> 8;}
if ((x & 0x0000000F) == 0) {count = count + 4; x = x >> 4;}
if ((x & 0x00000003) == 0) {count = count + 2; x = x >> 2;}
if ((x & 0x00000001) == 0) {count = count + 1;}

return count;
}

对上述解法略做改进：
/* 参考《Hacker's Delight》 */
int countTrailingZeros(int x)
{
int count = 0;

if (x == 0) {return 32;}
if ((x & 0x0000FFFF) == 0) {count = count +16; x = x >>16;}
if ((x & 0x000000FF) == 0) {count = count + 8; x = x >> 8;}
if ((x & 0x0000000F) == 0) {count = count + 4; x = x >> 4;}
if ((x & 0x00000003) == 0) {count = count + 2; x = x >> 2;}

return count + 1 - (x & 1);
}

---------------------------------------------------------------------------