在布尔数组中获取所有false元素索引的最快方法是什么？

Question

假设我有一个布尔数组: {false, true, false, false, true, true, ...}

获取(例如)假元素的索引的最快方式(最优化)是什么？在这种情况下0 2 3？

Answer 1

for循环可能是执行此操作的最快方法:

List<int> indices = new List<int>();
for (int i=0;i < theArray.Length; ++i)
{
   if (theArray[i])
   {
       indices.Add(i);
   }
}

请注意,通过预先分配以下内容,您可能会以额外内存为代价获得一点点速度List<int>:

List<int> indices = new List<int>(theArray.Length);

这将避免额外的内存分配.

Answer 2

最多32个元素:

int mask = 0;
for (int i = 0; i < arr.Length; i++)
{
    if (!arr[i]) mask += 1 << i;
}

掩码将是一个32位掩码,如果该位索引处的元素为假,则每个位为1;如果该元素为真,则为0.它是数组的另一种表示,如果您希望这样说,则使用四个字节而不是每个布尔值一个字节.对于最多64个元素,您可以使用该long类型.但是,据我记忆,int你可以把它enum变成一个适当的位掩码.

涉及的总字节数:掩码四个,数组中每个元素一个,循环中的索引四个.完成的总分配:两个(如果我们不计算数组的分配).