算法刷题笔记 最大异或对（详细注释的C++实现）

题目描述

• 在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？

输入格式

• 第一行输入一个整数N。
• 第二行输入N个整数A1～AN。

输出格式

• 输出一个整数表示答案。

数据范围

• 1 ≤ N ≤ 10^5,
• 0 ≤ Ai < 2^31

基本思路

• 本题可以使用字典树进行快速求解。字典树即Trie树，也被称为单词查找树。由于本题的代码具有非常详细的注释，因此整体思路只需要参考代码即可，在此不过多赘述。
• 需要注意的是，本题中使用了C++中的bitset模板类，该模板类可以将一个整数转换为指定位数的二进制数（通过使用构造函数），对于生成的二进制数，可以使用flip()方法对其进行取反；最后，还可以通过to_string()方法将该二进制数转换为string类型。
• 通过本题学习到的其他一些知识：
  • C++中基本数据类型作为函数参数，直接传入值的效率比传入常引用效率更高；
  • C++中基本数据类型使用赋值符号进行初始化的效率等同于使用初始化列表进行初始化；
  • C++中对使用最多的int数据类型进行了优化，使得这个类型可能比short等更短小的类型效率更高。

实现代码

#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;

// 创建一个整数数组存储用户输入
const int n = 100010;
int integers[n];
// 记录创建trie树过程中的当前结点下标
int node_index;
// 使用数组表示trie树（最多有100000个整数，每个整数要31位表示，且可能有两种情况的下一个结点）
int trie[31 * n][2];

// 功能：将一个指定的整数转换为三十一位二进制数构成的字符串
inline string get_binary(int n, bool flip = false)
{
    // 使用C++模板类bitset将十进制整数转换为三十一位的二进制整数
    bitset<31> binary(n);
    // 如果flip为true，则对该二进制串进行取反
    if(flip == true) binary.flip();
    // 将该二进制整数转换为字符串
    return binary.to_string();
}

// 功能：将一个二进制整数字符串插入到单词查找树中
void insert_to_trie(const string& binary_interger)
{
    // 从trie树的根节点开始向下遍历
    int node = 0;
    for(int i = 0; i < binary_interger.length(); ++ i)
    {
        // 记录该二进制整数字符串当前的字符，并将其转换为整数
        char current_char = binary_interger[i] - '0';
        // 如果当前trie树结点对应该字符的路线为空，则创建这条路线
        if(trie[node][current_char] == 0) trie[node][current_char] = ++ node_index;
        // 根据路线进行遍历，指向下一个结点
        node = trie[node][current_char];
    }
}

// 功能：根据指定的数组构建一棵二进制串单词查找树
void build_trie_tree(int n)
{
    // 逐一遍历整数数组中的每一个整数，并将其转换为三十一位形式的二进制字符串
    // current表示创建的二进制位结点编号
    for(int i = 0; i < n; ++ i)
    {
        // 首先将当前整数转换为二进制字符串
        string binary_integer = get_binary(integers[i]);
        // 将当前的二进制字符串插入单词查找树中
        insert_to_trie(binary_integer);
    }
}

// 功能：在trie树中查找与指定整数的二进制串能构成最大异或对的二进制串，并返回最大异或值
int search_max_xor(int x)
{
    // 将传入的整数转换为二进制后取反，然后转换为字符串，表示最理想情况下的遍历路线
    string ideal_binary = get_binary(x, true);
    // 逐一遍历该二进制字符串中的每一位，查找尽可能大的异或对
    int max = 0;           // 记录最大异或值
    int current_node = 0;  // 记录当前结点的下标
    for(int i = 0; i < ideal_binary.length(); ++ i)
    {
        // 记录二进制串的当前字符
        int current_char = ideal_binary[i] - '0';
        // 当可以按照最优路线遍历下去时，选择最优路线并更新最大异或值
        if(trie[current_node][current_char] != 0) 
        {
            current_node = trie[current_node][current_char];
            max = 2 * max + 1;
        }
        // 如果不能按照最优路线遍历下去，则选择另一条可以走的路线
        else
        {
            // 确定另一条路线
            current_char = (current_char == 1 ? 0 : 1);
            current_node = trie[current_node][current_char];
            // 更新最大异或值
            max = 2 * max;
        }
    }
    // 返回最大异或值
    return max;
}

// 功能：根据创建号的单词查找树，查找其中二进制串的最大异或对，并返回最大异或值
// 传入参数：单词查找树中的二进制串个数
int max_xor(int n)
{
    // 记录局部最大异或值
    int temp_max = 0;
    // 每次取出一个二进制串，找出与该二进制串构成最大异或对的异或值
    for(int i = 0; i < n; ++ i) temp_max = max(temp_max, search_max_xor(integers[i]));
    // 返回全局最大异或值
    return temp_max;
}

// 功能：用于求出一个数组中所有整数的最大异或对对应的异或值
// 传入参数：数组中的整数元素个数
// 输出结果：最大的异或对对应的异或值
int get_max_xor(int n)
{
    // 首先根据已知整数数组构建一棵单词查找树（trie树）
    build_trie_tree(n);
    // 根据已经构建好的单词查找树，查找最大异或对并返回
    return max_xor(n);
}

int main(void)
{
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; ++ i) scanf("%d", &integers[i]);
    printf("%d", get_max_xor(N));
    return 0;
}