向右展開位運算算法

本來這個職位要求的逆綿羊和山羊的操作，但我意識到，這是比我真正需要的，所以我編輯了標題，因爲我只需要一個expand-right algorithm，這是簡單的。我在下面描述的例子仍然相關。向右展開位運算算法

原貼：

我試圖找出如何做到既反綿羊和山羊的操作，或者甚至更好，一個向右展開翻轉。

根據Hacker's Delight，一個綿羊和山羊操作可以由下式表示：

SAG(x, m) = compress_left(x, m) | compress(x, ~m)

根據this site，逆可以通過發現：

INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw)

然而，我不能找到expand_left和expand_right函數的任何代碼。它們當然是壓縮的反函數，但壓縮本身很難理解。

例子：

爲了更好地解釋什麼是我要找的，可以考慮像一組8位：

0000abcd

變量a，b，c和d可以是那些或零。另外，還有一個掩碼可以重新定位這些位。

0ab00c0d

這可以用一個逆綿羊和山羊操作來完成：因此，例如，如果掩模是01100101，所得到的比特將被如下重新定位。然而，根據上述網站的this section，他提到了一種更有效的方式，他稱之爲擴展右鍵翻轉。看着他的網站，我無法弄清楚如何做到這一點。

來源

2013-05-15 Pé de Leão

'expand_right'可以在黑客的喜悅（第7.5章）中找到，我不知道在哪裏可以找到「炫」的變體。 – harold

@harold - 我想我有一個更老的版本，因爲我沒有看到第7.5節。我只是意識到該網站有源代碼下載，所以我現在正在看，但我很難理解sw參數是什麼。 –

第二版。 sw =子字大小。 Sirrida一直使用它，Hacker's Delight和其他大多數地方都不使用。 – harold

這是來自Hacker's Delight的expand_right，它只是表示expand，但它是right版本。

unsigned expand(unsigned x, unsigned m) { 
    unsigned m0, mk, mp, mv, t; 
    unsigned array[5]; 
    int i; 
    m0 = m;  // Save original mask. 
    mk = ~m << 1; // We will count 0's to right. 
    for (i = 0; i < 5; i++) { 
     mp = mk^(mk << 1);    // Parallel suffix. 
     mp = mp^(mp << 2); 
     mp = mp^(mp << 4); 
     mp = mp^(mp << 8); 
     mp = mp^(mp << 16); 
     mv = mp & m;      // Bits to move. 
     array[i] = mv; 
     m = (m^mv) | (mv >> (1 << i)); // Compress m. 
     mk = mk & ~mp; 
    } 
    for (i = 4; i >= 0; i--) { 
     mv = array[i]; 
     t = x << (1 << i); 
     x = (x & ~mv) | (t & mv); 
    } 
    return x & m0;  // Clear out extraneous bits. 
}

您可以使用expand_left(x, m) == expand_right(x >> (32 - popcnt(m)), m)使left版本，但是這可能不是最好的方式。

來源

2013-05-16 07:32:14 harold

謝謝！這是一些多汁的代碼！ –

向右展開位運算算法

回答

相關問題