1). var bitValue = (byteValue & (1 << bitNumber)) != 0;
1). 使用位与和位移操作可以将一个字节的特定位转换为bool值。
2). 使用System.Collections.BitArray类和其包含的Get(int index)方法。
- 哪个更快？
- BitArray在什么情况下比位运算更有用？
在C#中，使用BitArray获取位值是否比使用位运算符“与”和位移更快？
24
- Secret
1
4个回答
28
@乔纳森·莱恩哈特，
很遗憾，你的基准测试并不具有决定性。它没有考虑到可能存在的惰性加载、缓存和/或预取（由CPU、主机操作系统和/或.NET运行时实现）的影响。
重新排列测试顺序（或多次调用测试方法），您可能会注意到不同的时间测量结果。
我在我的机器上使用i7-3770 CPU和64位Windows 7，在“任何CPU”平台目标和.NET 4.0客户端配置文件下运行了您原始的基准测试，结果是这样的：
我得到的是：
Testing with 10000000 operations:
A UInt32 bitfield took 484 ms.
A BitArray (32) took 459 ms.
A List<bool>(32) took 393 ms.
这与您的观察基本一致。
然而，在执行UInt32测试之前执行BitArray测试会产生以下结果：
Testing with 10000000 operations:
A BitArray (32) took 513 ms.
A UInt32 bitfield took 456 ms.
A List<bool>(32) took 417 ms.
通过查看UInt32和BitArray测试的时间，您会注意到测量时间似乎与测试本身没有关联，而是与测试运行的顺序有关。
为了至少稍微减轻这些副作用，我在每个程序运行中执行了两次测试方法，并得到了以下结果。
测试顺序UInt32，BitArray，BoolArray，UInt32，BitArray，BoolArray：
Testing with 10000000 operations:
A UInt32 bitfield took 476 ms.
A BitArray (32) took 448 ms.
A List<bool>(32) took 367 ms.
A UInt32 bitfield took 419 ms. <<-- Watch this.
A BitArray (32) took 444 ms. <<-- Watch this.
A List<bool>(32) took 388 ms.
测试顺序 BitArray，UInt32，BoolArray，BitArray，UInt32，BoolArray：
Testing with 10000000 operations:
A BitArray (32) took 514 ms.
A UInt32 bitfield took 413 ms.
A List<bool>(32) took 379 ms.
A BitArray (32) took 444 ms. <<-- Watch this.
A UInt32 bitfield took 413 ms. <<-- Watch this.
A List<bool>(32) took 381 ms.
观察测试方法的第二次调用，至少在更新的.NET运行时下使用i7 CPU，UInt32测试比BitArray测试更快，而BoolArray测试仍然是最快的。
（我很抱歉不得不将我的Jonathon基准测试的回应写成答案，但作为一个新的SO用户，我不能发表评论...）
编辑：
与其打乱测试方法的顺序，您可以尝试在调用第一个测试之前放置Thread.Sleep(5000)或类似的内容...
此外，原始测试似乎使UInt32测试处于劣势，因为它包括一个边界检查“if (bitnum < 0 || bitnum > 31)”，该检查被执行了3000万次。其他两个测试都没有包含这样的边界检查。然而，这并不是全部事实，因为BitArray和bool数组都在内部进行边界检查。
虽然我没有测试，但我预计消除边界检查将使UInt32和BoolArray测试表现类似，但这对于公共API来说并不是一个好建议。
- user2819245
2
3你应该将所有的测试都完全分开独立地运行，而不仅仅是一个接一个地运行它们。请注意保持原意，使语言更通俗易懂，不要添加任何额外信息。 - Seph
3@Seph，你说得对。为了进行适当的基准测试，这将是正确的方法。然而，我编写的代码只是为了演示著名的原则“你不测量你认为你正在测量的东西”;) - user2819245
26
BitArray 将能够处理任意数量的布尔值，而一个 byte 只能容纳8个，int 只有32个等。这将是两者之间最大的区别。此外，
BitArray 实现了 IEnumerable，而整数类型显然没有。因此，一切都取决于您的项目要求; 如果需要 IEnumerable 或类似数组的接口，则选择 BitArray。实际上，我会使用
bool[] 而不是任何其他解决方案，简单地因为它更明确地表明你正在跟踪的数据类型。
BitArray 或 bitfield 将使用大约 1/8 的空间来存储 bool[], 因为它们将 8 个布尔值“打包”成一个字节，而一个单独的 bool 将占据整个 8 位字节。但是，使用 bitfield 或 BitArray 的空间优势在存储大量的 bools 前不会起作用。（具体数学细节留给读者:-)）基准测试结果：对于我的原始测试环境，似乎
BitArray 更快一点，但与使用整数类型自行处理数据的效率相差不大。还测试了 bool[]，结果并不出乎意料是最快的。在内存中访问单个字节要比访问不同字节中的单个位更简单。Testing with 10000000 operations:
A UInt32 bitfield took 808 ms.
A BitArray (32) took 574 ms.
A List<bool>(32) took 436 ms.
代码：
class Program
{
static void Main(string[] args)
{
Random r = new Random();
r.Next(1000);
const int N = 10000000;
Console.WriteLine("Testing with {0} operations:", N);
Console.WriteLine(" A UInt32 bitfield took {0} ms.", TestBitField(r, N));
Console.WriteLine(" A BitArray (32) took {0} ms.", TestBitArray(r, N));
Console.WriteLine(" A List<bool>(32) took {0} ms.", TestBoolArray(r, N));
Console.Read();
}
static long TestBitField(Random r, int n)
{
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
SetBit(ref bitfield, r.Next(32), true);
bool b = GetBit(bitfield, r.Next(32));
SetBit(ref bitfield, r.Next(32), b);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static bool GetBit(UInt32 x, int bitnum) {
if (bitnum < 0 || bitnum > 31)
throw new ArgumentOutOfRangeException("Invalid bit number");
return (x & (1 << bitnum)) != 0;
}
static void SetBit(ref UInt32 x, int bitnum, bool val)
{
if (bitnum < 0 || bitnum > 31)
throw new ArgumentOutOfRangeException("Invalid bit number");
if (val)
x |= (UInt32)(1 << bitnum);
else
x &= ~(UInt32)(1 << bitnum);
}
static long TestBitArray(Random r, int n)
{
BitArray b = new BitArray(32, false); // 40 bytes
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
b.Set(r.Next(32), true);
bool v = b.Get(r.Next(32));
b.Set(r.Next(32), v);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long TestBoolArray(Random r, int n)
{
bool[] ba = new bool[32];
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
ba[r.Next(32)] = true;
bool v = ba[r.Next(32)];
ba[r.Next(32)] = v;
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
}
- Jonathon Reinhart
11
我从原始帖子中删除了第二个问题，并重新打开。有趣的是，我在当前项目中有一堆SetBit和GetBit函数，看起来就像这些。 - Robert Harvey
4我在我的电脑上运行了您的代码，并分别得到了1525毫秒和1185毫秒的结果。然后我将您的“随机r”改成了一个“整数”，并在所有地方将其设置为零，再次运行了它。结果是581毫秒和209毫秒，表明BitArray的速度超过随机数生成器的两倍以上，并且随机数生成器占用了2/3的处理时间。当我将“r”设置为31时，我得到了基本相同的结果（我对于这两个运行分别使用零和31）。 - Robert Harvey
多年来，我对即时编译语言基准测试的认识是：似乎没有人能做到完全正确。编译器隐藏了许多“外部因素”，这些因素会影响你的结果。我非常怀疑这些测试的有效性或结论性。 - Trap
2@Trap 有更好的想法吗？ - Jonathon Reinhart
我刚刚看到这个，想补充一下，说一个布尔数组和一个BitArray之间的空间差异直到存储大量布尔值之前都不会有影响可能会产生误导。我的意思是这取决于我们对"大量"的定义。因为在理论限制之前，列表或数组可能会耗尽可分配内存。并且最重要的是，在我看来，BitArray的最大优势不是它需要更少的空间来存储值；而是由于其极小的间距，它可以存储比布尔数组多得多的值。 - mmg666
显示剩余6条评论
0
当数据以列表形式表示时，使用BitArray存储在缓存中的数据并不具有性能优势。
基准测试表明了一个显而易见的事实：由于没有计算要求，布尔值列表的性能比BitArray更快。
然而，这些测试的一个大问题是它们在32个元素的数组大小上运行。这意味着整个数组都适合缓存。当您开始执行大量内存获取操作时，处理大型布尔集合的成本将会显现。
5000个项目的BitArray与5000个项目的List将表现非常不同。列表将需要比BitArray多8倍的内存读取。
根据您的其余逻辑（您正在进行多少分支和其他操作），差异可能很小或相当大。内存预取允许CPU在处理第一块时拉取下一个预测的内存块到缓存中。如果您正在对数据结构进行干净的直线迭代，则可能看不到显着的性能差异。另一方面，如果您正在执行一些使CPU难以预测内存获取的分支或操作，则更有可能看到性能差异。
此外，如果您开始谈论多个数据结构，情况会变得更加复杂。如果您的代码依赖于对100个不同的BitArrays的引用，那么现在我们正在谈论更多的数据，即使BitArrays本身很小，您也将跳转以访问不同的BitArrays，因此访问模式将影响事情的发展。在特定算法/场景中进行基准测试才能了解真正的行为是不可能的。
- JamesHoux
0
如果有人仍在寻找一个足够快速的不同解决方案：我建议在GetBit和SetBit方法上使用积极内联[MethodImpl(256)]。此外，还可以使用OR和XOR值的查找表来处理位位置。去除位位置检查，因为System.IndexOutOfRangeException足以指示位位置错误，并且我们不需要消耗CPU进行额外检查。 另外，如果在大量元素上执行此操作并进行调试，强烈建议使用[DebuggerHidden]属性。DebuggerHidden属性帮助调试器跳过标有此属性的方法的调试过程，从而加快调试进程。
使用Jonathon Reinhart答案中的代码，并添加TestBitFieldOpt和TestBitFieldOpt2的方法和测试。
static readonly uint[] BITMASK = new uint[]
{
0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
};
static readonly uint[] BITMASK_XOR = new uint[]
{
0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF
};
static long TestBitFieldOpt(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
SetBitOpt(ref bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
SetBitOpt(ref bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long TestBitFieldOpt2(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
bitfield = SetBitOpt2(bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
bitfield = SetBitOpt2(bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
[MethodImpl(256)]
static bool GetBitOpt(UInt32 bitfield, int bitindex)
{
return (bitfield & BITMASK[bitindex]) != 0;
}
[MethodImpl(256)]
static void SetBitOpt(ref UInt32 bitfield, int bitindex, bool value)
{
if (value)
bitfield |= BITMASK[bitindex];
else
bitfield &= BITMASK_XOR[bitindex];
}
[MethodImpl(256)]
static UInt32 SetBitOpt2(UInt32 bitfield, int bitindex, bool value)
{
if (value)
return (bitfield | BITMASK[bitindex]);
return (bitfield & BITMASK_XOR[bitindex]);
}
我将测试数量增加了10的幂次方（以获得更真实的结果），优化后的代码结果与最快方法非常接近：
Testing with 100000000 operations:
A BitArray (32) took : 4947 ms.
A UInt32 bitfield took : 4399 ms.
A UInt32 bitfieldopt : 3583 ms.
A UInt32 bitfieldopt2 : 3583 ms.
A List<bool>(32) took : 3491 ms.
通常情况下，本地堆栈上的变量越少，分支越少，预先计算的值就会获胜。因此，拿起书和铅笔，缩短数学公式，使其更简洁...在函数内部进行真正的内联有很大帮助，但最好使用[MethodImpl(256)]属性来提高源代码的可读性/维护性，如上所述。
希望这能帮助某人找到解决他的问题的方法。
- SoLaR
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
System.Diagnostics.Stopwatch可以计时并确定其速度是否更快。最好在尽可能接近生产环境的条件下进行测试。 - Corey Ogburn