查找字节中设置的位的位置
本文关键字:位置 设置 字节 查找 | 更新日期: 2023-09-27 18:14:33
当我遇到这个问题时,我正在尝试创建一个稀疏八叉树的实现,就像nVidia的人("高效稀疏体素八叉树")为他们的体素所做的那样:
我有一个字节类型的位域(所以只有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个值,但是调整大小是昂贵的
对于42个(0010 1010)
,我期望结果类似于[2,4,6]
。
谁能提供一个更优雅的解决方案,仍然是可读的?
结果
我正在使用前面实现的八叉树叶数函数来将数组设置为适当的大小。
如果您追求代码简洁,我会使用:
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];
Edit:如果您正在使用查找表,并且可以承担一次性初始化(将通过许多后续使用平摊),我建议动态创建它(而不是使源代码膨胀)。以下是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();
这是一个使用__builtin_ffs的c风格解决方案
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;
}
如何,
public static IEnumerable<int> LeafPositions(byte octet)
{
for (var i = 1; octet > 0; octet >>= 1, i++)
{
if ((octet & 1) == 1)
{
yield return i;
}
}
}
或者,在我看来,更容易阅读。
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;
}