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

Question

给定32位int已知至少设置了2位,有没有办法有效地清除除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;
}