Hackers Delight 2-1 (4/5)

根據此定理, 我們可以推得 - 想要透過基本運算序列來關閉最左的1-位元是不可能的, 因為某個1-位元是否應該被關閉, 取決於它的左側是否還有其他的1-位元. 觀察其左側位元的需求是絕對無法迴避的, 也因此不可能透過右至左計算法達成.

同理, 想要透過基本運算序列來對一個 word 右移, 旋轉, 左移不定位元, 或計算當中的尾端0-位元序列長度, 都是不可能的. (計算尾端0-位元序列長度時, 輸出的最右位元取決於序列長度的奇偶性, 該性質是不可能只看輸入的最右位元就能決定的)

(譯註: 左移不定位元之所以無法達成, 可透過以下觀察得証: 令輸入當中的最右1-位元為第 x 號位元, 則輸出的第 x 號位元究竟是1還是0, 取決於左移量是否為0, 而想判斷左移量是否為0, 只看左移量的第 x 號位元或其右的位元是絕對不足以判定的)

對於上述的位元運算技巧, 有一個特別的應用: 輸入一個數字, 輸出下一個比它大, 而且含有等量 1-位元的數字. 這技巧可以幫助我們在利用數字來表示子集合的情形下, 窮舉所有相同大小的子集合.

(譯註: 原文很囉唆地說明了用數字來表示子集合的方法, 以下簡單帶過)
想要表示一個子集合, 我們可以把元素宇集存入序列當中, 如此一來每個子集合可以透過一個唯一個數字來表示: 數字當中的 i 號位元為1的時候, 代表該子集內包含 i 號元素.

R. W. Gosper 提出了一個演算法達成了上述的功能. 令 x 為輸入的數字, 該演算法的概念是尋找 x 當中最右的連續1-位元以及其右的0-位元序列, 並"增加"其數值直到含有等量的1-位元為止.

例如, 輸入 xxx0 1111 0000 (xxx 表示任意位元), 輸出 xxx1 0000 0111. 該演算法首先透過 s = x AND (-x) 來找出最右的1-位元. 在本例中得到的是 0000 0001 0000.
然後把它加入 x 得到 r (譯註: r 當中少了 n-1 個1-位元, n 代表連續1-位元的長度). 在本例中 r=xxx1 0000 0000.

接著, 我們必須補上少了的 n-1 個1-位元, 首先計算 r XOR x, 將造出一個有著 n+1 個1-位元的數字. 在本例中 r XOR x = 0001 1111 0000. 很明顯這數字又有了太多的1-位元, 我們將它除以 s, 可消去右側的0-位元序列, 最後再右移兩位元使得當中的1-位元個數為 n-1.

把這個拼拼湊湊造出來的, 有著 n-1 個置右1-位元序列的數字, 和 r 做 OR 運算就可以得到最終的輸出.