Shifts, Boolean, NAND, NOR

Shifting

Most programming languages will offer shift operators. These operators do as their name implies, they push/pull and shift some bits to a different position. << shifts bits left, >> shifts bits right.

Let’s take the 32-bit representation of the integer 64:

0000 0000 0000 0000 0000 0000 0100 0000

We could shift this integer right 6 places, and we would arrive at

0000 0000 0000 0000 0000 0000 0000 0001

Which is the 32 bit representation for the integer positive 1. The syntax for this would be:

int x = 64;
return x >> 6;

Alternatively, we can shift bits to the left. If we shift the integer 64, 6 places to its left we arrive at:

0000 0000 0000 0000 0001 0000 0000 0000

Which is the 32 bit representation for the integer positive 4096.

Interestingly, we will notice that these two operations correspond to multiplying and dividing.

/* this is shift left */
64 * (2^6) = 4096

/* this is shift right */
64 / (2^6) = 1.

Shifting can be useful in many instances. We saw how to add and subtract using two’s complement, to multiply and divide we can use shifts, where

x >> n = x / 2^n

and

x << n = x * 2^n

Bitwise Booleans

How do booleans come into play in all of this? Well a boolean can also be represented by an integer. False = 0, true = 1.

In 32 bits, False = 0000 0000 0000 0000 0000 0000 0000 0000

and True = 0000 0000 0000 0000 0000 0000 0000 0001

Boolean operators treat any non zero as True and zero as False. However, if their evaluation is False then they return 0 and if they evaluate to True they evaluate to 1.

So !0xFFFFFFF == 0x0000000

!0xABCD == 0x0000

!0x000001 == 0x000000

and

!!0xFFFFFF = 0x000001

!!0xABCD == 0x0001

!!0x00001 == 0x00001

Which leads us to being able to use && and || if we wanted to:

0x55 && 0xFF == 0x01

0x00 && 0xFF == 0x00

0x66 || 0x00 == 0x00

0x55 || 0xFF == 0x01

Boolean Circuits

Computer systems are made up of electrical circuits and use the binary system to represent and store data. In order to do so, electrical circuits have been designed to receive one or more binary numbers as their inputs and produce a single output. The logical operations of these circuits are governed by the rules of Boolean logic.

There are six Boolean operators available: AND, OR, NOT, NAND, NOR and XOR. In order to understand how they work, look at the simple electrical circuit in the figure below. It involves a single switch, a light, a battery and some connecting cables. Since both a light and a switch can either be on or off, the circuit can be in one of the two states, and as such resembles the binary system used in computer systems.

There are only two states that both the switch and the light can have at any point in time:

1. When the switch is open, the light is off. In the binary system, the switch and the light in this state are represented by a 1.
2. When the switch is closed the light is on. In the binary system, the switch and the light in this state are represented by a 0.

The electrical circuit described above is the simplest electrical circuit. It resembles a simple on/off switch. Computer systems however demand more complex circuitry in order to accomplish their tasks and so we must examine the six Boolean operators and their truth tables.

AND

The AND Boolean operator shown below is slightly more complicated than the simple electrical circuit of the on/off switch. The main difference is that there are two switches, instead of one, in series.

There are four states that the switches and the light can have at any point in time:

1. When both switches are open (0) and the light is off (0)
2. When switch 1 is open(0) and switch 2 is closed (1) the light is off (0)
3. When switch 1 is closed(1) and switch 2 is open (0) the light is off (0)
4. When both switches are closed (1) the light is on (1)

This can be represented with a Truth Table:

Switch 1	Switch 2	Output
Open(0)	Open(0)	off(0)
Open(0)	Closed(1)	off(0)
Closed(1)	Open(0)	off(0)
Closed(1)	Closed(1)	on(1)

OR

The OR operator would then have the following diagrammatic representation and truth table:

Switch 1	Switch 2	Output
Open(0)	Open(0)	off(0)
Open(0)	Closed(1)	on(1)
Closed(1)	Open(0)	on(1)
Closed(1)	Closed(1)	on(1)

NAND

The NAND Boolean operator is similar to the AND Boolean operator, but with its outputs inverted. As in the AND Boolean operator, the NAND Boolean operator has four states that it can be in, which are described in the Truth Table below. Instead of having an output of 1/true when both the inputs are 1/true, as is the case for the AND Boolean operator, the NAND Boolean operator has an output of 1/true when one or both inputs are 0/false.

As a Boolean operator, NAND is very important in computer science since any Boolean function can be implemented by using a combination of NAND gates.

Switch 1	Switch 2	Output
Open(0)	Open(0)	on(1)
Open(0)	Closed(1)	on(1)
Closed(1)	Open(0)	on(1)
Closed(1)	Closed(1)	off(0)

NOR

The NOR Boolean operator similar to the OR Boolean operator but with its outputs inverted. As in the OR Boolean operator, the NOR Boolean operator has four states that it can be in, which are described in the truth table below. Instead of having an output of 1/true when one or both inputs are l/true, as is the case for the OR Boolean operator, the NOR Boolean operator has an output of 1/true when both inputs are 0/false.

Switch 1	Switch 2	Output
Open(0)	Open(0)	on(1)
Open(0)	Closed(1)	off(0)
Closed(1)	Open(0)	off(0)
Closed(1)	Closed(1)	off(0)

Symbols

Boolean Expression Equivalences