3

我有一个由 64 位组成的位字段：

long bitfield = 0;

我可以为给定索引设置位，如下所示：

void Set(long index)
{
   bitfield |= 1L << (int)(index % 64);
}

即，如果索引为 0、64、128、...，则设置位 0，如果索引为 1、65、129，...，则设置位 1，依此类推。

问题：给定一个索引和一个计数（或一个较低和较高的索引），如何在不使用循环的情况下为该范围内的所有索引设置位？

4

3 回答 3

3 
long SetRangeMask(int lower, int upper)     // 3..7
{
   if (! (lower <= upper)) throw new ArgumentException("...");

   int size = upper - lower + 1;            // 7 - 3 + 1 = 5
   if (size >= 64) return -1;
   long mask = (1 << size) - 1;             // #00100000 - 1  = #000011111
   return mask << lower | mask >> -lower;   // #00011111 << 3 = #011111000
}
于 2012-04-05T22:55:59.537 回答
1

您可以使用查找表来组合位掩码

一个真正简单的方法，不考虑特殊情况或像这些问题提出的优化，看起来像：

 static readonly private long[] maskLUT = new long[64,64] { /* generated */ };

 void SetRange(long lobit, long hibit)
 {
     lobit %= 64;
     hibit %= 64;

     bitfield |= lobit<hibit? maskLUT[lobit,hibit] : maskLUT[hibit,lobit];
 }

想法：

  • 您可能会考虑给定的优化[lobit...hibit]，如果hibit-lobit>=64，您可以一次设置所有位。

  • 考虑到两个边界都可以环绕的事实，需要考虑区域的连接性（您是先环绕两个边界，还是先环绕两个边界lobit，然后使用增量hibit从包裹的边界，就像前面提到的优化一样？）

于 2012-04-05T22:28:38.340 回答
1

您可以使用 2 x -1 创建一个 x 位长的掩码，然后将其移入并进行 OR 运算，如下所示：

void Set( int index, int count ) {
  bitfield |= (long)(Math.Pow( 2, count ) - 1) << ((index-count) % 64);
}

更新： 我喜欢认为这可以Math.Pow优化左移两个的幂，但它可能不会。Math.Pow如果是这种情况，您可以通过将调用替换为相应的左移来获得更多性能：

public void Set( int index, int count ) {
  bitfield |= ((2 << count - 1) - 1) << ((index-count) % 64);
}
于 2012-04-05T22:30:47.197 回答