比如說我有一個uint8_t可以是任何值的值，我只想將所有位從最低有效位翻轉到最高有效的最后 1 位值？我將如何以最有效的方式做到這一點？，有沒有可以避免使用回圈的解決方案？
以下是一些案例：
左側是原始位 - 翻轉后的右側。
00011101->0000001000000000->0000000011111111->0000000011110111->0000100001000000->00111111
[編輯]
型別也可以大于uint8_t, 它可以是uint32_t,uint64_t和__uint128_t。我只是使用uint8_t它，因為它是示例案例中最容易顯示的尺寸。
uj5u.com熱心網友回復：
一般來說，我希望大多數解決方案大致具有這種形式：
- 計算需要翻轉的位掩碼
- 通過該掩碼進行異或
正如評論中提到的，x64 是一個感興趣的目標，在 x64 上，您可以像這樣執行第 1 步：
- 通過前導零 ( ) 并從 64（或 32 中適當的值）中減去該位置
p，找到最高有效 1 的從 1 開始的位置。_lzcnt_u64 p使用從最低有效位開始的連續設定位創建一個掩碼，可能使用_bzhi_u64.
有一些變體，例如使用 BitScanReverse 找到最重要的 1（但它有一個丑陋的 0 情況），或使用移位代替bzhi（但它有一個丑陋的情況 64）。lzcnt并且bzhi是一個很好的組合，沒有丑陋的案例。bzhi需要 BMI2（Intel Haswell 或更新版本，AMD Zen 或更新版本）。
把它放在一起：
x ^ _bzhi_u64(~(uint64_t)0, 64 - _lzcnt_u64(x))
步驟 1 也可以使用一些移位和按位 OR 以通用方式（無特殊操作）實作，如下所示：
m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32; // last step should be removed if x is 32-bit
uj5u.com熱心網友回復：
這是 32 位整數的一個簡單示例，可與 gcc 和兼容的編譯器（clang等）一起使用，并且可以跨大多數架構移植。
uint32_t flip(uint32_t n)
{
#ifndef __LZCNT__ // we don't need to handle n==0 if we are
// using lzcnt rather than bsr on x86-64
if (n == 0) return 0;
#endif
uint32_t mask = ~0U >> __builtin_clz(n);
return n ^ mask;
}
DEMO
uj5u.com熱心網友回復：
如果您的用例對性能至關重要，您可能還需要考慮使用 SIMD 實作來對大量元素執行位翻轉操作。這是一個使用 AVX512 處理 32 位元素的示例：
void flip(const uint32_t in[], uint32_t out[], size_t n)
{
assert((n & 7) == 0); // for this example we only handle arrays which are vector multiples in size
for (size_t i = 0; i 8 <= n; i = 8)
{
__m512i vin = _mm512_loadu_si512(&in[i]);
__m512i vlz = _mm512_lzcnt_epi32(vin);
__m512i vmask = _mm512_srlv_epi32(_mm512_set1_epi32(-1), vlz);
__m512i vout = _mm512_xor_si512(vin, vmask);
_mm512_storeu_si512(&out[i], vout);
}
}
這使用與其他解決方案相同的方法，即計算前導零、創建掩碼、XOR，但對于 32 位元素，它每次回圈迭代處理 8 個元素。您可以類似地實作 64 位版本，但不幸的是，對于元素大小 < 32 位或 > 64 位，沒有類似的 AVX512 內在函式。
您可以在Compiler Explorer上看到上述 32 位示例（注意：如果您在輸出窗格 - 這似乎是由于當前編譯器資源管理器中的故障）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/465493.html
上一篇：在c中乘以二維矩陣時面臨的問題