异或的作用：0+1=1 ，0+0=0或者1+1=0
输入描述：
第一行一个数字n
第二行n个数字
输出描述：
输出最多的区间的个数
示例：
输入
3 0 2 2
输出
2
思路：因为每两个数之间异或的值我们无法判断，所以采用一个思想：我先给定一个值（’存入set集合。其他集合都行）然后将它与后一个数异或（’存入set集合），再将值与后一位数异或（’存入set集合），以此类推，直到某一个结果与之前的值相等，那么此时count加一。 只要中间有值异或为0，那么就肯定 会有后来的值等于之前的值。
public class Solution4 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int res=0;
int i=0;
int count=0;
Set<Integer> mSet=new HashSet<>();
mSet.add(res);
while(i<n) {
res=res^(sc.nextInt());
if(mSet.contains(res)) {
count++;
mSet.clear();
}
mSet.add(res);
i++;
}
System.out.println(count);
}
}
题目描述:给定整数m以及n个数字A1, A2, …, An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果。
请求出这些结果中大于m的有多少个。
输入:第一行包含两个整数n, m。
第二行给出n个整数A1, A2, …, An。
样例输入:3 10
6 5 10
输出:输出仅包括一行，即所求的答案。
样例输出:2
异或那道题可以把每个数的二进制位求出来，用一个字典树维护，然后遍历每一个数按位贪心，比如这一位m是1，遍历的这个数这一位是0，那么和他异或的数就必须是1，如果这一位m是0，要大于m的话异或和的这一位可以是1也可以是零，ans加上之前维护的二进制位加上使这一位为1的数在字典树中查询有多少个数满足这个前缀的条件，然后在令这一位的异或和为0，继续向下遍历，最后的答案除以2。
image.png
import java.util.Scanner;
public class Q2_异或 {
public static void main(String[] args) {
trieNode root = new trieNode(-1);//根节点不存有效值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] items = new int[n];
for(int i=0; i<n; i++){
items[i] = sc.nextInt();
insert(root, items[i]);
}
long result = 0;
for(int num : items){
result += query(root, num, m, 31);//31到0是整数能表示的范围
}
System.out.println(result/2);
}
/**
* 将number加入到root中
* @param root
* @param number
*/
public static void insert(trieNode root, int number){
trieNode current = root;
for(int i=31; i>=0; i--){//先存放高位数字比如数字5，二进制为0101，则存放顺序是0,1,0,1
//求解对应第i位置处二进制数字是0还是1
int digit = (number>>i)&1;
if(current.next[digit]==null){
current.next[digit] = new trieNode(digit);
}
current = current.next[digit];
current.count++;
}
}
/**
* @param root//trieTree树
* @param a//a是做异或运算的其中的一个值
* @param m//和异或结果进行比较的数字，大于m记录值加1
* @param k//number转换为二进制后对应的第k位置上的数字
* @return
*/
public static int query(trieNode root, int a, int m, int k){
if(root == null){
return 0;
}
trieNode current = root;
for(int i=k; i>=0; i--){
int aDigit = (a>>i)&1;
int mDigit = (m>>i)&1;
if(aDigit == 1 && mDigit == 1){
if(current.next[0] == null){//对应k位置处的数字若为空，则返回0
return 0;
}else{
current = current.next[0];//返回第k位置为0的数字的个数
}
}else if(aDigit == 0 && mDigit ==1){
if(current.next[1] == null){
return 0;
}else {
current = current.next[1];
}
}else if(aDigit == 0 && mDigit == 0){
int p = query(current.next[0], a, m, i-1);
int q = (current.next[1]==null?0:current.next[1].count);
return p+q;
}else if(aDigit == 1 && mDigit == 0){
int p = query(current.next[1], a, m, i-1);
int q = (current.next[0]==null?0:current.next[0].count);
return p+q;
}
}
return 0;
}
}
//存放所有数字的二进制的形式的trie树
class trieNode{
trieNode[] next = new trieNode[2];//存放孩子结点，只有0和1两种数字
int count = 0;//此处包含的数字0或1的个数
int digit = 0;
public trieNode(int digit) {
this.digit = digit;
}
}
