arrays - 整数数组的校验和？

Question

我有一个大小为 4、9、16 或 25 的数组(根据输入)，数组中的数字相同但减一(如果数组大小为 9，则数组中最大的元素数组将是 8) 数字以 0 开头 我想做一些算法来为数组生成某种校验和，这样我就可以比较这两个数组是否相等，而无需遍历整个数组并逐一检查每个元素。

我在哪里可以获得此类信息？我需要尽可能简单的东西。谢谢。

编辑:只是为了清楚我想要什么:

-数组中的所有数字都是不同的，所以[0,1,1,2]是无效的，因为有一个重复的元素(1)

-数字的位置很重要，因此 [0,1,2,3] 与 [3,2,1,0] 不同

-数组将包含数字 0，因此也应考虑这一点。

编辑:

好吧，我尝试在这里实现 Fletcher 算法: http://en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){
  int i;
  int sum1=0;
  int sum2=0;
  for(i=0;i<size;i++){
    sum1=(sum1+array[i])%255;
    sum2=(sum2+sum1)%255;
  }
  return (sum2 << 8) | sum1;
}

老实说，我不知道返回线是做什么的，但不幸的是，该算法不起作用。 对于数组 [2,1,3,0] 和 [1,3,2,0]，我得到相同的校验和。

编辑2:

好的，这是另一个，阿德勒校验和 http://en.wikipedia.org/wiki/Adler-32#Example_implementation

#define MOD 65521;

unsigned long adler(int array[], int size){
  int i;
  unsigned long a=1;
  unsigned long b=0;
  for(i=0;i<size;i++){
    a=(a+array[i])%MOD;
    b=(b+a)%MOD;
  }
  return (b <<16) | a;
}

这也行不通。 数组 [2,0,3,1] 和 [1,3,0,2] 生成相同的校验和。 我在这里失去了希望，有什么想法吗？

Answer 1

让我们以包含 25 个整数的数组为例。你解释说它可以包含唯一整数 0 到 24 的任何排列。根据 this page , 有 25 个! (25 阶乘)可能的排列，即 15511210043330985984000000。远远超过一个 32 位整数可以包含的。

结论是无论你怎么努力，你都会有碰撞。

现在，这是一个计算位置的简单算法:

int checksum(int[] array, int size) {
  int c = 0;
  for(int i = 0; i < size; i++) {
    c += array[i];
    c = c << 3 | c >> (32 - 3); // rotate a little
    c ^= 0xFFFFFFFF; // invert just for fun
  }
  return c;
}