AND按位运算的数学方程?

例如,在左移操作中,

5 << 1 = 10

10 << 1 = 20

然后可以建立一个数学方程,

n << 1 = n * 2.

如果存在左移操作的等式,

那么有可能还有一个

AND运算的数学方程?

或任何其他按位运算符?

没有直接的单个操作映射到每个按位操作。 但是,它们都可以通过迭代手段(或一个非常长的公式)进行模拟。

 (a & b) 

可以完成:

 (((a/1 % 2) * (b/1 % 2)) * 1) + (((a/2 % 2) * (b/2 % 2)) * 2) + (((a/4 % 2) * (b/4 % 2)) * 4) + ... (((a/n % 2) * (b/n % 2)) * n) 

其中n是2,即A和B组成的位数减1。 这假设整数除法(余数被丢弃)。

这取决于你对“数学方程”的意思。 没有简单的算术算法。

如果从正式的数论理论角度来看,你可以只使用加法乘法描述“和”(以及“或”和“xor”) – 这是一个相当大的“和” – 一阶谓词逻辑。 但这肯定不是你的意思,尤其是因为这些工具足以描述计算机可以做的任何事情

除特定情况外,不可能在其他数学运算中描述按位运算。

具有2 n -1的操作和操作与具有2 n的模数操作相同。 具有2 n -1的逆的操作和操作可被视为2 n的除法,截断和相乘。

这取决于你对“数学”的意思。 如果你正在寻找简单的学校代数,那么答案就是否定的。 但数学并不神圣 – 数学家一直在定义新的操作和概念。

例如,您可以将32位数字表示为32个布尔值的向量,然后在它们上定义“AND”运算,它们在它们对应的元素之间执行标准布尔“和”。

这是一个certificate,对于2位按位运算,你无法用+ -*来描述&检查一下 ,现在就想出来了,所以,谁知道):

问题是,我们能找到多项式吗?

 x & y == P(x, y) 

哪里

 P(x, y) = a0_0 + a1_0*x + a0_1*y + a2_0*x^ + ... 

这是它的样子:

  0 1 2 3 -------- 0| 0 0 0 0 1| 0 1 0 1 2| 0 0 2 2 3| 0 1 2 3 

首先,显然a0_0 == 0 。 接下来你可以看到如果P被重写:

  |------- Q(x, y) --------| P(x, y) = xy*R(x,y) + a1_0*x + a0_1*y + ... 

并且y保持为0,而x在0,1,2,3之间变化; 那么每个值的Q(x,y)必须为0。 同样,如果x保持为0且y变化。 所以Q(x, y)可以设置为0而不失一般性。

但是现在,由于P(2, 2) = 2 ,但是2 * 2 == 0 ,因此多项式P不存在。

而且,我认为这也会推广到更多位。

所以答案是,如果你只是寻找+*- ,不,你不能这样做。

是的,它们是总和。 考虑长度为n的二进制字。 它可以写成如下; A = A0 * 2 ^ 0 + A1 * 2 ^ 1 + A 2 * 2 ^ 3 ….的* 2 ^ N。 其中a是{0,1}的元素

因此,如果a是A中的位而bn是B中的位,那么; AandB = a0 * b0 * 2 ^ 0 + a1 * b1 * 2 ^ 1 … a * bn * 2 ^ n类似地AxorB =(a0 + b0)mod2 * 2 ^ 0 +(a1 + b1)mod2 * 2 ^ 1 … +(一个+ BN)模2 * 2 ^ N

现在考虑身份; Axor1 = NOTA

我们现在有三个运算符(Bitwise AND,Bitwise XOR和Bitwise NOT)

从这两个我们可以做任何我们想要的。

例如,按位OR

不[(NOTA)和(notB)] =未[否(AorB)] = AorB

虽然它不能保证很漂亮。

在回应关于mod2算术的评论不是很基本时,这在某种意义上是正确的。 然而,虽然现在由于计算机普及而常见,但我们在这里所涉及的整个主题并不是特别“基本”。 OP已经掌握了一些基本的东西。 在称为“抽象代数”的数学领域中研究了有限代数结构,例如加法和乘法模n(其中n是某些数,例如2,8或2 ^ 32)。 还有其他结构使用二进制运算(加法是二进制运算,它需要两个操作数并产生一个结果,如乘法和xor),如xor,和位移等,它们与加法和乘法“同构”整数模型 这意味着它们的行为方式相同,它们是联想的,分配的等等(虽然它们可能是也可能不是可交换的,但想到矩阵乘法)很难告诉别人从哪里开始寻找更多信息。 我想最好的方法是从一本关于正式数学的书开始。(数学certificate)你需要它来理解任何高级数学文本。 然后是关于抽象代数的文本。 如果你是计算机科学专业,你将在课堂上获得很多。 如果你是一名数学专业的学生,​​你将在适当的时候深入学习这些东西。 如果你是一个历史专业,我不是历史,我是一个历史频道瘾君子,但你应该切换专业,因为你浪费你的才能!