按位间隔算法

Question

我最近在D新闻组上读了一个有趣的帖子,基本上要求,

给定两个(签署)整数一个 ∈[ 一_分钟,一_最大值 ],b ∈[ b _分钟,b _最大值 ],什么是最紧密的间隔一个 | b？

我认为如果区间算术可以应用于一般的位运算符(假设无限位).按位NOT和移位是微不足道的,因为它们只对应于-1- x和2 ⁿ x.但由于按位和算术属性的混合,按位-AND/OR更加棘手.

是否有多项式时间算法来计算按位AND/OR的间隔？

---

注意:

• 假设所有按位运算都以线性时间(位数)运行,并且测试/设置位是恒定时间.
• 蛮力算法以指数时间运行.
• 因为~(a | b) = ~a & ~b,解决按位AND和-NOT问题意味着按位OR完成.
• 虽然该线程的内容表明min { a | b } = max(a _min,b _min),它不是最严格的约束.考虑一下[2, 3] | [8, 9] = [10, 11].)
• 实际上处理无符号算术就足够了,因为我们可以将一个有符号的区间分成负的和非负的子集,并且使用de Morgan定律和交换性只需要解决非负区间的按位AND,-OR和-AND-NOT情况.

Answer 1

对于非负整数的区间 [a _min , a _{max ]，我们可以计算按位最小值 a 0}，其中只要区间内可能，位就会独立设置为 0。类似地，我们可以计算按位最大值 a ₁，其中在区间内尽可能多的位被设置为 1。对于 [b _min , b _max ]，我们执行相同的操作并得到 b ₀和 b ₁。那么结果区间就是[a ₀ | 0 , ₁ |_​ b ₁ ]。

_{很容易从 [a min} , a _max ]中检查 a 可以采用哪些值。对于位 n，如果 m >= n 的所有位 m 在最小值_和最大值_中一致，则该值被强制，否则它可以是 0 或 1。

这可以在 O(n) 内完成。

签名的案例留给读者作为练习。第一步是提供按位运算符对负整数的含义的定义。

编辑：不幸的是，这是错误的：考虑 [a _min , a _max ] = [b _min , b _max ] = [1,2]的情况。那么a | b可以是 1、2 或 3，但按位最小值为 0。