作者：張張張張
github地址：https://github.com/zhanghekai
【转载请注明出处，谢谢！】

★★★由于位运算直接对内存数据进行操作，不需要转成十进制，直接在二进制上进行运算，因此处理速度非常快！！！

一、按位“与”运算符

• 按位“与”（Bitwise AND）,运算符号为：$\&$
• $a\&b$ 的操作结果：$a、b$中对应位同时为1，则对应结果位也为1，其余情况对应结果位为0。
  例：
  $$\begin{gathered} 10010001101000101011001111000 \\ \&111111100000000 \\ ---------------- \\ 101011000000000 \end{gathered}$$

1. 用于整数的奇偶性判断

\qquad 一个整数$a$，$a\&1$这个表达式可以用来判断$a$的奇偶性。二进制的末尾位为$0$表示偶数，末尾位为$1$表示奇数。使用$a\%2$来判断奇偶性和$a\&1$是一样的作用，但是$a\&1$要快好多。

例：当$a$为偶数时，$a\&1$的结果为$0$： 设$a=6$
$$\begin{gathered} 110 \\ \&1 \\ ---------------- \\ 0 \end{gathered}$$

例：当$a$为奇数时，$a\&1$的结果为$1$： 设$a=7$
$$\begin{gathered} 111 \\ \&1 \\ ---------------- \\ 1 \end{gathered}$$

2. 判断a是否是2的正整数幂

\qquad 如果一个数$a$他是$2$的正整数幂，那么$a$的二进制形式必定为$100000....$(最高位为1，之后有0个或多个0，注意：$2^0=1$，$1$是$2$的$0$次幂)；而$a-1$的二进制形式必定是$111111...$(全为$1$，但当$a=1$时， $a-1=0$)。若$a$是$2$的正整数幂，则必有$a\&(a-1)$结果为$0$。

例：当$a=16$时：
$$\begin{gathered} 10000 \\ \&1111 \\ ---------------- \\ 0 \end{gathered}$$

3. 统计二进制数a中1的个数

朴素的统计方法是： 先判断$n$的奇偶性，为奇数时计数器增加$1$，然后将$a$右移一位，重复上面的步骤，知道移位完毕。

公式法： $a\&(a-1)$ 的作用是消掉二进制数$a$中最低位的$1$。将$a\&(a-1)$ 的结果重新赋值给$a$，继续进行此操作，直到赋值结果为$0$时终止，重复的次数即为$a$中$1$的个数。

• 以python代码为例：$7$的二进制为$111$

def a1(n):
    count = 0
    while n!=0:
        n = n&(n-1)
        count+=1
    return count

a1(7)

二、按位“异或”运算符

• 按位“异或”，运算符号为：$\bigwedge$
• $a\bigwedge b$ 的操作结果：$a、b$中对应位相异时(即：一个为0，一个为1)，则对应结果位为1，其余情况对应结果位为0。
  例：
  $$\begin{gathered} 1001 \\ \bigwedge 0101 \\ ---------------- \\ 1100 \end{gathered}$$
  知识点：
  1. 任何数和0异或为任何数：0 ^ n => n
  2. 相同的数异或为0：n ^ n => 0
  3. 满足交换律a ^ b ^ c <=> a ^ c ^ b

1. 不使用临时变量，交换a和b的值

\qquad 只需下列三行代码即可实现：

a = 7
b = 5

a = a^b
b = b^a
a = a^b

\qquad 最终输出结果为：$a=5,b=7$

2. 除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

注意： 相同的数异或为0：n ^ n => 0，且，满足交换律a ^ b ^ c <=> a ^ c ^ b

\qquad 只要让数组中的元素依次相“异或”，出现两次的元素最终异或为0，仅剩下唯一只出现过一次的元素。

python代码：

nums=[1,2,3,5,6,4,2,6,3,1,4]

def YiHuo(nums):
    result = 0
    for i in range(len(nums)):
        result = result ^ nums[i]   
    return result

print(YiHuo(nums))

\qquad 输出结果为：$5$

【未完，随时更新】

---

【参考文献】

• 位运算之按位与(&)操作(快速取模算法)：https://www.cnblogs.com/bytebee/p/8194677.html
• 位运算思维解题技巧二：按位与&和左右移动 统计二进制中1的个数：https://blog.csdn.net/weixin_42110638/article/details/86594605