今日复习内容：基础算法中的位运算

1.简介

位运算就是对二进制进行操作的运算方式，分为与运算，或运算，异或运算，取反，左移和右移。

（1）与运算

x	y	x&y
0	0	0
0	1	0
1	0	0
1	1	1

(2)或运算

x	y	x|y
0	0	0
0	1	1
1	0	1
1	1	1

(3)异或运算

x	y	x^y
0	0	0
1	0	1
0	1	1
1	1	0

异或运算满足以下性质：

交换律：x ^ y = y ^ x

结合律：(x ^ y) ^ z = x ^ (y ^ z)

自反性：x ^ x = 0

零元素：x ^ 0 = x

逆运算：若 x ^ y = z ，则两边同时异或y，得x = z ^ y。

（4）取反（~）

就是把原来的1变为0，把原来的0变为1。

（5）左移（<<）

向左移动指定数位。

举个例子：

6 的二进制为110，我把它放在一个表格里，下面一行就是向左移2位。

0	0	1	1	0
1	1	0	0	0

每次左移一位，就相当于多乘了一个2。（结合二进制还原为10进制的步骤理解）

（6）右移（>>）

右移和左移的原理一样，每次右移一位，就相当于多除了一个2。

2.用途

• 判断奇偶性

举个例子：6的二进制为110，3的二进制为11，这样就好理解了。 

• 求出x二进制的第i位

比如获取第0位（记为X0），可以直接来一个操作： X0 & 1，如果结果是1，则第0位就是1，如果结果是0，那么第0位就是0。

如果题目让获取第i位，那就用右移，把它移动到第0位，再用上面的方法。

（抱歉，我现在只能理解这些知识点，等我第二次复习的时候，再补上剩下的，有些知识点我还没懂）

3.例题

例题1：二进制中1的个数

题目描述：

给定一个整数x，输出该数二进制中1的个数；

例如，9 的二进制是1001，1的个数是2.

输入描述：

输入一个x（内存空间为32位的整数）

输出描述：

输出一个数，表示x二进制中1的个数。

参考答案：

x = int(input())
ans = 0
for i in range(32):
    if (x >> i) & 1:
        ans += 1
print(ans)

运行结果：

例题2：区间或

题目描述：

给定一个长度为n的数组a。现在有q次询问，给出两个整数l和r，求a[l];|;a[l + 1];|...;|;a[r - 1];|;a[r]的值，其中|表示按位或。

输入格式：

第一行输入两个整数n和q，分别表示数组的长度和 询问的次数；

接下来一行输入n个数：a[1],a[2],...,a[n],表示数组a；

接下来q行：

每行两个整数l和r，代表询问给出的区间。

输出格式：

对于每一次询问，输出一个整数表示结果。

名词解释：

或运算：只要有1则为1；

区间或：区间中的每一数位都单独计算，只要按数位分的区间中有一个1，则该数位的或运算就是1。

参考答案：

from itertools import accumulate
import sys
input = sys.stdin.readline
print = sys.stdout.write
n,q = map(int,input().split())
a = list(map(int,input().split()))
a_bit = []
# 每一位单独考虑，求a数组的每个数组的第i位的情况
for i in range(31):
    now_bit = []
    for x in a:
        now_bit.append((x >> i) & 1)
    # 求前缀和，方便后续计算区间和
    a_bit.append(list(accumulate(now_bit)))

for _ in range(q):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    ans = 0
    for i in range(31):
        if l == 0:
            now = a_bit[i][r]

        else:
            now = a_bit[i][r] - a_bit[i][l - 1]

        if now >= 0:
            ans += (1 << i)


    print(str(ans) + '\n')

例题3：异或森林

题目描述：

在一个神秘的世界中，存在着一个叫做“异或森林”的地方，异或森林中的每个树木都拥有独特的力量。肖恩进入了这片森林，他得到了一个任务：找出数组中满足条件的子数组，使得子数组中所有元素异或运算结果的因数为偶数，完成任务将揭示宝藏的所在地。现在，你能告诉肖恩有多少个子数组满足条件吗？

输入描述：

第一行输入一个数字n表示数组元素个数；

第二行输入n个数字，第i个数字a[i]表示数组的第i个元素；

数据保证1 <= n <= 10^4 , 1 <= a[i] <= n。

输出描述：

输出一个数字，表示满足条件的子数组的个数。

提示：

区间异或 = 前缀异或；

异或值因数个数为偶数等价于异或值为非平方数；

参考答案：

n = int(input())
a = list(map(int,input().split()))
# 预处理前缀异或，方便后续出来区间异或
pre_xor = [0] * n
pre_xor[0] = a[0]
for i in range(1,n):
    pre_xor[i] = pre_xor[i - 1] ^ a[i]
    
ans = 0
for x in range(200):
    xor = x * x
    dic = {}
    dic[0] = 1
    for j in range(n):
        ans += dic.get(pre_xor[j] ^ xor,0)
        dic(pre_xor[j]) = dic.get(pre_xor[j],0) + 1
        
ans = n * (n + 1) // 2 - ans
print(ans)

说实话，我虽然做出了这个题，但是我好像理解了，又好像没理解，看来得再研究一下。

OK，这篇就写到这里，下一篇继续！