提问人：HappMacDonald 提问时间：10/29/2023 更新时间：10/29/2023 访问量：61
是否可以仅使用非按位运算来模拟按位算术“and”或“or”？
Can one emulate bitwise arithmetic "and" or "or" using only non-bitwise operations?
问：
想象一下，我们的任务是使用一个理想化的科学计算器，该计算器具有以下属性：
不直接支持按位运算或基数转换（例如，不能简单地“转换为”基数 2 或基数 16 等）
完全支持四种基本算术函数（+、-、*、/）
完全支持三角函数、对数、幂、根。为简单起见，我们可以假设 trig 函数只使用弧度。
支持括号和标准 PEMDAS 运算顺序
甚至完全支持以下分段函数
-- CEIL（迈向正无穷大）
-- floor（朝向负无穷大）
-- 截断（删除分数分量，例如四舍五入到零）
--绝对值
-- 符号（负数产生 -1，正数产生 +1，精确零产生零）
-- 模 （ 与 b*（a/b-floor（a/b）） 相同）
它可以处理 N 位有效数字的精度，其中 N 的大小并不是非常相关。我加入这个条件只是因为当我们不定义某种精度的有限界限时，数学会变得很奇怪。
计算器还可以将读数上的单个数字存储和调用到少数寄存器中，清除每个或所有寄存器，并清除显示。
我们的任务
是找出一种方法来计算任意两个任意非负整数的按位“和”或按位“或”或“，仅使用此计算器。
例如
按位“not”很容易通过以下表达式完成：
2^ceil（log（input+1）/log（2）） - 输入 - 1
这会反转输入值的每个二进制位，直到但不超过其最高有效位。
对于固定的恒定位宽，也可以执行相同的操作：
2^bitWidth - 输入 - 1
只要输入< 2^bitWidth
另一个例子
向更高有效位的位移位（又称位移左，假设最高有效位在前，左到写表示法）可以通过输入轻松处理*2
约束
- 我希望该解决方案涉及固定数量的步骤，这些步骤不会随着输入 O（1） 的大小而变化。特别是，必须在循环中提取和处理单个二进制数字是一座太远的桥梁。
宽松的约束
我们的算法可以自由地为无效输入呈现未定义的废话
输入必须为非负整数才能有效
我们简单地假设我们使用的计算器具有足够的精度来处理我们在尝试的任何大小的输入上尝试的任何数学运算，而不会屈服于浮点舍入误差
赋予动机
我知道所有经典的数学运算都可以只使用按位运算来计算。我正在努力确定是否可以证明相反的情况也有效。鉴于我可以执行“not”，我理解能够完成“and”⋀或能够完成“or”⋁应该为此后能够完成每个按位运算的排列开辟道路。:)
我尝试过简单加法的变体来实现“或”输出，但能够检测和/或纠正潜在的进位仍然让我在这种方法上受阻。 例如，a+b == a⋁b iff （a⋀b==0）。如果我能够检测到何时 （a⋀b！=0），和/或反转进位（从结果中减去 a⋀b*2），这可能会让我更接近一步。
答：
2赞
Spektre
10/29/2023
#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)
或者您可以使用 Karnough 映射仅使用 NAND 来实现任何逻辑功能......
0赞
Simon Goater
10/29/2023
#2
一个简单、合理高效且可移植的解决方案是使用查找表。如果不允许使用模运算符，则可以很容易地替换它，因为 A % B 等价于整数算术中的 A - B*（A/B），否则相当于 A - B*floor（A/B）。两个整数上的任何按位逻辑运算符都可以使用适当的查找表以这种方式计算。下面是如何在 32 位整数上模拟逻辑 OR 的示例。
uint32_t logicalOR(uint32_t A, uint32_t B) {
uint32_t res, Anibble, Bnibble;
uint8_t lut[16][16] = {....};
res = 0;
Anibble = A / 0x10000000;
Bnibble = B / 0x10000000;
res = lut[Anibble][Bnibble];
Anibble = (A / 0x1000000) % 16;
Bnibble = (B / 0x1000000) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = (A / 0x100000) % 16;
Bnibble = (B / 0x100000) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = (A / 0x10000) % 16;
Bnibble = (B / 0x10000) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = (A / 0x1000) % 16;
Bnibble = (B / 0x1000) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = (A / 0x100) % 16;
Bnibble = (B / 0x100) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = (A / 0x10) % 16;
Bnibble = (B / 0x10) % 16;
res = (res * 16) + lut[Anibble][Bnibble];
Anibble = A % 16;
Bnibble = A % 16;
res = (res * 16) + lut[Anibble][Bnibble];
return res;
}
评论
0赞
HappMacDonald
10/30/2023
不幸的是，这不符合我在问题的约束标题中列出的单个约束。我正在尝试找到一个解决方案，该解决方案不会随着输入大小的增加而增加其步骤数（或所需预先安排的数据的大小，因为此类预先安排的数据也需要使用步骤进行构造）。
评论
2^ceil(log(input+1)/log(2)) - input - 1