如何有效地找到整數中最低有效設定位的位置？

決定最低有效設定位的位置

在程式設計中，決定設定的最低有效位元（LSB）的位置整數可能是一個有用的運算。一個簡單的實作涉及重複用 1 遮罩整數並將其右移，直到結果變為非零，但此方法對於大整數可能會很慢。

位元旋轉最佳化

位擺弄駭客提供了一個有效的替代方案。其中一種駭客稱為「乘法和尋找」方法，利用 de Bruijn 序列的屬性在一步中執行計算。

程式碼實作

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

說明

此程式碼的工作原理是乘以整數v 乘以一個神奇的常數，然後對結果進行位移。 MultiplyDeBruijnBitPosition 陣列將乘法結果對應到 LSB 的所需位置。

優點和參考

此方法比普通實作快得多，特別是對於大整數。有關此技術的更多見解和詳細說明，請參閱：

• 「使用de Bruijn 序列在電腦單字中索引1」
• 「板表示> 位板>」位掃描”

以上是如何有效地找到整數中最低有效設定位的位置？的詳細內容。更多資訊請關注PHP中文網其他相關文章！