无分支地将一个整数列表映射到另一个整数列表

Question

我有一个整数列表，它们是：

28525 30068 25975 26740 29286 24947 30067

。使用单个数学和逻辑表达式（计算速度越快越好），我需要将它们转换为列表

0 1 2 3 4 5 6

。我不能使用查找表或任何已知的哈希，因为它太慢了，表达式也需要在 C 中。

我试图通过暴力破解表达式

number & x

中的第二个组件来最大程度地减少数字携带的信息量，同时保持可区分性。我发现这种方式使所有结果彼此不同的最小数字是

1031

，它给了我这个：

1029 1028 1031 4 6 3 1027

。我想我可以添加另一个逻辑操作来进一步缩小范围，但是，我认为这不是最有效的方法。您对如何解决这个问题有什么想法吗？

顺便说一句，我不确定我是否添加了正确的标签，如果您认为它们不合适，请随时修复它们。

更新：我尝试使用余数运算符，它与暴力破解游戏我：

number % 14 = 7 10 5 0 12 13 9

，这要好得多，但仍然需要更多步骤。

Answer 1

根据您的要求，有两种方法可以在恒定的时间内完成您的要求。

第一种方法是创建一个最大预期整数大小的数组，然后将值分配给该数组，以便您可以将一个值映射到另一个值。

#include <stdio.h>
#include <string.h>

#define LIST_SIZE 7
int main() {
    int inputs[LIST_SIZE] = {28525, 30068, 25975, 26740, 29286, 24947, 30067};
    int mapper[30069] = {};
    mapper[28525] = 0;
    mapper[30068] = 1;
    mapper[25975] = 2;
    mapper[26740] = 3;
    mapper[29286] = 4;
    mapper[24947] = 5;
    mapper[30067] = 6;
    int results[LIST_SIZE];

    for (int i = 0; i < LIST_SIZE; i++) {
        results[i] = mapper[inputs[i]];
    }

    // Display results
    for (int i = 0; i < LIST_SIZE; i++) {
        printf("%d ", results[i]);
    }

    return 0;
}

这将始终在恒定时间内返回 a。

下一个方法是在常数时间内遍历数组。

#include <stdio.h>

#define LIST_SIZE 7

int mapper(int input){
    static int checker[] = {28525 ,30068 ,25975 ,26740 ,29286 ,24947 ,30067};
    static int length = sizeof(checker) / sizeof(checker[0]);
    int output = -1;

    // Don't return early to make it constant time.
    for(int i = 0; i < length; i++){
        if(checker[i] == input) output = i;
    }
    return output;
}

int main() {
    int numbers[LIST_SIZE] = {28525, 30068, 25975, 26740, 29286, 24947, 30067};
    int results[LIST_SIZE];

    for (int i = 0; i < LIST_SIZE; i++) {
        results[i] = mapper(numbers[i]);
    }

    // Display results
    for (int i = 0; i < LIST_SIZE; i++) {
        printf("%d ", results[i]);
    }

    return 0;
}