文章目錄

• -x
• x & -x，當x為偶數時
• x & -x，當x為奇數時
• x&-x 的實際用途

---

-x

-x 在二進制里表示對 x 的二進制按位取反(~x)之后再加 1 ，即

-x = ~x+1

x & -x，當x為偶數時

在執行 x & -x 時，若 x 為偶數，最后結果肯定有如下兩個特征：

這個結果只有一位值是1， 其他位均是0

這個值的末位0的個數與原值保持一致

從數學上推導，因為 偶數 的二進制末尾一定由 k 個 0 構成，如：110（6） 100（4）。
那么對其按位取反一定得到 k 個 1 ，當再對 ~x 進行 加一 操作后，一定能得到 1個1 和 k個0 ，而在 1 前面的數已經全部 按位取反 ，唯有 1 后面的數經過 取反->加一進位（形同再次取反） ，變回了原來的數，但我們知道，1 后面原本就是 k個0 ，因此， 證得上述兩個特征。

用幾個實例來證明：

x = 4 x：100 ~x: 011 -x=~x+1: 100 x & -x: 100x = 6 x: 110 ~x: 001 -x: 010 x & -x: 010x = 10 x: 1010 ~x: 0101 -x: 0110 x & -x: 0010

而這個結果有什么用呢？實際上這個結果是能整除這個偶數的最大的2的冪, 即：
m = n & -n ，則 n % m = 0 ， 且 m = 2 ^ k 。

---

x & -x，當x為奇數時

x 為奇數時就比較簡單了， 因為奇數取反后的值一定是偶數， 也就是有 k個0 。對其進行 加一 操作也就是變成了 k-1個0 和 1個1 ，形如：00…001（k-1個0），不會發生進位，因此只有最后一位變成了原本的數，也就是 1 ，因此 x&-x 值為 1 。

用幾個實例來證明：

x = 3 x：11 ~x: 00 -x=~x+1: 01 x & -x: 01x = 5 x: 101 ~x: 010 -x: 011 x & -x: 001x = 11 x: 1011 ~x: 0100 -x: 0101 x & -x: 0001

---

x&-x 的實際用途

實際上如果用過 Lowbit函數 ，那么此時已經會恍然大悟了，沒錯， x & -x 正是 Lowbit函數 的一種實現方式。

這里簡單說一下什么是 Lowbit函數 ？Lowbit函數用來返回參數轉為二進制后，最后一個1的位置所代表的數值。例如，Lowbit(34)的返回值將是2；而Lowbit(12)返回4；Lowbit(8)返回8；參數為任何奇數時返回1。

總結

以上是生活随笔為你收集整理的神奇的x -x，Lowbit函数的实现方式！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。