Xor through basic operations. Basic logical operations (and, or, xor, not)

In this article I will tell you how bit operations work. At first glance, they may seem complicated and useless to you, but in reality this is not at all the case. This is what I will try to convince you of.

Introduction

Bitwise operators operate directly on the bits of a number, so the numbers in the examples will be in binary.

I will cover the following bitwise operators:

• | (Bitwise OR),
• & (Bitwise AND (AND)),
• ^ (Exclusive OR (XOR)),
• ~ (Bitwise Negation (NOT)),
• << (Побитовый сдвиг влево),
• >> (Bitwise shift right).

Bit operations are studied in discrete mathematics, and also form the basis of digital technology, since the logic of the operation of logic gates, the basic elements of digital circuits, is based on them. In discrete mathematics, as in digital engineering, truth tables are used to describe their operation. Truth tables, it seems to me, greatly facilitate the understanding of bit operations, so I will present them in this article. They are, however, almost never used in explanations of bitwise operators in high-level programming languages.

You also need to know about bit operators:

1. Some bitwise operators are similar to the operators you're probably familiar with (&&, ||). This is because they are actually similar in some ways. However, they should not be confused under any circumstances.
2. Most bit operations are compound assignment operations.

Bitwise OR

Bitwise OR operates equivalent to logical OR, but applied to each pair of bits of a binary number. The binary bit of the result is 0 only when both corresponding bits in are 0. In all other cases, the binary result is 1. That is, if we have the following truth table:

38 | 53 will be like this:

As a result, we get 110111 2, or 55 10.

Bitwise AND

Bitwise AND is sort of the opposite operation of bitwise OR. The binary digit of the result is 1 only when both corresponding bits of the operands are equal to 1. In other words, we can say that the binary digits of the resulting number are the result of multiplying the corresponding bits of the operand: 1x1 = 1, 1x0 = 0. The following truth table corresponds to the bitwise AND:

An example of bitwise AND working on the expression 38 & 53:

As a result, we get 100100 2, or 36 10.

You can use the bitwise AND operator to check whether a number is even or odd. For integers, if the least significant bit is 1, then the number is odd (based on binary to decimal conversion). Why is this necessary if you can just use %2? On my computer, for example, &1 runs 66% faster. Quite a nice performance boost, let me tell you.

Exclusive OR (XOR)

The difference between XOR and bitwise OR is that to produce a 1, only one bit in a pair can be a 1:

For example, the expression 138^43 will be equal to...

… 10100001 2, or 160 10

Using ^ you can change the values ​​of two variables (having the same data type) without using a temporary variable.

You can also encrypt text using exclusive OR. To do this, you just need to iterate through all the characters, and ^ them with the key character. For a more complex cipher, you can use a string of characters:

String msg = "This is a message"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }

XOR is not the most secure encryption method, but it can be made part of the encryption algorithm.

Bitwise negation (NOT)

Bitwise negation inverts all bits of the operand. That is, what was 1 will become 0, and vice versa.

For example, here is operation ~52:

The result will be 203 10

When using bitwise negation, the sign of the result will always be the opposite sign of the original number (when working with signed numbers). Find out why this happens right now.

Additional code

Here I should tell you a little about the way to represent negative integers in a computer, namely about the two’s complement code. Without going into details, it is needed to facilitate the arithmetic of binary numbers.

The main thing you need to know about numbers written in two's complement is that the most significant bit is signed. If it is 0, then the number is positive and coincides with the representation of this number in direct code, and if 1, then it is negative. That is, 10111101 is a negative number, and 01000011 is a positive number.

To convert a negative number to its two's complement, you need to invert all the bits of the number (essentially using bitwise negation) and add 1 to the result.

For example, if we have 109:

With the above method we get -109 in two's complement code.
A very simplified explanation of additional code has just been presented, and I strongly encourage you to study this topic in more detail.

Bitwise shift left

Bit shifts are slightly different from the bit operations discussed earlier. A bitwise left shift shifts the bits of its operand N number of bits to the left, starting with the least significant bit. Empty spaces after the shift are filled with zeros. It happens like this:

An interesting feature of shifting left by N positions is that it is equivalent to multiplying the number by 2 N . So 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Bitwise shift right

As you might guess, >> shifts the bits of the operand by a specified number of bits to the right.

If the operand is positive, then the empty spaces are filled with zeros. If we initially work with a negative number, then all the empty spaces on the left are filled with ones. This is done to preserve the sign according to the additional code explained earlier.

Since bitwise shift right is the opposite operation of bitwise shift left, it is easy to guess that shifting a number to the right by N number of positions also divides that number by 2 N . Again, this is much faster than normal division.

Conclusion

So now you know more about bit operations and are not afraid of them. I can assume that you will not use >>1 every time you divide by 2. However, bit operations are good to have in your arsenal, and now you can use them if necessary or answer a tricky interview question.

Often, in order to demonstrate the limited capabilities of single-layer perceptrons when solving problems, they resort to considering the so-called problem XOR – exclusive OR.

The essence of the task is as follows. The logical function XOR is given - exclusive OR. It is a function of two arguments, each of which can be zero or one. It takes the value , when one of the arguments is equal to one, but not both, otherwise . The problem can be illustrated using a single-layer, single-neuron, two-input system, shown in the figure below.

Let us denote one input by , and the other by , then all their possible combinations will consist of four points on the plane. The table below shows the required relationship between inputs and output, where input combinations that should produce a zero output are labeled and , a single output is labeled and .

One neuron with two inputs can form a decision surface in the form of an arbitrary straight line. In order for the network to implement the XOR function specified in the table above, you need to position the line so that the points are on one side of the line, and the points are on the other. Having tried to draw such a straight line in the figure below, we are convinced that this is impossible. This means that no matter what values ​​are assigned to the weights and threshold, a single-layer neural network is unable to reproduce the relationship between input and output required to represent the XOR function.

However, the XOR function is easily formed by a two-layer network, and in many ways. Let's consider one of these methods. Let's modernize the network in the figure by adding another hidden layer of neurons:

Note that this network given as is, i.e. we can assume that she has already been trained. The numbers above the arrows show the values ​​of synaptic weights. As an activation function, we will use a single jump function with a threshold having the following graph:

Then the result of the operation of such a neural network can be presented in the form of the following table:

Each of the two neurons of the first layer forms a decision surface in the form of an arbitrary straight line (divides the plane into two half-planes), and the neuron of the output layer combines these two solutions, forming a decision surface in the form of a strip formed by parallel straight lines of the neurons of the first layer:

The neural network used in this article to solve the XOR problem is primitive and does not take full advantage of the capabilities of multilayer networks. Obviously, multilayer neural networks have greater representing power than single-layer ones only in the presence of nonlinearity. And in this network, a threshold linear activation function is applied. Such a network cannot be trained, for example, using a backpropagation algorithm.

Absolutely all digital microcircuits consist of the same logical elements - the “building blocks” of any digital node. That's what we'll talk about now.

Logic element- This is a circuit that has several inputs and one output. Each state of the signals at the inputs corresponds to a specific signal at the output.

So what are the elements?

Element “AND”

Otherwise it is called “conjunctor”.

In order to understand how it works, you need to draw a table that lists the output states for any combination of input signals. This table is called " truth table" Truth tables are widely used in digital technology to describe the operation of logic circuits.

This is what the “AND” element and its truth table look like:

Since you will have to communicate with both Russian and bourgeois tech. documentation, I will provide symbolic graphic symbols (GID) of elements both according to our and non-our standards.

We look at the truth table and clarify the principle in our brain. It is not difficult to understand: a unit at the output of the “AND” element occurs only when units are supplied to both inputs. This explains the name of the element: units must be on BOTH one AND the other input.

If we look at it a little differently, we can say this: the output of the “AND” element will be zero if zero is applied to at least one of its inputs. Let's remember. Let's move on.

OR element

In another way, he is called a “disjunctor”.

We admire:

Again, the name speaks for itself.

A unit appears at the output when a unit is applied to one OR to the other OR to both inputs at once. This element can also be called the “AND” element for negative logic: a zero at its output occurs only if zeros are supplied to both one and the second input.

NOTE element

More often, it is called an “inverter”.

Do I need to say anything about his work?

NAND element

The NAND gate works exactly the same as the AND gate, only the output signal is completely opposite. Where the “AND” element should have a “0” output, the “AND-NOT” element should have a one. And vice versa. This is easy to understand from the equivalent circuit of the element:

Element "NOR" (NOR)

The same story - an “OR” element with an inverter at the output.

The next comrade is a little more cunning:
Exclusive OR element (XOR)

He's like this:

The operation it performs is often called "addition modulo 2". In fact, digital adders are built on these elements.

Let's look at the truth table. When is the output unit? Correct: when the inputs have different signals. On one - 1, on the other - 0. That's how cunning he is.

The equivalent circuit is something like this:

It is not necessary to memorize it.

Actually, these are the main logical elements. Absolutely any digital microcircuits are built on their basis. Even your favorite Pentium 4.

And finally, several microcircuits containing digital elements. The numbers of the corresponding legs of the microcircuit are indicated near the terminals of the elements. All chips listed here have 14 legs. Power is supplied to legs 7 (-) and 14 (+). Supply voltage – see the table in the previous paragraph.

Indicated by the figure of speech “either... or...” The compound statement “either A or B” is true when either A or B is true, but not both; V otherwise the compound statement is false.

Those. the result is true (equal to 1), If A is not equal to B (A≠B).

This operation is often compared to disjunction because they are very similar in properties, and both have similarities to the conjunction “or” in everyday speech. Compare the rules for these operations:

1. true if true or , or both at once.

2. true if true or, But Not both at once.

Operation excludes the latter option (“both at once”) and for this reason is called exclusive “OR”. Ambiguity natural language is that the conjunction “or” can be used in both cases.

5. Implication (logical consequence) is formed by combining two statements into one using the figure of speech “if ... then ....”.

Recording: A®B

A compound statement formed by the operation of implication is false if and only if a false conclusion (second statement) follows from a true premise (the first statement).

Those. if 1 implies 0, then the result is 0, in other cases – 1.

For example, the statement “If a number is divisible by 10, then it is divisible by 5” is true because both the first and second statements are true.

The statement “If a number is divisible by 10, then it is divisible by 3” is false because a false conclusion is drawn from a true premise.

"This quadrilateral is a square" (A) And "A circle can be circumscribed around a given quadrilateral" (IN). Then the compound statement reads as “If a given quadrilateral is a square, then a circle can be drawn around it.”

In ordinary speech the connective "if... then" describes the cause-and-effect relationship between statements. But in logical operations the meaning of statements is not taken into account. Only their truth or falsity is considered. Therefore, one should not be embarrassed by the “meaninglessness” of implications formed by statements that are completely unrelated in content. For example, like this: “if the President of the United States is a Democrat, then there are giraffes in Africa,” “if a watermelon is a berry, then there is gasoline in the gas station.”

6. Equivalence (logical equality, ~ º Û) is formed by combining two statements into one using the figure of speech “...if and only if...”

A compound statement formed by an equivalence operation is true if and only if both statements are simultaneously either false or true.

For example, the statements “A computer can compute if and only if it is turned on” and “A computer cannot compute if and only if it is not turned on” are true because both simple statements are simultaneously true.

Truth tables

For each compound statement (logical function), it is possible to construct a truth table that determines its truth or falsity for all possible combinations of the initial values ​​of simple statements.

Truth table this is a table view logic circuit(operations), which lists all possible combinations of the truth values ​​of the input signals (operands) along with the truth value of the output signal (result of the operation) for each of these combinations.

Let us reflect the above discussed logical operations in the truth table:

In propositional algebra, all logical functions by logical transformations can be reduced to three basic ones: logical addition, logical multiplication and logical negation.

Let us prove that the implication operation A®B is equivalent to the logical expression:

The operation exclusive OR (non-equivalence, addition modulo two) is denoted by a symbol and differs from logical OR only when A=1 and B=1.

Thus, the disparity of two statements X1 and X2 is called a statement Y that is true if and only if one of these statements is true and the other is false.

The definition of this operation can be written in the form of a truth table (Table 6):

Table 6 – Truth table of the “EXCLUSIVE OR” operation

As can be seen from Table 6, the logic of the element’s operation corresponds to its name.

This is the same “OR” element with one small difference. If the value at both inputs is equal to a logical one, then the output of the “EXCLUSIVE OR” element, unlike the “OR” element, is not one, but zero.

The EXCLUSIVE OR operation actually compares two binary digits for a match.

Each logical connective is considered as an operation on logical statements and has its own name and designation (Table 7).

Table 7 - Basic logical operations

1. The order of logical operations in a complex logical expression

The system of logical operations of inversion, conjunction, and disjunction allows you to construct arbitrarily complex logical expression.

When calculating the value of a logical expression, a certain order of logical operations is adopted.

1. Inversion.

2. Conjunction.

3. Disjunction.

4. Implication.

5. Equivalence.

Parentheses are used to change the specified order of operations.

1. Logical Expressions and Truth Tables

   1. Boolean expressions

Each compound statement can be expressed in the form of a formula (logical expression), which includes logical variables, denoting statements, and signs of logical operations, denoting logical functions.

To write a compound statement in the form of a logical expression in a formal language (the language of algebra of logic), in a compound statement it is necessary to identify simple statements and logical connections between them.

Let us write in the form of a logical expression the compound statement “(2·2=5 or 2∙2=4) and (2∙2≠5 or 2∙ 2 ≠4)".

Let's analyze the compound statement. It contains two simple statements:

A = “2 2=5” - false (0),

B = “2 2=4” - true (1).

Then the compound statement can be written in the following form:

«( AorIN) and (Ā orIN)».

Now you need to write the statement in the form of a logical expression, taking into account the sequence of logical operations. When performing logical operations, the following order of their execution is defined:

inversion, conjunction, disjunction.

Parentheses can be used to change the specified order:

F = (AvIN) & (Ā vIN).

The truth or falsity of compound statements can be determined purely formally, guided by the laws of propositional algebra, without referring to the semantic content of the statements.

Let us substitute the values ​​of logical variables into the logical expression and, using the truth tables of basic logical operations, we obtain the value of the logical function:

F= (A v B) & ( Ā v B) = (0 v 1) & (1 v 0) = 1 & 1 = 1.

Truth tables

Tables in which logical operations reflect the results of calculations of complex statements for various values ​​of the original simple statements are called truth tables.

Simple statements are denoted by variables (for example, A and B).

When constructing truth tables, it is advisable to be guided by a certain sequence of actions:

it is necessary to determine the number of rows in the truth table. It is equal to the quantity possible combinations values ​​of logical variables included in a logical expression. If the number of logical variables is equal to p, That:

number of lines = 2 n .

In our case, the logical function

has 2 variables and therefore the number of rows in the truth table must be 4;

it is necessary to determine the number of columns in the truth table, which is equal to the number of logical variables plus the number of logical operations.

In our case, the number of variables is two: A and B, and the number of logical operations is five (Table 8), that is, the number of columns of the truth table is seven;

it is necessary to build a truth table with the specified number of rows and columns, designate the columns and enter into the table possible sets of values ​​of the original logical variables;

it is necessary to fill the truth table by columns, performing basic logical operations in the required sequence and in accordance with their truth tables.

We can now determine the value of a Boolean function for any set of Boolean variable values.

Table 8 – Truth table of a logical function