並行計算右側連續的零位（尾隨）：解釋？

考慮Bit Twiddling Hacks網站的this link。爲了計算尾隨位時，使用下面的算法：並行計算右側連續的零位（尾隨）：解釋？

unsigned int v;  // 32-bit word input to count zero bits on right 
unsigned int c = 32; // c will be the number of zero bits on the right 
v &= -signed(v); /* THIS LINE */ 
if (v) c--; 
if (v & 0x0000FFFF) c -= 16; 
if (v & 0x00FF00FF) c -= 8; 
if (v & 0x0F0F0F0F) c -= 4; 
if (v & 0x33333333) c -= 2; 
if (v & 0x55555555) c -= 1;

有人能解釋我標記爲/* THIS LINE */線的作用，更重要的是它可以只使用位操作，以避免使用signed()？

編輯：如何通過算術/邏輯/位運算來代替signed()？

來源

2014-01-23 Vincent

* signed *只是一種類型轉換，它並不代表任何實際的彙編指令。 –

沒有在本世紀生產的任何CPU，沒有。 – MSalters

v &= -signed(v)將清除v的最低位集（1位），即從v中提取最低有效1位（v將成爲2的冪後的數）。例如，對於v=14 (1110)，在此之後，我們有v=2 (0010)。

在這裏，使用signed()是因爲v是unsigned，並且您試圖否定unsigned值（給出與VS2012的編譯錯誤）（來自JoelRondeau的評論）。或者你會得到這樣的警告：warning C4146: unary minus operator applied to unsigned type, result still unsigned（我的測試）。

來源

2014-01-23 04:33:34 herohuyongtao

signed（）是因爲v是無符號的，而你試圖否定一個無符號值（給VS2012編譯錯誤）。 –

@JoelRondeau如你所說更新。謝謝。 – herohuyongtao

@herohuyongtao：但是假設我沒有signed（）函數，那麼我怎樣才能使用標準操作（算術/邏輯/位運算符）？ – Vincent

表達v &= -signed(v)，是AND運算的數量和負該號碼本身。因此，我們正在執行一個二進制的數量和數量

來源

2014-01-23 04:43:27 sajas

的二進制補碼錶示繼我從代碼理解： -

及V配合其2的補： - 設置第一個1後所有的數字從右到0

實施例： - v = 10101000然後-v =〜v + 1（1的補加1）= 01010111 + 1 = 01011000
v & -v = 10101000 & 01011000 00001000 =

來源

2014-01-23 05:56:13

有沒有簡單的位運算做-signed(v)。加法和減法需要「進位」，位X上的操作可能會影響位X + 1。所以，它需要算術。

但基本上，一元-x只是二進制0-x，所以如果您沒有直接否定操作，則可以使用標準算術。

來源

2014-01-23 09:37:21 MSalters

>沒有簡單的按位操作來執行 - 簽名（v）有。（v＆0xFFFFFFFF）+ 1 – rbtx99

並行計算右側連續的零位（尾隨）：解釋？

回答

相關問題