如何了解x&(-x)和x&(x-1)

文章目錄

• • 對于x&(-x)
  • 對于x&(x-1)

x&(-x)：保留二進制下最後出現的1的位置，其餘位置置0（即一個數中最大的2的n次幂的因數);

x&(x-1)：消除二進制下最後出現1的位置，其餘保持不變;

具體分析如下：

二進制下的數字都可以寫成（A）1（B）的形式，其中A表示一串01字元串，1表示從右向左的出現的第一個數字1，B表示空（奇數）或者是連續的0（偶數），即：

偶數：(A)1(00…0)

奇數：(A)1

對于x&(-x)

-x的運算是，所有位置取反+1，即變形如下（Ā表示所有位置取反）：

偶數：(Ā)0(11…1) + 1 = (Ā)1(00…0)

奇數：(Ā)0 + 1 = (Ā)1

　　是以，x&(-x)即：

偶數：(Ā)1(00…0) & (A)1(00…0) = (00…0)1(00…0)

奇數：(Ā)1 & (A)1 = (00…0)1

對于x&(x-1)

x-1變形如下：

偶數：(A)1(00…0) - 1 = (A)0(11…1)

奇數：(A)1-1 = (A)0

　　是以，x&(x-1)即：

偶數：(A)0(11…1) & (A)1(00…0) = (A)0(00…0)

奇數：(A)0 & (A)1 = (A)0