IBM Ponder This #140 · 2009 年 12 月

设 x 是一个可带前导零的 25 位二进制数。用 & 表示按位与，对以下十个十六进制掩码 m_i，计算 i=1,…,10 的 (x & m_i) 的乘积：

0x1f, 0x3e0, 0x7c00, 0xf8000, 0x1f00000,
0x108421, 0x210842, 0x421084, 0x842108, 0x1084210

依官方 12 月 4 日修订，该乘积必须是某个质数的非平凡整数次幂，即底数为质数、指数为大于 1 的整数。最初题面只写一般整数幂，这一较宽条件已被更正。

一个“掩码问题”指定 m，并询问 (x & m) 是否为零。最少需要多少个这样的问题才能确定 x？

原题给出性质：若候选集合至多含四个 x，就可以再用两个掩码问题区分。请给出一个预先固定的 N-2 个掩码的序列，使其联合答案把全部候选划分为大小至多为四的子集；这些问题不能依赖先前答案。最后两个问题可以依前面结果选取，不必列出。

12 月 9 日进一步明确，x 的最高位不必为 1。

解答

认真尝试后再打开

待补充。