algorithm - 清除一个字中除了两个最重要的设置位以外的所有位

Question

给定一个已知至少设置了 2 位的 32 位 int，有没有办法有效地清除除设置的 2 个最高有效位之外的所有位？即我想确保输出正好设置了 2 位。

如果输入保证只有 2 或 3 位设置怎么办？

例子:

0x2040 -> 0x2040
0x0300 -> 0x0300
0x0109 -> 0x0108
0x5040 -> 0x5000

---

基准测试结果:

代码:

QueryPerformanceFrequency(&freq);
/***********/
value = (base =2)|1;
QueryPerformanceCounter(&start);
for (l=0;l<A_LOT; l++)
{
  //!!value calculation goes here
  junk+=value;    //use result to prevent optimizer removing it.

  //advance to the next 2|3 bit word
  if (value&0x80000000)
  {  if (base&0x80000000)
     {  base=6;
     }
     base*=2;
     value=base|1;
  }
  else
  {  value<<=1;
  }
}
QueryPerformanceCounter(&end);
time = (end.QuadPart - start.QuadPart);
time /= freq.QuadPart;
printf("--------- name\n");
printf("%ld loops took %f sec (%f additional)\n",A_LOT, time, time-baseline);
printf("words /sec = %f Million\n",A_LOT/(time-baseline)/1.0e6); 

在 Core2Duo E7500@2.93 GHz 上使用 VS2005 默认发布设置的结果:

--------- BASELINE
1000000 loops took 0.001630 sec
--------- sirgedas
1000000 loops took 0.002479 sec (0.000849 additional)
words /sec = 1178.074206 Million
--------- ashelly
1000000 loops took 0.004640 sec (0.003010 additional)
words /sec = 332.230369 Million
--------- mvds
1000000 loops took 0.005250 sec (0.003620 additional)
words /sec = 276.242030 Million
--------- spender
1000000 loops took 0.009594 sec (0.007964 additional)
words /sec = 125.566361 Million
--------- schnaader
1000000 loops took 0.025680 sec (0.024050 additional)
words /sec = 41.580158 Million

Answer 1

如果输入保证恰好有 2 或 3 位，那么可以非常快速地计算出答案。我们利用了表达式 x&(x-1) 等于 x 且 LSB 被清除这一事实。如果设置了 2 个或更少的位，则将该表达式应用于输入两次将产生 0。如果恰好设置了 2 位，我们将返回原始输入。否则，我们返回清除 LSB 的原始输入。

C++代码如下:

// assumes a has exactly 2 or 3 bits set
int topTwoBitsOf( int a ) 
{
   int b = a&(a-1);         // b = a with LSB cleared
   return b&(b-1) ? b : a;  // check if clearing the LSB of b produces 0
}

如果你愿意，这可以写成一个令人困惑的单一表达式:

int topTwoBitsOf( int a )
{
   return a&(a-1)&((a&(a-1))-1) ? a&(a-1) : a;
}