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

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 自身ID”，只有ID为2、3、5和7的设备才能得到0，所以它们知道该执行某些操作。

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

因此，我只需要一种方法让设备确定它们是否应该执行操作或忽略接收到的数据包。同时，我需要尽可能缩短数据包的长度。

我尽力解释了问题，如果还不清楚，请告诉我详细说明。

- Mehrad Moein

---

为什么不使用位串呢？每个位表示一个设备，你只需要进行按位 AND 运算即可确定给定的机器是否应该做出反应。每个设备需要一个位，例如256个设备就需要16个字节。如果只需要一个机器做出反应，这可能有些浪费，但如果需要95个设备做出响应，则相当紧凑。 - elixenide

13个字节对于100个设备来说已经相当高效了，但我在想是否有更紧凑的解决方案。另一个问题是对于第100个设备，设备ID应该是0b10000...00000（99个零）。我不能使用这个ID。设备ID最多可以占用4个字节。 - Mehrad Moein

设备 ID 可能只是 100（0b01100100 = 1 字节）。 您只需要使用该 ID 来确定要使用数据包的哪个字节（ceil(100 / 8) = 第 13 个字节），并对该字节按位进行 AND 运算以得到 100 % 8 = 4 = 0b00000100。4 字节 = 32 位 = 足够存储 2^32 设备 ID 的空间。 - elixenide

这正是我在寻找的。非常感谢。我该如何将您的评论标记为答案？ - Mehrad Moein

读者们可能会喜欢 Google Code Jam 的难题“充电混乱”。https://code.google.com/codejam/contest/2984486/dashboard#s=p0&a=0 - Colonel Panic

Answer 1

像Ed Cottrell建议的那样，一个位串可以完成这个任务。如果机器被标记为{1,..,n}，则有2ⁿ-1种可能的子集（假设您不发送没有目标的请求）。因此，您需要一个数据结构来保存此类子集的每个可能的签名，无论您决定签名是什么。并且对于这样的数据结构，n位（每台机器一位）是大小方面最好的。在机器上执行的评估需要恒定时间（对于标记为l的机器，只需查看第l位）。

但是，您可以采用混合方案。比如，如果您只有一个设备的任务，那么发送n位（除一个以外都为0）就太浪费了。因此，您可以取一个附加位T，它表示数据包的类型。如果您像上面描述的那样发送长度为n的位串，则T的值设置为0；如果您使用更合适的方案（即使用更少的位数），则将其设置为1。如果只有一台机器需要执行任务，则可以直接发送该机器的标签（长度为O(log n)位）。如果您需要执行任务的机器少于O(n/log n)台，则此方法可以减小数据包的大小。但是，在机器上执行评估会更加昂贵。

- cobarzan

---

+1 为混合方案。我想到了这个，但不确定如何最好地解释它。你的解释非常好。 - elixenide

Answer 2

你可以使用一个位字符串，其中每个位表示一个设备。然后，您只需要进行按位 AND 操作即可判断给定的机器是否应该响应。

您需要为每个设备使用一个位，例如，256 个设备需要 32 字节。诚然，如果您只需要一个机器响应，那么这有点浪费，但是如果您需要 95 个设备响应，那么它非常紧凑。

您提到需要设备 ID <= 4 字节，但这不是问题：4 字节 = 32 位 = 足够存储 2^32 设备 ID 的空间。例如，第 101 台机器的设备 ID（如果从 0 开始）可以是100 (0b01100100) = 1 字节。您只需要使用它来确定要使用数据包的哪个字节(ceil(100 / 8) = 第 13 个)并对该字节进行按位 AND 操作以得出 100 % 8 = 4 = 0b00000100。

---

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

- elixenide