找到一个字节

我tyring创建稀疏八叉树实现像在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)。

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

结果

我使用的八叉树叶数我先前实施到阵列设定为适当的大小的功能。

来源

2013-05-19 HaMster

这是不是真的那么慢重新分配的数组。对于你的目的而言，它是否太慢是另一回事（因为这大概是经常调用的内循环代码）。您可能首先考虑计算汉明权重（位数设置为1），以便可以分配适当大小的数组，并测量两种方法。 http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer –

你知道，这就是为什么我在这里问。我写的最后一个方法就是尽可能快地获得叶数......不能相信我这样做时并没有考虑自己的代码。非常感谢你的最明显的想法！ – HaMster

如果你以后代码简洁下去，我会用这样的：

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();

来源

2013-05-19 17:52:04 Douglas

+1查找表完全避免了任何性能问题。 –

由于这只是一个字节，因此查找表可能是最快的方法。谢谢你的想法！ – HaMster

查询表是否比switch语句更快？ – Jodrell

下面是一个使用__builtin_ffs

int arrayPosition = 0; 
unsigned int tmp_bitmap = original_bitfield;   
while (tmp_bitmap > 0) { 
    int leafposition = __builtin_ffs(tmp_bitmap) - 1; 
    tmp_bitmap &= (tmp_bitmap-1); 
    result[arrayPosition++] = leafposition; 
}

来源

2015-05-30 06:47:47 boolAeon

怎么样，

public static IEnumerable<int> LeafPositions(byte octet) 
{ 
    for (var i = 1; octet > 0; octet >>= 1, i++) 
    { 
     if ((octet & 1) == 1) 
     { 
      yield return i; 
     } 
    } 
}

，或者更容易在我看来，阅读C风格的解决方案。

IEnumerable<int> LeafPositions(byte octet) 
{ 
    if ((octet & 1) == 1) yield return 1; 
    if ((octet & 2) == 2) yield return 2; 
    if ((octet & 4) == 4) yield return 3; 
    if ((octet & 8) == 8) yield return 4; 
    if ((octet & 16) == 16) yield return 5; 
    if ((octet & 32) == 32) yield return 6; 
    if ((octet & 64) == 64) yield return 7; 
    if ((octet & 128) == 128) yield return 8; 
}

或者走极端

IEnumerable<int> LeafPositions(byte octet) 
{ 
    switch (octet) 
    { 
     case 1: 
      yield return 1; 
      break; 

     case 2: 
      yield return 2; 
      break; 

     case 3: 
      yield return 1; 
      yield return 2; 
      break; 

     ... 

     case 255: 
      yield return 1; 
      yield return 2; 
      yield return 3; 
      yield return 4; 
      yield return 5; 
      yield return 6; 
      yield return 7; 
      yield return 8; 
      break; 
    } 

    yield break; 
}

来源

2015-06-16 09:18:47 Jodrell

找到一个字节

回答

相关问题