C代码位运算时间超限问题求高效优化方案

给定整数n和k，需要找到满足0 < a < b ≤ n且运算结果小于k的a AND b、a OR b、a XOR b的最大值。原代码采用暴力枚举所有数对后排序的方式实现，虽然逻辑正确，但时间复杂度为O(n²)，当n较大时会因超时无法通过测试用例，以下是高效的优化思路和实现代码。

原代码问题分析 #

原代码的核心问题在于：

• 枚举所有n*(n-1)/2个数对，时间复杂度为O(n²)，当n达到1e4时，数对数量就会超过5e7，计算量急剧上升；
• 对三个数组进行冒泡排序，排序的时间复杂度为O(m²)（m为数对数量），进一步加剧了超时问题。

高效优化思路 #

针对三种位运算的特性，我们可以分别设计O(n log M)（M为整数的二进制位数，通常为32）的算法，避免枚举所有数对：

1. 最大a AND b < k的求解 #

AND运算的结果不会超过参与运算的两个数中的较小值。我们可以从k-1开始向下遍历，找到第一个能被两个不同数a < b ≤n通过AND运算得到的值，通过位掩码快速判断是否存在符合条件的数对。

2. 最大a OR b < k的求解 #

OR运算的结果不小于参与运算的两个数中的较大值。因此，若max(a,b) ≥k，则a|b ≥k，我们只需在a,b ≤ min(n, k-1)的范围内寻找最大OR值，同样从k-1向下遍历即可快速定位目标值。

3. 最大a XOR b < k的求解 #

借助前缀树（Trie）存储数字的二进制位，遍历每个数b时，在Trie中查找最大的a < b使得a^b <k，记录最大结果。这种方法的时间复杂度为O(n log M)，能高效处理大规模数据。

优化后的C代码实现 #

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define min(a,b) ((a) < (b) ? (a) : (b))

// 求解最大a AND b <k
int max_and(int n, int k) {
    for (int x = k-1; x > 0; x--) {
        int mask = x;
        int b = mask;
        while (b <= n) {
            if ((b & mask) == mask) {
                if (mask < b) {
                    return x;
                }
                int next_b = b | (mask - 1);
                if (next_b > n) break;
                b = next_b + 1;
            } else {
                b += (mask - (b & mask)) + 1;
            }
        }
    }
    return 0;
}

// 求解最大a OR b <k
int max_or(int n, int k) {
    if (k == 1) return 0;
    int upper = min(n, k-1);
    for (int x = k-1; x > 0; x--) {
        for (int b = upper; b > x/2; b--) {
            int a = x ^ b;
            if (a > 0 && a < b && (a | b) == x) {
                return x;
            }
        }
    }
    return 0;
}

// 前缀树节点结构，用于XOR求解
typedef struct TrieNode {
    struct TrieNode* children[2];
} TrieNode;

// 创建新节点
TrieNode* create_node() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->children[0] = node->children[1] = NULL;
    return node;
}

// 插入数字到前缀树（从最高位到最低位）
void insert(TrieNode* root, int num) {
    TrieNode* curr = root;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!curr->children[bit]) {
            curr->children[bit] = create_node();
        }
        curr = curr->children[bit];
    }
}

// 查找与num异或后小于k的最大结果
int query(TrieNode* root, int num, int k) {
    if (!root->children[0] && !root->children[1]) return -1;
    TrieNode* curr = root;
    int max_xor = 0;
    for (int i = 31; i >= 0; i--) {
        int num_bit = (num >> i) & 1;
        int k_bit = (k >> i) & 1;
        int desired_bit = 1 - num_bit;
        
        if (curr->children[desired_bit]) {
            int temp_xor = max_xor | (1 << i);
            int k_prefix = k & ~((1 << i) - 1);
            if (temp_xor < k_prefix) {
                max_xor = temp_xor;
                curr = curr->children[desired_bit];
            } else if (temp_xor == k_prefix) {
                max_xor = temp_xor;
                curr = curr->children[desired_bit];
            } else {
                if (curr->children[num_bit]) {
                    curr = curr->children[num_bit];
                } else {
                    break;
                }
            }
        } else {
            if (curr->children[num_bit]) {
                curr = curr->children[num_bit];
            } else {
                break;
            }
        }
    }
    return max_xor;
}

// 求解最大a XOR b <k
int max_xor(int n, int k) {
    if (k == 1) return 0;
    TrieNode* root = create_node();
    int max_val = 0;
    insert(root, 1);
    
    for (int b = 2; b <= n; b++) {
        int current = query(root, b, k);
        if (current > max_val) {
            max_val = current;
        }
        insert(root, b);
    }
    
    // 释放前缀树内存（简化版可省略，实际使用需添加）
    return max_val;
}

void calculate_the_maximum(int n, int k) {
    printf("%d\n", max_and(n, k));
    printf("%d\n", max_or(n, k));
    printf("%d\n", max_xor(n, k));
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    calculate_the_maximum(n, k);
    return 0;
}

代码说明 #

• max_and：通过位掩码快速定位是否存在满足a&b=x的数对，避免全量枚举；
• max_or：缩小查找范围至min(n,k-1)，从大到小遍历快速找到符合条件的最大值；
• max_xor：利用前缀树存储二进制位，每次查询仅需遍历32位即可找到最优解，时间复杂度极低。

内容的提问来源于stack exchange，提问作者Raunak Shah