校验和是否为整数数组？

Question

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

我在哪里可以获得这类信息？我需要一些尽可能简单的东西.谢谢.

编辑:只是为了清楚我想要的东西:

- 数组中的所有数字都是不同的,因此[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],我得到相同的校验和.

EDIT2:

好的,这是另一个,Adler校验和 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 的任何排列。根据此页面，有 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;
}