algorithm - 判断一个数字是否属于某个组的算法

Question

我什至不确定这是否可能，但我认为无论如何都值得一问。

假设我们在一个网络中有 100 台设备。每台设备都有一个唯一的 ID。

我想告诉一组这样的设备通过只广播一个数据包(所有设备都接收到的数据包)来做某事。例如，如果我想告诉设备 2、5、75、116 和 530 做某事，我必须广播:2-5-75-116-530但是如果我想要(例如)95 个设备做某事，这个数据包会变得很长!!!所以我需要一种方法来减少这个数据包的长度。

想了想，想出了一个主意:

如果我只使用素数作为设备 ID 会怎样？然后我可以发送我需要的组的设备 ID 的乘积，因为数据包和每个设备都会检查接收到的数字及其设备 ID 的余数是否为 0。

例如，如果我想让设备 2、3、5 和 7 做某事，我会广播 2*3*5*7 = 210 然后每个设备将计算“210 mod self ID”并且只有 ID 为 2 的设备,3,5 和 7 将得到 0，因此他们知道他们应该做某事。

但这种方法效率不高，因为第 100 个素数是 541，广播的数字可能会变得非常大，“mod”计算可能会变得非常困难。(设备有 8 位处理器)。

所以我只需要一种方法让设备确定它们是否应该做某事或忽略接收到的数据包。而且我需要数据包尽可能短。

我已经尽力解释了这个问题，如果还是很模糊，请告诉我更多的解释。

Answer 1

您可以只使用一个位串，其中每个位代表一个设备。然后，您只需要按位 AND 来判断给定机器是否应该使用react。

每个设备需要一位，例如，256 个设备需要 32 个字节。不可否认，如果您只需要一台机器来使用react，那有点浪费，但如果您需要，比如说，95 台设备来使用react，那就相当紧凑了。

您提到您需要设备 ID <= 4 个字节，但这没问题:4 个字节 = 32 位 = 足够的空间来存储 2^32 个设备 ID。例如，第 101 台机器的设备 ID(如果您从 0 开始)可能只是 100 (0b01100100) = 1 字节。您只需要使用它来确定要使用数据包的哪个字节(ceil(100/8) = 第 13 个)以及该字节与 100 % 8 = 4 = 0b00000100。

---

作为cobarzan said ，您还可以使用允许单独寻址的混合方案。在这种情况下，您可以将第一位用作指示多机或单机寻址的信号。正如 cobarzan 所说，这需要更多的处理，这意味着第一个字节只能存储 7 个机器信号，而不是 8 个。