математическое уравнение для битовой операции И?

Question

Например, в операции сдвига влево:

5 << 1 = 10

10 << 1 = 20

, тогда можно сделать математическое уравнение,

n << 1 = n * 2.

Если существует уравнение для операции сдвига влево,

, тогда возможно ли, что для операции AND также существует математическое уравнение

?

или любые другие побитовые операторы?

Answer 1

Не существует простой операции, которая сопоставлялась бы с каждой побитовой операцией. Однако все они могут быть смоделированы с помощью итерационных средств (или одной действительно длинной формулы).

(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, минус один. Это предполагает целочисленное деление (остаток отбрасывается).

Answer 2

Это зависит от того, что вы подразумеваете под «математическим уравнением». Нет простого арифметического.

Если вы посмотрите на это с формальной теории чисел, вы можете описать побитовые "и" (и "или" и "xor"), используя только сложение, умножение и И это довольно большое «и» с точки зрения мирян - логика предикатов первого порядка. Но это, безусловно, не то, что вы имели в виду, не в последнюю очередь потому, что этих инструментов достаточно, чтобы описать все, что может сделать компьютер вообще.

Answer 3

За исключением особых обстоятельств, невозможно описать побитовые операции в других математических операциях.

Операция с 2 ⁿ -1 аналогична операции с модулем с 2 ⁿ . Операцию and с обратным 2 ⁿ -1 можно рассматривать как деление на 2 ⁿ , усечение и умножение на одно и то же.

Answer 4

Да, это суммы. Рассмотрим для двоичного слова длины n. Это можно записать следующим образом; A = a0 * 2 ^ 0 + a1 * 2 ^ 1 + а2 * 2 ^ 3 .... * 2 ^ п. Где an является элементом {0,1}

Следовательно, если an - бит в A, а bn - бит в B, то; AandB = a0 * b0 * 2 ^ 0 + a1 * b1 * 2 ^ 1 ... * млрд * 2 ^ п так же AxorB = (a0 + b0) mod 2 * 2 ^ 0 + (a1 + b1) mod 2 * 2 ^ 1 ... + (ап + Ьп) mod 2 * 2 ^ п

Рассмотрим теперь личность; Axor1 = NOTA

Теперь у нас есть три оператора, которые нам нужны (побитовое И, побитовое XOR и побитовое НЕ)

Из этих двух мы можем сделать все, что захотим.

Например, побитовое ИЛИ

* 1012 не * [(NOTA) и (notB)] = нет [нет (AorB)] = AorB

Хотя это не гарантированно будет красиво.

В ответ на комментарий о том, что арифметика mod2 не является базовой, это в некотором смысле верно. Однако, несмотря на то, что в настоящее время это широко распространено из-за преобладания компьютеров, весь предмет, который мы здесь затрагиваем, не является особенно «базовым». ОП понял что-то фундаментальное. Существуют конечные алгебраические структуры, изучаемые в математической области, известной как «Абстрактная алгебра», такой как сложение и умножение по модулю n (где n - это некоторое число, такое как 2, 8 или 2 ^ 32). Существуют другие структуры, использующие бинарные операции (сложение - это двоичная операция, она принимает два операнда и дает результат, как умножение и xor), такие как xor, сдвиги битов и т. Д., Которые «изоморфны» сложению и умножению. над целыми числами мод n. это означает, что они действуют одинаково, они ассоциативны, распределительны и т. д. (хотя они могут или не могут быть коммутативными, подумайте о умножении матриц) Трудно сказать кому-то, с чего начать искать дополнительную информацию. Я думаю, что лучшим способом было бы начать с книги по формальной математике. (Математические доказательства). Вам это нужно, чтобы понять любой сложный математический текст. Затем текст по абстрактной алгебре. Если вы являетесь специалистом в области компьютерных наук, вы многое узнаете на своих занятиях. Если вы изучаете математику, вы будете изучать эти вещи в свое время. Если вы майор истории, я не стучу по истории, я наркоман канала истории, но вам следует сменить специализацию, потому что вы тратите свои таланты!

Answer 5

Вот доказательство того, что для 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 не может есть.

И, я думаю, это будет обобщаться и на большее количество битов.

Таким образом, ответ таков: если вы ищете только +, * и -, нет, вы не можете сделать это.

Answer 6

Это зависит от того, что вы подразумеваете под «математическим».Если вы ищете простую школьную алгебру, то ответ - нет.Но математика не является священной - математики постоянно определяют новые операции и концепции.

Например, вы можете представить 32-битные числа как векторы 32 логических значений, а затем определить операцию «И» над ними, которая выполняет стандартныелогическое «и» между соответствующими элементами.