Logical operations

13.2.1. Logic Basics

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.

Table 13.1. The AND Operator

A B A ^ B
0 0 0
0 1 0
1 0 0
1 1 1


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

Table 13.2. The OR Operator

A B A v B
0 0 0
0 1 1
1 0 1
1 1 1


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

Table 13.3. The NOT Operator

A A’
0 1
1 0


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.

Table 13.4. Adder Truth Table

A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0


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

13.2.2. Logic Instructions

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

13.2.3. Using Masks

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