c - 如何从较大(11 字节)的唯一编号生成较小的唯一编号？将军C

Question

我有几个设备。它们每个都有由 11 个字节组成的唯一 ID，例如:0x34 0x57 0x36 0x31 0x38 0x39 0x15 0x0e 0x00 0x0f 0x00。我想生成唯一编号(0-32767 或 0-65535)以在广播 FindDevices 命令时延迟应答。当设备同时开始响应时，会出现 RS485 总线争用问题，因此我想避免这种情况。

我的第一次尝试是对唯一 ID 的所有 11 个字节求和，调用 srand(sum) 来生成种子，然后调用 rand() 来获取我的值。但不幸的是，这是一个糟糕的解决方案，在我的一批设备中，我有 2 台设备具有唯一 ID，但具有相同的“(不是那么)唯一”编号 :(

UID1:34 57 36 31 38 39 15 0e 00 0f 00总和:405 十进制生成数:23860

UID2:34 57 33 31 35 39 04 18 00 1c 00总和:405 十进制生成数:23860

设备不知道在其他设备中生成了什么数字或它们具有什么唯一 ID，因此它们不能简单地比较它们。

知道如何生成这样的唯一编号(0-32767 或 0-65535)吗？

编辑:我工作台中批处理的唯一 ID(十六进制)列表:
01. 34 57 36 31 38 39 15 0E 00 02 00
02. 34 57 36 31 38 39 15 0E 00 06 00
03. 34 57 36 31 38 39 15 0E 00 0A 00
04. 34 57 36 31 38 39 15 0E 00 0E 00
05. 34 57 36 31 38 39 15 0A 00 14 00
06. 34 57 36 31 38 39 15 0A 00 1C 00
07. 34 57 36 31 38 39 15 09 00 23 00
08. 34 57 36 31 38 39 15 0A 00 24 00
09. 34 57 36 31 38 39 0E 1D 00 1A 00
10. 34 57 36 31 38 39 15 0E 00 09 00
11. 34 57 33 31 35 39 04 10 00 20 00
12. 34 57 33 31 35 39 04 18 00 1C 00
13. 34 57 36 31 38 39 15 0E 00 0F 00
14. 34 57 36 31 38 39 15 0E 00 13 00
15. 34 57 36 31 38 39 15 0E 00 17 00
16. 34 57 36 31 38 39 15 0E 00 1F 00
17. 34 57 36 31 38 39 15 0A 00 25 00
看起来它们是唯一的，但许多字节是重复的/恒定的。好的解决方案应该生成整个范围内的值，即使输入值彼此接近 :)

编辑2:以下是您回答的所有解决方案的结果:

Test results:
OP:  1977, H1L: 14759, H1H: 13938, H2L:  7189, H2H: 36686, H3L: 14759, H3H: 13938, H4:  2652, PRS: 61086
OP:  3669, H1L: 13735, H1H: 12914, H2L:  8213, H2H: 37710, H3L: 13735, H3H: 12914, H4:  6748, PRS: 25852
OP:  5361, H1L: 16807, H1H: 15986, H2L:  5141, H2H: 34638, H3L: 16807, H3H: 15986, H4: 10844, PRS: 40974
OP:  7053, H1L: 15783, H1H: 14962, H2L:  6165, H2H: 35662, H3L: 15783, H3H: 14962, H4: 14940, PRS: 19836
OP:  7899, H1L: 18507, H1H: 25943, H2L:  3441, H2H: 24681, H3L: 18507, H3H: 25943, H4: 21076, PRS:  4898
OP: 11283, H1L: 20555, H1H: 27991, H2L:  1393, H2H: 22633, H3L: 20555, H3H: 27991, H4: 29268, PRS: 10065
OP: 13821, H1L:   391, H1H: 26260, H2L: 21557, H2H: 24364, H3L:   391, H3H: 26260, H4: 36434, PRS: 63904
OP: 14667, H1L: 30795, H1H: 38231, H2L: 23902, H2H: 12393, H3L: 30795, H3H: 38231, H4: 37460, PRS: 46300
OP: 15513, H1L: 23009, H1H: 40628, H2L: 31688, H2H:  9996, H3L: 23009, H3H: 40628, H4: 27066, PRS: 21678
OP: 21322, H1L: 17063, H1H: 16242, H2L:  4885, H2H: 34382, H3L: 17063, H3H: 16242, H4:  9820, PRS: 60787
OP: 22168, H1L: 31736, H1H: 54522, H2L: 22961, H2H: 61623, H3L: 31736, H3H: 54522, H4: 32801, PRS: 20737
OP: 23860, H1L:  3760, H1H: 10032, H2L: 18188, H2H: 40592, H3L:  3760, H3H: 10032, H4: 28721, PRS: 50696
OP: 23860, H1L: 15527, H1H: 14706, H2L:  6421, H2H: 35918, H3L: 15527, H3H: 14706, H4: 15964, PRS: 28319
OP: 25552, H1L: 10407, H1H:  9586, H2L: 11541, H2H: 41038, H3L: 10407, H3H:  9586, H4: 20060, PRS: 60097
OP: 27244, H1L:  9383, H1H:  8562, H2L: 12565, H2H: 42062, H3L:  9383, H3H:  8562, H4: 24156, PRS:  5512
OP: 30628, H1L: 11431, H1H: 10610, H2L: 10517, H2H: 40014, H3L: 11431, H3H: 10610, H4: 32348, PRS: 55107
OP: 31474, H1L: 30539, H1H: 37975, H2L: 24158, H2H: 12649, H3L: 30539, H3H: 37975, H4: 38484, PRS:  4379
OP: 20035, H1L:     0, H1H:     0, H2L: 21948, H2H: 50624, H3L:     0, H3H:     0, H4:     0, PRS: 26124

OP 是我的原始方法，它很差并且为列出的 UID 生成非唯一编号。H1L 和H1H 是 chux 提出的简化解决方案。H2L、H2H、H3L、H3H 是我的修改(在下部或上部添加 ~)以查看它是否产生更好的结果。H4 是 alain 提出的解决方案。PRS 是 Pearson 返回 mattinbits 建议的 uint16_t。

获胜者是... PRS! :) 您的所有建议都从列出的 UID 生成唯一数字，因此它们是正确的，但 Pearson 散列法 提供最佳的结果方差(在 Excel 中检查 ;) )。感谢您的帮助!

Answer 1

要从较大的数字(11 字节或 88 位)生成 15 或 16 位范围内的唯一数字是 hash function并且像 OP 生成的编号 23860 一样容易发生冲突。

将所有 11 个字节求和非常弱，因为 11 个字节的和在 0 到 11*255 或 2805 的范围内，分布非常不均匀。所以代码只为 srand() 生成了 2806 个不同的种子。使用比 8 位更宽的整数分组会更好。推荐 64 位组相互异或。

使用 srand()/rand() 是一种方法，但在一致性方面有弱点:1) 可移植性:不同平台上的相同数据可能会产生不同的数字，如 C 指定的关于 rand() 方法的内容很少。 2) 因为它需要 2 个函数共享一个全局状态变量，所以代码必须确保另一个线程/中断不会把事情搞砸，或者这些调用会扰乱其他使用 rand() 的函数的一致性。 rand() 的一个大问题是在 RAND_MAX 为 32767(其最小指定值)且代码尝试 [0...65536] 的系统上。

我发现一致性很重要，因为能够在多个平台上使用相同的测试代码:代码维护方面的显着优势。

@mattinbits well 推荐一个好的 8/16 位解决方案。为什么要重新发明轮子？然而我不使用战车轮胎，所以......

如果 OP 似乎并不真正需要 [0...32767] 或 [0...65536] 的整个 范围内的标识符(OP 是指 65535 吗？)，请考虑prime 依赖于 % 的简单可移植可重复哈希方法接近极限以很好地混合位。

// return numbers 0 ... 32748 or 0 ... 65536
unsigned long Hash(const unsigned char ID[11]) {
  unsigned long long Upper;
  unsigned long Lower;
  Upper = (ID[0]*1ULL<<56) | (ID[1]*1ULL<<48) | (ID[2]*1ULL<<40) | (ID[3]*1ULL<<32) |
      (ID[4]*1UL<<24)  | (ID[5]*1UL<<16) | (ID[6]*1U<<8) | ID[7];
  Lower = (ID[8]*1UL<<16) | (ID[9]*1U<<8) | ID[10];
  // Greatest prime <= 32768
  #define Prime_LE_32768 32749
  return (Upper ^ Lower) % Prime_LE_32768;

  // or 
  // Greatest prime <= 65537
  #define Prime_LE_65537 65537
  return (Upper ^ Lower) % Prime_LE_65537;
}

[编辑] 具有潜在的简化。

unsigned Hash(const uint8_t ID[11], unsigned prime) {
  uint64_t H[2] = {0};
  memcpy(H, ID, 11);
  return (H[0] ^ H[1]) % prime;
}

const unsigned char ID[][11] = {
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x02, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x06, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x0A, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x0E, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0A, 0x00, 0x14, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0A, 0x00, 0x1C, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x09, 0x00, 0x23, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0A, 0x00, 0x24, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x0E, 0x1D, 0x00, 0x1A, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x09, 0x00 },
    { 0x34, 0x57, 0x33, 0x31, 0x35, 0x39, 0x04, 0x10, 0x00, 0x20, 0x00 },
    { 0x34, 0x57, 0x33, 0x31, 0x35, 0x39, 0x04, 0x18, 0x00, 0x1C, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x0F, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x13, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x17, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0E, 0x00, 0x1F, 0x00 },
    { 0x34, 0x57, 0x36, 0x31, 0x38, 0x39, 0x15, 0x0A, 0x00, 0x25, 0x00 },
    { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } };

#define Prime_LE_32768 32749
#define Prime_LE_65536 65521u
void test() {
  int i, j;
  for (i = 0; i < sizeof ID / sizeof ID[0]; i++) {
    const char *comma = "";
    for (j = 0; j < 11; j++) {
      printf("%s%02X", comma, ID[i][j]);
      comma = "-";
    }
    printf(" %5u", Hash(ID[i], Prime_LE_32768));
    printf(" %5u\n", Hash(ID[i], Prime_LE_65536));
  }
  puts("");
}

Output

34-57-36-31-38-39-15-0E-00-02-00 14759 13938
34-57-36-31-38-39-15-0E-00-06-00 13735 12914
34-57-36-31-38-39-15-0E-00-0A-00 16807 15986
34-57-36-31-38-39-15-0E-00-0E-00 15783 14962
34-57-36-31-38-39-15-0A-00-14-00 18507 25943
34-57-36-31-38-39-15-0A-00-1C-00 20555 27991
34-57-36-31-38-39-15-09-00-23-00   391 26260
34-57-36-31-38-39-15-0A-00-24-00 30795 38231
34-57-36-31-38-39-0E-1D-00-1A-00 23009 40628
34-57-36-31-38-39-15-0E-00-09-00 17063 16242
34-57-33-31-35-39-04-10-00-20-00 31736 54522
34-57-33-31-35-39-04-18-00-1C-00  3760 10032
34-57-36-31-38-39-15-0E-00-0F-00 15527 14706
34-57-36-31-38-39-15-0E-00-13-00 10407  9586
34-57-36-31-38-39-15-0E-00-17-00  9383  8562
34-57-36-31-38-39-15-0E-00-1F-00 11431 10610
34-57-36-31-38-39-15-0A-00-25-00 30539 37975
00-00-00-00-00-00-00-00-00-00-00     0     0