我正在用 C# 编写一段对时间要求严格的代码，它要求我将定义包含范围的两个无符号整数转换为位字段。前任：
uint x1 = 3;
uint x2 = 9;
//defines the range [3-9]
// 98 7654 3
//must be converted to: 0000 0011 1111 1000
它可能有助于以相反的顺序可视化位
该范围的最大值是在运行时给出的参数，我们将其称为max_val. 因此，位域变量应该定义为一个UInt32大小等于的数组max_val/32：
UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];
给定由变量x1和定义的范围x2，执行此转换的最快方法是什么？
试试这个。计算必须用全填充的数组项的范围，并通过迭代此范围来完成此操作。最后在两个边界设置项目。
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));
可能代码不是 100% 正确，但这个想法应该可行。
刚刚测试了一下，发现了三个bug。在开始索引处的计算需要一个 mod 32，在结束索引处，32 必须是 31，并且是一个逻辑 and 而不是分配来处理开始索引和结束索引相同的情况。应该挺快的。
只是用 x1 和 x2 在阵列上的相等分布对其进行了基准测试。Intel Core 2 Duo E8400 3.0 GHz，MS VirtualPC 和 Windows XP 主机上的 Server 2003 R2。
Array length [bits] 320 160 64
Performance [executions/s] 33 million 43 million 54 million
再优化一次 x % 32 == x & 31 但我无法衡量性能提升。由于我的测试中只有 10.000.000 次迭代，因此波动非常大。而且我在 VirtualPC 中运行，这使得情况更加不可预测。
我将 BitArray 中的所有位设置为真或假的解决方案：
public static BitArray SetRange(BitArray bitArray, Int32 offset, Int32 length, Boolean value)
{
Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
bitArray.CopyTo(ints, 0);
var firstInt = offset >> 5;
var lastInt = (offset + length) >> 5;
Int32 mask = 0;
if (value)
{
// set first and last int
mask = (-1 << (offset & 31));
if (lastInt != firstInt)
ints[lastInt] |= ~(-1 << ((offset + length) & 31));
else
mask &= ~(-1 << ((offset + length) & 31));
ints[firstInt] |= mask;
// set all ints in between
for (Int32 i = firstInt + 1; i < lastInt; i++)
ints[i] = -1;
}
else
{
// set first and last int
mask = ~(-1 << (offset & 31));
if (lastInt != firstInt)
ints[lastInt] &= -1 << ((offset + length) & 31);
else
mask |= -1 << ((offset + length) & 31);
ints[firstInt] &= mask;
// set all ints in between
for (Int32 i = firstInt + 1; i < lastInt; i++)
ints[i] = 0;
}
return new BitArray(ints) { Length = bitArray.Length };
}
你可以试试：
UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) &
~(UInt32)(Math.Pow(2, x1)-1);
是否有理由不使用 System.Collections.BitArray 类而不是 UInt32[]？否则，我会尝试这样的事情：
int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
bitArray[i] = 0;
}
// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min
if (minIndex == maxIndex) {
bitArray[minIndex] = maxBits & minBits;
}
else {
bitArray[minIndex] = minBits;
bitArray[maxIndex] = maxBits;
}
我很无聊，尝试用一个char数组来做它，并用它从 base 2Convert.ToUInt32(string, int)转换为一个。uint
uint Range(int l, int h)
{
char[] buffer = new char[h];
for (int i = 0; i < buffer.Length; i++)
{
buffer[i] = i < h - l ? '1' : '0';
}
return Convert.ToUInt32(new string(buffer), 2);
}
一个简单的基准测试表明，我的方法比 Angrey Jim 的方法快 5%（即使你用位移位替换了第二个 Pow。）
如果上限太大uint而无法放入单个int. 这有点神秘，但我相信它有效。
uint[] Range(int l, int h)
{
char[] buffer = new char[h];
for (int i = 0; i < buffer.Length; i++)
{
buffer[i] = i < h - l ? '1' : '0';
}
int bitsInUInt = sizeof(uint) * 8;
int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
(decimal)bitsInUInt);
uint[] uints = new uint[numNeededUInts];
for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
j >= 0 && s >= 0;
j--, s -= bitsInUInt)
{
uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
}
int remainder = buffer.Length % bitsInUInt;
if (remainder > 0)
{
uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
}
return uints;
}
试试这个：
uint x1 = 3;
uint x2 = 9;
int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1;
/*
(1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/