可以仅使用非按位运算来模拟按位算术“与”或“或”吗？

Question

想象我们的任务是使用一个理想化的科学计算器，它具有以下属性：

• 不直接支持按位运算或基数转换（例如不能简单地“转换为”基数 2 或基数 16 等）

• 全面支持四种基本算术函数（+、-、*、/）

• 完全支持三角函数、对数、指数、根。为了简单起见，我们可以假设三角函数仅使用弧度。

• 支持括号和标准 PEMDAS 运算顺序

• Even 完全支持以下分段函数

-- ceil （朝向正无穷大）

-- 下限（向负无穷大）

-- 截断（去掉小数部分，例如向零舍入）

--绝对值

-- 符号（负数产生 -1，正数产生 +1，精确的零产生零）

-- 模（与 b*(a/b-floor(a/b)) 相同）

• 它可以处理 N 位有效数字的精度，其中 N 的大小并不是非常相关。我加入这个附带条件只是因为当我们没有定义某种有限的精度界限时，数学可能会变得很奇怪。

• 计算器还可以将读数上的各个数字存储和调用到几个寄存器中，清除每个或所有寄存器，并清除显示。

我们的任务

是找出一种仅使用此计算器计算任意两个任意非负整数的按位“与” 或 按位“或”的方法。

例如

按位“not”很容易通过以下表达式完成：

2^ceil(log(输入+1)/log(2)) - 输入 - 1

反转输入值的每个二进制位，直到但不超过其最高有效位。

对于固定不变的位宽度也可以做同样的事情：

2^bitWidth - 输入 - 1

只要输入< 2^bitWidth

另一个例子

可以通过输入*2轻松处理向更高有效位的按位移位（也称为左移位，假设最高有效位在前并且向左写入符号）

约束

我希望解决方案涉及固定数量的步骤，这些步骤不会随着输入 O(1) 的大小而变化。特别是必须在循环中提取和处理单个二进制数字是一座太过遥远的桥梁。

宽松的约束

• 我们的算法可以自由地为无效输入呈现未定义的废话

• 输入必须为非负整数才有效

• 我们将简单地假设我们使用的计算器有足够的精度来处理我们在任何大小的输入上尝试的任何数学运算，而不会屈服于浮点舍入误差

动机

我知道所有经典数学运算都可以仅使用按位运算来计算。我正在努力确定相反的方法是否也能发挥作用。鉴于我可以执行“不”，我明白无论是能够完成“与”⋀还是能够完成“或”⋁，都应该为之后能够完成按位运算的每个排列开辟道路。 :)

我已经尝试过简单加法的变体来实现“或”输出，但是能够检测和/或纠正潜在的进位仍然阻碍了我这种方法。 例如 a+b == a⋁b 当且仅当 (a⋀b==0)。我是否能够检测何时 (a⋀b!=0)，和/或反转进位（从结果中减去 a⋀b*2），这可以让我更近一步。

Answer 1

嗯，这让我想起了可能几个月前发布的一个问题，关于使用算术函数来执行逻辑函数，但懒得寻找它......

您可以像这样提取

b

的二进制数字

b0 = x%1
b1 = (x/2)%1
b2 = (x/4)%1
...

并重建回来：

b = b0 + 2*b1 + 4*b2 + ... 现在你可以像这样计算

c = a AND b

：

c0 = a0*b0
c1 = a1*b1
c2 = a2*b2
...
c = c0 + 2*c1 + 4*c2 + ...

现在您已经实现了 AND 和 NOT，因此您可以使用

德摩根定律 来使用 NAND 实现任何逻辑函数...

NOT(A OR  B) = NOT(A) AND NOT(B)
NOT(A AND B) = NOT(A) OR  NOT(B)