兩個操作/ C++

Question

// b: uint32_t array of size n => 32*n bits 
// The bit index, i, is in the range 0 <= i < 32 * n 
// The bit in b at bit index 0 is always 0! 

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) { 
    // Returns a bit index, k, such that k <= i and k is the largest bit index 
    // for which bit k in b is 0. 
} 

// As above, value == 0 or 1 
void set_bit (uint32_t *b, unsigned n, unsigned i, unsigned value) { 
    // Sets bit at bit index i to value. 
    // It could be something like (untested): 
    if (value) 
     b[i >> 5] |= (1 << (i&31)); 
    else 
     b[i >> 5] &= (~(1 << (i&31))); 
} 

我正在尋找最有效的，但仍然可移植的（在不同的目標，但僅使用了克++編譯器）的方式來實現這些功能（尤其是第一一）。位（大，小端或其他）的存儲順序無關緊要。

天真實現（未經測試）：

uint32_t get_bit (uint32_t *b, unsigned n, unsigned i) { 
    return b[i >> 5] & (1 << (i&31)); 
} 

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) { 
    while (get_bit (b, n, i)) 
     i--; 
    return i; 
} 

跳過所有-1元素：

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) { 
    for (unsigned k = i >> 5; ~(b[k]) == 0; i = (--k << 5) + 31); 
    while (get_bit (b, n, i)) 
     i--; 
    return i; 
} 

Answer 1

取決於你有多少可用儲存空間，你可以採取查找表的方法。舉例來說，如果你可以花256個字節，那麼下面的函數會爲一個單一的uint32_t：

static const int table[256] = { 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
    3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, 0, 
}; 


int func(uint32_t b, int i) 
{ 
    b = (b << (31-i)); 

    if ((b & 0xFFFF0000) != 0xFFFF0000) 
    { 
     return ((b & 0xFF000000) != 0xFF000000) 
      ? table[(b >> 24) & 0xFF] + 24 - (31-i) 
      : table[(b >> 16) & 0xFF] + 16 - (31-i); 
    } 
    else 
    { 
     return ((b & 0xFF00) != 0xFF00) 
      ? table[(b >> 8) & 0xFF] + 8 - (31-i) 
      : table[(b >> 0) & 0xFF] + 0 - (31-i); 
    } 
} 

我敢肯定，這可以進一步優化。例如，有一些方法可以消除昂貴的條件分支;您可以使用布爾條件評估爲1或0的事實，並將它們用作被乘數。

如果您有64kB可用，那麼您一次在16位塊上執行此操作，依此類推。當然，在大型桌面上隨機訪問可能會帶來緩存效果，因此您需要進行實驗和配置文件。

Answer 2

通常我會嘗試避免「隨機」分支。例如，我們可以採用奧利查爾斯沃斯提出的解決方案，並擺脫if s。

它解決了LUT的大部分計算，但最後一部分仍然需要分支。引入額外的LUT來對付它：

unsigned index2 = table[ b  & 0xFF]  | // Values 0..7, so we use 3 bits 
       (table[(b >> 8) & 0xFF] << 3) | // Next 3 bits.. 
       (table[(b >> 16) & 0xFF] << 6) | 
       (table[(b >> 24) & 0xFF] << 9); 

現在，我們在index2 12位的值，我們可以轉化爲有意義的值用單表查詢：

return table2[index2]; // char[4096] array with precomputed values. 

此外，通過首先使用16位查找表，我們將最終得到兩個16位查找和一個8位查找。

Answer 3

您可以使用二進制搜索到一個UINT32內找到一個零位。您也可以用查找表替換最後幾個步驟，以平衡LUT的內存佔用與指令。首先，一個控制流程的解決方案：

unsigned idx_of_first_zero_bit(uint32_t n) { 
    int idx = 0; 
    if (n == 0xffffffff) return 32; // Not found; presumably the common case 

    // Binary search 
    if (n & 0xffff == 0xffff) { 
    n >>= 16; 
    idx += 16; 
    } 
    if (n & 0xff == 0xff) { 
    n >>= 8; 
    idx += 8; 
    } 
    if (n & 0xf == 0xf) { 
    n >>= 4; 
    idx += 4; 
    } 
    if (n & 0x3 == 0x3) { 
    n >>= 2; 
    idx += 2; 
    } 
    if (n & 0x1 == 0x1) { 
    n >>= 1; 
    idx += 1; 
    } 
    return idx; 
} 

爲避免分支誤預測，可以使用按位運算來實現條件更新。

 
int shift; 

// First step 
shift = ((n & 0xffff == 0xffff) << 4); // shift = (n & 0xffff == 0xffff) ? 16 : 0 
n >>= shift; 
idx += shift; 

// Next step 
shift = ((n & 0xff == 0xff) << 3); // shift = (n & 0xff == 0xff) ? 8 : 0 
n >>= shift; 
idx += shift;