n位二进制数删位识别算法：剩余n-1位数能否指示删除位？

核心结论 #

当且仅当n为奇数时，存在满足需求的对应关系；当n为偶数时，不存在这样的对应关系（例如n=2时，二进制数01无法找到合法删位：删掉0得到1需对应0，删掉1得到0需对应1，这会与00/11的需求矛盾）。

具体构造方法（n为奇数） #

设m = n-1（m为偶数），我们可以基于二进制数中1的数量进行分组：

1. 定义映射函数f：对于任意m位二进制数s：
   • 若s中1的个数 ≥ m/2，则f(s) = 1（表示被删除的位是1）；
   • 若s中1的个数 < m/2，则f(s) = 0（表示被删除的位是0）。
2. 对于任意n位二进制数T：
   • 统计T中0的个数a和1的个数b，由于n是奇数，a ≠ b：
     • 若b > a（1的数量更多）：b ≥ (n+1)/2，删除任意一个1后得到s，s中1的个数为b-1 ≥ (n+1)/2 -1 = (n-1)/2 = m/2，因此f(s)=1，与被删除的位类型一致；
     • 若a > b（0的数量更多）：b ≤ (n-1)/2 -1 = m/2 -1，删除任意一个0后得到s，s中1的个数仍为b < m/2，因此f(s)=0，与被删除的位类型一致。

示例验证（n=7，用户案例） #

• 原n位二进制数：0110101，其中1的个数为4，0的个数为3（b > a）；
• 删除第2位（1）后得到m位二进制数：010101，其中1的个数为3，恰好等于m/2=3，因此f(s)=1，准确指示被删除的位是1，符合需求。

内容的提问来源于stack exchange，提问作者Tiago Miguel Sousa