# Logical operations

Logic operations include any operations that manipulate *Boolean* values. Boolean values are either true or false. They are named after English mathematician George Boole, who invented Boolean algebra, and is widely considered the founder of computer science theory. They can also be represented as 1 and 0. Normally, 1 represents true, and 0 represents false, but it could be the other way around.

The basic Boolean operators are *and* (^), *or* (v), and *not* (‘). In settings where Boolean operators are not mixed with mathematical operators, or is sometimes written as + and and as *. We will avoid this notation to prevent confusion with addition and multiplication. All Boolean functions can be built from these three basic operators.

Given two Boolean variables A and B, the Boolean expression A ^ B is true only if both A and B are true. The truth table below illustrates all possible combinations with the AND operator.

A v B is true if either A or B is true, including the case when both are true.

Not A is true when A is false, and vice-versa.

Another common operator is the exclusive or (xor) operator. A xor B is defined as A or B, but not both. In other words, A xor B is true if A and B are different. This turns out to be frequently useful, so most computer architectures include an xor instruction.

A xor B = (A ^ B’) or (A’ ^ B)

All functions in digital computers, including arithmetic operations, are built on these basic logic functions. The full details are covered in a course on digital logic. As a simple example, suppose we add two 1-bit binary numbers A and B. This will result in a 1-bit sum, and a 1-bit carry.

From the truth table, we can see that S = A xor B, and C = A ^ B. From this basic logic, we can develop a circuit to add N-bit numbers. From these adders, we can develop subtracters, multipliers, and dividers, and eventually an entire arithmetic/logic unit (ALU).

In machine language, logic instructions perform the same logic operation on all corresponding bits in a word. Suppose X and Y are two 8-bit words with values of 0x23 and 0x4f. We can line up the values as we would when performing an arithmetic operation, and perform a logic operation on corresponding bits instead:

00100011 00100011 00100011' 00100011 ^ 01001111 v 01001111 xor 01001111 ---------------------------------------------------------------- 00000011 01101111 11011100 01101100

Some architectures have instructions to perform logic operations on various data sizes. For example, the VAX has `andb`

(byte), `andw`

(word) and `andl`

(long word) instructions. The MIPS, being a RISC architecture, has a more limited instruction set, and hence all logic operations act on 32-bit words. The `not`

operation is not supported by hardware, but is implemented as a pseudo-instruction. The not operation can be easily achieved by a variety of means.

# and and $t0, $t2, $t1 andi $t0, $t2, 0xffff0000 # or or $t0, $t2, $t1 ori $t0, $t2, 0xffff0000 # not not $t0, $t1 # xor xor $t0, $t2, $t1 xori $t0, $t2, 0xffff0000 # nor nor $t0, $t2, $t1 # not $t1, $t0 xori $t1, $t0, 0xffffffff nor $t1, $t0, $t0 # slow not sub $t0, $0, $t0 addi $t0, $t0, -1 # Incredibly slow not mul $t0, $t0, -1 addi $t0, $t0, -1

and vs div for detecting odd numbers Can be used in C

Logic instructions are commonly used to set (turn on) or clear (reset, turn off) individual bits within a word without affecting other bits.

By ANDing a value with a deliberately designed constant, called a *bit mask* we can clear specific bits. Any bits that are 0 in the mask will be cleared in the result, and bits that are 1 in the mask with be preserved in the result.

value 10010100 mask 00001111 ---------------- 00000100

Likewise, we can use an OR operation to set bits. A 1 in the mask causes the bit to be set, and a 0 causes it be be preserved.

value 10010100 mask 00001111 ---------------- 10011111

An XOR can be used to invert (toggle) specific bits. A 1 in the mask causes a bit to be inverted, while a 0 causes it be preserved:

value 10010100 mask 00001111 ---------------- 10011011

What MAL instruction would we use to set the two rightmost bits in $t0 while leaving the rest alone?

# OR with 0000 0000 0000 0000 0000 0000 0000 0011 ori $t0, $t0, 3

What MAL instruction would we use to clear bits 3 and 5 in $t0 while leaving the rest alone?

# AND with 1111 1111 1111 1111 1111 1111 1101 0111 andi $t0, $t0, 0xffffffd7

What MAL instruction would be use to toggle the leftmost bit in $t0? ( Sign-magnitude negation )

# XOR with 1000 0000 0000 0000 0000 0000 0000 0000 xori $t0, $t0, 0x80000000