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 回答