找到一个字节中的设置位位置

Question

当我遇到这个问题时,我正在努力创建一个稀疏的八叉树实现,就像nVidia ("Efficient Sparse Voxel Octrees")的人们为他们的体素做的那样:

我有一个字节类型的字节(只有8位)告诉我八叶树的叶子在哪里(1表示叶子,0表示没有叶子,8个节点附着 - > 8位).我现在要做的是返回叶子位置的数组.我当前的实现是使用while循环来确定是否设置了LSB.之后输入移1.所以这就是我这样做的方式:

int leafposition = _leafmask & _validmask;
int[] result = new int[8]; 
int arrayPosition = 0;
int iteration = 0;
while ( leafposition > 0 )
{
   iteration++; //nodes are not zero-indexed ... ?
   if ( (leafposition & 1) == 1 ) // LSB set?
   {
     result.SetValue( iteration, arrayPosition );
     arrayPosition++;
   };
   leafposition = leafposition >> 1;
}
return result;

这看起来并不优雅,有两件令人不安的事情:

• 这个while循环模仿for循环
• 结果数组很可能小于8个值,但调整大小是昂贵的

我希望结果与[2,4,6]42 相似(0010 1010).

任何人都可以提供更优雅的解决方案仍然可读吗？

---

结果

我正在使用我之前实现的八叉树叶子计数的函数来将数组设置为适当的大小.

Answer 1

如果你追求代码简洁,我会用这个:

int[] result = new int[8]; 
byte leafposition = 42;
int arrayPosition = 0;
for (int iteration = 0; iteration < 8; ++iteration)
    if ((leafposition & (1 << iteration)) != 0)
        result[arrayPosition++] = iteration + 1;   // one-indexed

如果你正在追求性能,我会使用预先填充的数组(256个条目).您可以静态生成(在编译时)或懒惰(在第一次调用方法之前).

int[][] leaves =
{
    /* 00000000 */ new int[] { },
    /* 00000001 */ new int[] { 1 },
    /* 00000010 */ new int[] { 2 },
    /* 00000011 */ new int[] { 1, 2 },
    /* 00000100 */ new int[] { 3 },
    /* 00000101 */ new int[] { 1, 3 },
    /* 00000110 */ new int[] { 2, 3 },
    /* 00000111 */ new int[] { 1, 2, 3 },
    /* 00001000 */ new int[] { 4 },
    /* 00001001 */ new int[] { 1, 4 },
    /* ... */
};

byte leafposition = 42;
int[] result = leaves[leafposition];

编辑:如果您正在使用查找表并且可以进行一次性初始化(将通过许多后续使用进行摊销),我建议动态创建它(而不是膨胀您的源代码).这是LINQ中的一些示例代码; 你可以使用循环版本.

int[][] leaves = new int[256][];
for (int i = 0; i < 256; ++i)
    leaves[i] = Enumerable.Range(0, 8)
                          .Where(b => (i & (1 << b)) != 0)
                          .Select(b => b + 1)
                          .ToArray();