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

2021年初赛首次涉及位运算，涉及到两个很经典的位运算：

1. x&(-x)：保留二进制下最后出现的1的位置，其余位置置0（即一个数中最大的$2^n$次幂的因数）。
2. x&(x-1)：消除二进制下最后出现1的位置，其余保持不变。

比如 ** 8 & （-8） = 8，因为8的因数，有8 = 222所有最大是222 6 & （-6）= 2，因为6的因数，有6 = 23所有最大是2 12&（-12）= 4，因为12的因数，有12 = 223所有最大是22 具体分析如下： 我们可以从看待字符串的角度去思考这件事。 二进制下的数字都可以写成（A）1（B）的形式，其中A表示一串01字符串，1表示从右向左的出现的第一个数字1，B表示空（奇数）或者是连续的0（偶数），即：

偶数：(A)1(00…0) 奇数：(A)1

• ** 对于x&(-x)** 用法1： 第一，用来判断二级制1的个数 AcWinner 850.二进制中1的个数 II -x 的运算是，对x所有位置（包括符号位）取反+1，即变形如下（Ā表示所有位置取反）： (这里有个误区，我们常常讲的是负数的补码是，在负数的原码基础上除了符号位外，其他所有位取反再加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) 有两种用法，
• 第一，用来判断该数二进制中1的个数；AcWinner 859. 街灯
• 第二，用来 x&(x-1) ==0 判断是否是2的幂。AcWinner 857. 宰相的麦子

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

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com