转换一个范围成位数组 [英] Converting a range into a bit array

问题描述

我写在C＃中的时间关键件code的，需要我转换定义一个包容的范围变成位2个无符号整数。例如：

I'm writing a time-critical piece of code in C# that requires me to convert two unsigned integers that define an inclusive range into a bit field. Ex:

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

这可能有助于形象化位以相反的顺序

It may help to visualize the bits in reverse order

此范围的最大值是在运行时给出的参数我们称之为 MAX_VAL 。因此，位字段变量应该被定义为 UInt32的数组大小等于 MAX_VAL / 32 ：

The maximum value for this range is a parameter given at run-time which we'll call max_val. Therefore, the bit field variable ought to be defined as a UInt32 array with size equal to max_val/32:

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

鉴于变量定义的范围 X1 和 X2 ，什么是执行此转换的最快方法是什么？

Given a range defined by the variables x1 and x2, what is the fastest way to perform this conversion?

推荐答案

试试这个。计算必须充满所有的人，并通过遍历这个范围内做到这一点数组项的范围内。最后，在两个边界设定的项目。

Try this. Calculate the range of array items that must be filled with all ones and do this by iterating over this range. Finally set the items at both borders.

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

可能是code是不是100％正确，但这个想法应该工作。

May be the code is not 100% correct, but the idea should work.

---

刚刚测试了一下，发现3个缺陷。在开始指数的计算所需要的模32，并在结束索引32必须是31和逻辑和而不是分配到处理的开始和结束索引是相同的情况下。应该是比较快的。

Just tested it and found three bugs. The calculation at start index required a mod 32 and at end index the 32 must be 31 and a logical and instead of a assignment to handle the case of start and end index being the same. Should be quite fast.

---

刚刚与X1的公平分配和X2阵列超过基准它。
英特尔酷睿2双核E8400 3.0 GHz的，MS虚拟PC与服务器2003 R2的Windows XP主机上。

Just benchmarked it with equal distribution of x1 and x2 over the array. Intel Core 2 Duo E8400 3.0 GHz, MS VirtualPC with Server 2003 R2 on Windows XP host.

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

---

---

还有一个优化调度X％32 == X'放大器; 31但我无法meassure性能增益。因为只有10.000.000在我的测试迭代的波动都相当高。而我在运行的VirtualPC使局势更加联合国predictable。

One more optimazation x % 32 == x & 31 but I am unable to meassure a performance gain. Because of only 10.000.000 iterations in my test the fluctuations are quite high. And I am running in VirtualPC making the situation even more unpredictable.

这篇关于转换一个范围成位数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！