參考文章
https://www.cnblogs.com/yzxag/p/12668034.html
2021 年的 CSP-J 初賽題的閱讀程序一中涉及到了兩個很經(jīng)典的位運算：
x&(-x)：保留二進制下最后出現(xiàn)的1的位置，其余位置置0（即一個數(shù)中最大的2的n次冪的因數(shù)
x&(x-1)：消除二進制下最后出現(xiàn)1的位置昨稼，其余保持不變
看懂了這兩種位運算霹疫，問題求解就變得容易了咐熙。
二進制下的數(shù)字都可以寫成（A）1（B）的形式，其中A表示一串01字符串犀被，1表示從右向左的出現(xiàn)的第一個數(shù)字1昏鹃，B表示空（奇數(shù)）或者是連續(xù)的0（偶數(shù)），即：
- 偶數(shù)：(A)1(00…0)
- 奇數(shù)：(A)1
x&(-x)
-x的運算是贩疙，所有位置取反+1讹弯，即變形如下（ā表示所有位置取反）：
偶數(shù)：(ā)0(11…1) + 1 = (ā)1(00…0)
奇數(shù)：(ā)0 + 1 = (ā)1
所以况既，x&(-x)即：偶數(shù)：(ā)1(00…0) & (A)1(00…0) = (00…0)1(00…0)
奇數(shù)：(ā)1 & (A)1 = (00…0)1
x&(x-1)
x-1變形如下：
- 偶數(shù)：(A)1(00…0) - 1 = (A)0(11…1)
- 奇數(shù)：(A)1-1 = (A)0
所以，x&(x-1)即：
- 偶數(shù)：(A)0(11…1) & (A)1(00…0) = (A)0(00…0)
- 奇數(shù)：(A)0 & (A)1 = (A)0
