使用1的補碼生成顯示第一個非零位的掩碼

Question

在閱讀採訪準備書時，我發現了一個關於補碼1的有趣屬性。

物業說給一個數X，我們可以生成使用1的補數如下口罩，顯示第一個設置位（從右到左）： X & ~(X - 1)其中~代表1的補數。

例如，如果X = 0b0011然後 0b0011 & 0b1101 = 0b0001

我理解的是，筆者是做X-1翻轉右起第一個非零位。不過我很好奇，他是怎麼想出顯示在X的第一個非零位的想法，採取1的的X-1和&荷蘭國際集團它的補充與X會導致成位掩碼

它是我第一次在StackOverflow發佈，所以如果這個問題不屬於這裏，我很抱歉。

Answer 1

這實際上可以用一些數學來證明。假設x是一個正整數。對於所有的x，存在x的二進制表示。另外，對於所有x，存在一個數字x - 1，它也具有二進制表示。對於所有x，位於1的位將與x - 1不同。讓我們定義~作爲補碼運算符。對於任何二進制數字b,~b都將b中的所有0轉換爲1s，並將s中的所有b轉換爲0s。然後我們可以說，~(x - 1)必須在1的位置上具有相同的位，如x。現在，這對於奇數很簡單，因爲所有奇數o在1的位中有1，所以必須有~(x - 1)，我們可以在那裏停下來。對於偶數，這有點棘手。對於所有偶數，e，1位必須爲空。正如我們所述，x（和e）必須大於0，我們也可以說對於所有的偶數，e，存在一些位，使得該位的值爲1。我們也可以說對於e - 1，1的位必須是1，因爲e - 1必須是奇數。此外，我們可以說在e中的值爲1的第一位將是0的e - 1。因此，使用補碼e - 1，e中的那個位必須是0，該位將通過補碼規則變爲1。使用&運營商，這將是e和~(e - 1)之間的常見1位。

Answer 2

首先，請注意，對於任何X,X & (~X) = 0和X & X = X。

Let X = b_n b_(n-1) ... b_k ... b_1, where b_k is the first set bit. 
Thus, X is essentially this: 
    b_n b_(n-1) ... b_(k+1) 1 0 0 ... 0 
           ---- k ---- 
X-1 is: 
    b_n b_(n-1) ... b_(k+1) 0 1 1 ... 1 
           ---- k ---- 
~(X-1) is: 
    ~b_n ~b_(n-1) ... ~b_(k+1) 1 0 0 ... 0 
           ---- k ---- 

X & ~(X-1) is: 
    0 0 .................... 0 1 0 0 ... 0 
           ---- k ---- 

Answer 3

這招可能是更好地稱爲寫成

X & -X 

這是（的-）的定義等同，並且使用的-如下解釋就變得非常簡單明白：

對於非零數的字符串表示法， - （a10 ^k）=（〜a）10 ^k

如果您對符號不熟悉，a10 ^k只是表示「一些位串」a「，後跟一個1，後跟k個零」。

這個解釋只是說，否定保持所有的尾隨零和最低的1，但反轉所有的高位。你可以看到，它也是從否定的定義中做到的，例如，如果你看看~X + 1，你會發現+1消除了尾隨零的反轉（成爲+1的反轉）和最低設置位（它變爲0，然後通過尾隨零進位）。

無論如何，使用否定的解釋，顯然頂部部分被刪除，最低設置位被保留，並且尾部零將保留。

一般來說，字符串表示法在提出這些技巧時非常有用。例如，如果你知道否定的樣子，在串符號，這一招實在是相當明顯的，所以有一些相關的技巧，你可以接着還發現：

• x & x - 1重置最低設置位
• x | -x一直尾隨零，但將所有較高位
• x^-x保持尾隨零位時，最低設定位，但將所有較高位

..和更多的變種。