理解 x&(-x)和x&(x-1)（2021 CSP-J）

参考文章
https://www.cnblogs.com/yzxag/p/12668034.html

2021 年的 CSP-J 初赛题的阅读程序一中涉及到了两个很经典的位运算：

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
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容