在圆形位字段中设置位范围

本文关键字：置位 范围 字段 | 更新日期: 2023-09-27 18:30:25

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

long bitfield = 0;

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

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

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

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

在圆形位字段中设置位范围

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
}

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

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

 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，就像前面提到的优化一样？

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

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

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

public void Set( int index, int count ) {
  bitfield |= ((2 << count - 1) - 1) << ((index-count) % 64);
}
相关文章：