找到一個字節

我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

找到一個字節

回答

相關問題