如何用位运算优化竞赛代码？附CodeChef问题代码优化需求

问题背景 #

Chef拥有一个长度为N的数组A，需向数组中添加一个非负整数X，使得整个数组的按位或结果等于Y。请确定X的最小可能值，若不存在这样的X则输出-1。

输入格式 #

• 第一行输入单个整数T，表示测试用例数量。
• 每个测试用例的第一行包含两个整数N和Y，分别为数组A的长度和数组最终的按位或结果。
• 第二行包含N个空格分隔的整数A₁、A₂、…、A_N，表示数组A。

原代码 #

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

int* binary_number(int n)     // returns pointer to a array of length 20(based on given constrains)     representing binary 
{
    int* ptc;
    ptc = (int*) malloc(20*sizeof(int));
    for(int i = 0; i < 20; i++)
    {
        if((n / (int) pow(2,19-i)) > 0){*(ptc + i) = 1;}
        else {*(ptc + i) = 0;}
        n = n % (int) pow(2,19-i) ;
    }
    return ptc;
}

int or_value(int* ptc, int n)    // Takes in pointers containing 1 or zero and gives the logical OR 
{
    for(int k = 0; k < n; n++)
    {
        if(*ptc == *(ptc + 20*k)){continue;}        // pointers are 20 units apart
        else{return 1;break;}
    }

    return *ptc;

}


int main(void) {

int t; scanf("%d", &t);

for (int i = 0; i < t; i++)
{
    int n, y;
    scanf("%d %d", &n, &y);
    int a[n];
    
    for(int j = 0; j < n ; j++)
    {
        scanf("%d", &a[j]);
    }
    
    int b[20*n];
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < 20; k++)
        {
            b[20*j + k] = *(binary_number(a[n])+k);
        }
    }
    
    int c = 0;
    int p = 0;
    for (int j = 0; j < 20; j++)
    {
        
        if ((*(binary_number(y) + j) == 1) && (or_value((&b[0] + j),n) == 0)){c = c + pow(2,19 - j);}
        else if ((*(binary_number(y) + j) == 0) && (or_value((&b[0] + j),n) == 1)){p = 1; break;}
    }

    if (p==1){printf("-1");}
    else {printf("%d\n", c);}
}

return 0;
}

优化方案 #

原代码存在大量低效操作，比如反复内存分配、浮点运算处理位操作、冗余二进制数组存储，还包含逻辑错误，以下是针对性优化：

1. 用位运算替代二进制数组与pow #

位运算比浮点运算+数组操作高效数倍，无需将数字转为二进制数组，直接用位操作提取每一位：

• 提取数字num的第k位（最低位为第0位）：(num >> k) & 1
• 计算2的幂：用1 << k替代pow(2, k)，避免浮点误差与性能损耗

2. 预计算数组总按位或结果 #

原代码反复计算每一位的OR值，可先计算数组整体的按位或结果total_or：

• 若(total_or & (~Y)) != 0，说明数组存在Y没有的位，无论加什么X，最终OR结果都会包含这些位，直接返回-1
• 否则，X只需补充Y中存在但total_or中缺失的位，这些位的组合就是最小X（仅需将这些位设为1，其余为0）

3. 消除内存泄漏与冗余分配 #

原代码binary_number函数每次调用都malloc但从未free，会引发内存泄漏。优化后完全不需要该函数，直接用位运算处理。

4. 修复原代码逻辑错误 #

• 原代码binary_number(a[n])下标越界，应为binary_number(a[j])
• or_value函数循环条件for(int k = 0; k < n; n++)错误，应为k++，否则会无限循环

优化后的代码 #

#include <stdio.h>

int main(void) {
    int t;
    scanf("%d", &t);
    
    while (t--) {
        int n, y;
        scanf("%d %d", &n, &y);
        
        int total_or = 0;
        for (int j = 0; j < n; j++) {
            int num;
            scanf("%d", &num);
            total_or |= num;
        }
        
        // 检查是否存在不可能的情况：数组OR结果包含Y没有的位
        if ((total_or & (~y)) != 0) {
            printf("-1\n");
            continue;
        }
        
        // 计算最小X：Y中存在但total_or中缺失的位的组合
        int min_x = y & (~total_or);
        printf("%d\n", min_x);
    }
    
    return 0;
}

优化效果说明 #

• 时间复杂度从O(TN20)降至O(T*N)，每一步都是简单位运算，性能大幅提升
• 消除内存泄漏与逻辑错误，代码简洁可靠
• 避免浮点运算的误差与性能开销

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