Mathematical equation for and bitwise operation And?

Question

In a shift operation, for example,

5 << 1 = 10

10 << 1 = 20

then you can make a mathematical equation,

n << 1 = n * 2.

If there is an equation for the left shift operation,

is it possible that there is also

mathematical equation for AND operation?

or any other bitwise operators?

Answer 1

There is no simple simple operation that maps to each bitwise operation. However, they can be modeled using iterative tools (or one very long formula).

 (a & b) 

can be done using

 (((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) 

Where n is 2 the number of bits making up A and B minus one. This assumes integer division (the remainder is discarded).

Answer 2

It depends on what you mean by a "mathematical equation." There is no simple arithmetic.

If you look at it from a formal number-theoretic point of view, you can describe bitwise "and" (and "or" and "xor") using only addition, multiplication and - and this is quite large "and" in terms of perspective " - The logic of first-order predicates, but this is certainly not what you had in mind, not least because these tools are enough to describe everything that a computer can do.

Answer 3

Except in special circumstances, it is not possible to describe bitwise operations in other mathematical operations.

An and the operation with 2 ⁿ -1 is the same as the operation of the module with 2 ⁿ . An and the inverse 2 ⁿ -1 operation can be considered as dividing by 2 ⁿ truncating and multiplying by the same thing.

Answer 4

It depends on what you mean by “math.” If you are looking for simple school algebra, then the answer is no. But mathematics is not sacred - mathematicians always define new operations and concepts.

For example, you can represent 32-bit numbers as vectors of 32 logical elements, and then define the “AND” operation on them, which performs standard logical “and” between the corresponding elements.

Answer 5

Here is the proof that for two-bit bitwise operations you cannot describe & with just + - and * (check this out, just come up with it now, so who knows):

The question is, is it possible to find a polynomial

 x & y == P(x, y) 

Where

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

Here's what it would look like:

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

Firstly, a0_0 == 0 clear. Then you can see that if P rewritten:

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

And y held at 0, and x changed to 0, 1, 2, 3; then Q (x, y) must be 0 for each of these values. Similarly, if x held at 0 and y changes. So Q(x, y) can be set to 0 without loss of generality.

But now, since P(2, 2) = 2 , but 2 * 2 == 0 , the polynomial P cannot exist.

And, I think, it will generalize and more bits.

So the answer is: if you are only looking for + , * and - , you cannot do it.

Answer 6

Yes, these are amounts. Consider a binary word of length n. It can be written as follows; A = a0 * 2 ^ 0 + a1 * 2 ^ 1 + a2 * 2 ^ 3 .... * 2 ^ n. Where a is an element from {0,1}

Therefore, if an is a bit in and bn is a bit in B, then; AandB = a0 * b0 * 2 ^ 0 + a1 * b1 * 2 ^ 1 ... * bn * 2 ^ n by the analogy of AxorB = (a0 + b0) mod 2 * 2 ^ 0 + (a1 + b1) mod 2 * 2 ^ 1 ... + (an + bn) mod 2 * 2 ^ n

Consider now the identity; Axor1 = NOTA

Now we have the three operators we need (Bitwise AND, Bitwise XOR and Bitwise NOT)

From these two we can do whatever we want.

For example, bitwise OR

not [(NOTA) and (notB)] = no [no (AorB)] = AorB

It is not guaranteed that he will be good.

In response to the comment regarding arithmetic mod2 is not very simple, it is true in a sense. However, despite the fact that it is widespread due to the prevalence of computers at the present time, the whole subject that we touch on here is not particularly "basic". The OP understood something fundamental. In a mathematical field known as "Abstract Algebra", such as addition and multiplication modulo n (where n is a number, such as 2, 8 or 2 ^ 32), finite algebraic structures are studied. There are other structures that use binary operations (adding is a binary operation, it takes two operands and produces the result, like multiplication and xor), such as xor, and bit shifts, etc., which are "isomorphic" to adding and multiplication over integers mod n. this means that they act the same way, they are associative, distributive, etc. (although they may or may not be commutative, think about matrix multiplication). It's hard to tell someone where to start looking for additional information. I think the best way is to start with a book on official math. (Mathematical evidence). You need this to understand any advanced math text. Then text on abstract algebra. If you learn a large computer, you will get a lot of things in your classes. If your mathematician is a major, you will study these things in the depths of everything in advance. If your historical major, I do not knock history, I am a history channel addict, but you have to switch majors because you spend your talents!