A digital logic gate accepts input and produces a *Yes* or *No* output based upon a condition. Examine a light switch with two switches in the pseudo-electronic schematic below.

In order for the light to turn on, both switches must be on, but if either switch is turned off or if both switches are turned off, then the light is off.

In binary, “on” would be represented with a 1 bit, and “off” would be represented with a 0 bit. A **truth table** describes all possible output states given any combination of input states. Here is a truth table that shows all possible combinations that turn the light on and off.

Different types of logic — AND, OR, XOR, NOT — permit testing two or more inputs in order to determine if the output equates to a Yes/No, True/False, or 1/0 decision.

## AND Gate

The light switch mechanism described above is an example of an AND gate. Only when both inputs are on will the light turn on. This concept is easier to understand if we look at the AND symbol used in electronics.

In binary, a logic AND will produce a 1 bit only when both input bits are 1. If either or both inputs are 0, then output is 0.

Entire bytes can be ANDed together. From right to left, line up each bit in a column and perform the AND function on each bit in order. Pad with zeros if needed to avoid confusion.

### Bitwise AND and Conditional (Boolean) AND

In programming, there are two types of AND: **bitwise** and **conditional**. Bitwise AND is often represented by a single ampersand symbol (**&**), and it means to AND individual bits together.

The conditional AND is usually represented by two ampersand symbols together (**&&**), and its result is true if and only if the given programming expressions evaluate to true. While both represent AND logic, they serve different purposes. In this lesson, we are referring to bitwise AND.

### What is the result of 11101010b AND 110011b?

First, line up the bits so that the least significant bit in both base 2 numbers aligns with the ones place value. Pad the smaller base 2 with leading zeros so the two numbers have the same length. This helps avoid the temptation to “pull down” the most significant 1 bits.

11101010 00110011 --------------

Order does not matter. We could also write,

00110011 11101010 --------------

and obtain the same result.

Consult the truth table to determine the AND logic. For each column from right to left, record a 1 for each 1-1 pair and record 0 for everything else.

11101010 AND 00110011 -------------- 00100010

### What is 1001001 AND 0001000?

Align both numbers from the ones place and AND the bits together individually.

1001001 AND 0001000 -------------- 0001000

### AND Masking

The last example demonstrated bit masking. If we want to determine whether or not a certain bit (bit 4, in this case) is set or clear while ignoring all other bits, we can AND it with a mask of equal bit length where bit 4 is the only bit set to 1.

1001001 (Data to evaluate) AND 0001000 (Mask with bit 4 = 1) --------------------------------------- 0001000 (Bit 4 is 1)

The input number 1001001b contains other bits, but they are ignored because the mask 0001000b set them to 0, which causes them to be 0 in the output.

1000001 (Data to evaluate) AND 0001000 (Mask with bit 4 = 1) --------------------------------------- 0000000 (Bit 4 is 0)

Had bit 4 been 0 in the data number, the entire output would be 0.

### Subnet Mask

Masking is useful in IPv4 (Internet Protocol version 4) networking to determine if a given IP address exists in the same subnet.

An IPv4 address is denoted in dotted decimal notation. For example,

192.168.1.1

The subnet mask is also expressed in dotted decimal notation.

255.255.255.0

Converted to binary, both produce 32-bit sequences.

11000000.10101000.00000001.00000001 (IP address) 11111111.11111111.11111111.00000000 (Subnet mask)

ANDing the IP address with the subnet mask obtains the network ID.

11000000.10101000.00000001.00000001 (IP address: 192.168.1.1) AND 11111111.11111111.11111111.00000000 (Subnet mask: 255.255.255.0) ---------------------------------------------------------------- 11000000.10101000.00000001.00000000 (Network ID: 192.168.1.0)

If the computer receives a new IP address, such as 192.168.1.33, it will AND it with the subnet mask. If the results of the AND match the network ID, then the computer knows the new IP address exists on the same network.

11000000.10101000.00000001.00100001 (IP address: 192.168.1.33) AND 11111111.11111111.11111111.00000000 (Subnet mask: 255.255.255.0) ------------------------------------------------------- 11000000.10101000.00000001.00000000 (Obtained ID: 192.168.1.0) 11000000.10101000.00000001.00000000 (Matching network ID)

But if a different IP address, such as 192.**169**.1.33, is ANDed to obtain a different network ID, then the computer knows the new IP address must exist on another network.

11000000.10101001.00000001.00100001 (IP address: 192.169.1.33) AND 11111111.11111111.11111111.00000000 (Subnet mask: 255.255.255.0) ------------------------------------------------------------- 11000000.10101001.00000001.00000000 (Different ID: 192.169.1.0) 11000000.10101000.00000001.00000000 (Does not match 192.168.1.0)

In both cases, AND compared only the three most significant bytes of the IP address (bits 8 to 31) with the given mask. The low byte (bits 0 to 7) was ignored.

## OR Gate

OR outputs 1 when at least 1 input is 1.

In programming, there are bitwise OR and conditional OR. Bitwise OR evaluates individual bits, and it is represented by a single pipe character (**|**). Conditional OR is represented by two successive pipe characters (**||**), and it applies to expressions, not bits (unless bits are part of the expression). This lesson refers to bitwise OR.

### What is 11011011b OR 1001b?

First, align both numbers with the ones place and pad the smaller number with leading zeros.

11011011 OR 00001001 -------------- 11011011

What is 1110b OR 011b?

1110 OR 0011 ---------- 1111

## Exclusive OR (XOR)

*Ah!* This one is a goodie that might appear illogical at first, but it makes many computing constructs happen that are not possible with plain AND or plain OR.

XOR only outputs 1 when only 1 input is 1. Or to phrase it another way, XOR is 0 when both inputs are the same.

### What is 1011b XOR 1101b?

1011 XOR 1101 --------- 0110

### What is 1011001b XOR 110b?

1011001 XOR 0000110 ------------ 1011111

### XOR Checksum

A **checksum** is a form of error-checking for a group of bits. XOR has the unique ability to produce a checksum when given two numbers. If either number is lost or corrupted, XOR can reconstruct the missing number by XORing the generated checksum with the remaining number.

Suppose we have two data bytes: 10011111b and 10100000b. We XOR them together to produce a third byte. This is the checksum byte.

10011111 (Byte 1) XOR 10100000 (Byte 2) --------------------------------- 00111111 (Checksum)

Suppose Byte 2 gets corrupted.

10011111 (Byte 1) XOR ???????? (Byte 2 Corrupted by space invaders) ----------------------------------------------------- 00111111 (Checksum)

We can XOR the checksum with byte 1 to recover byte 2.

10011111 (Byte 1) XOR 00111111 (Checksum) ----------------------------------- 10100000 (Byte 2 Recovered)

### XOR and Cryptography

A simple demonstration of XOR involves the **symmetric key cipher** — a secret message technique where both parties use the same code, called a **key**, to encrypt and decrypt the letters in a sentence.

Suppose Mr. X wishes to send the word *“HELP”* to his contact Mr. Z. Each letter in the word *HELP* has a binary representation called **ASCII** (**A**merican **S**tandard **C**ode for **I**nformation **I**nterchange). Each letter is one byte, so we replace each letter with its ASCII byte.

HELP becomes

H E L P 01001000 01000101 01001100 01010000

Mr. X and Mr. Z have pre-agreed upon an 8-bit key: 11001100b. Any other 8-bit value would also work, but this is the one they know and keep secret between them.

Before sending the message, Mr. X encrypts it by XORing each byte with the same key 11001100b.

**Mr. X Encrypts:**

H E L P Plaintext: 01001000 01000101 01001100 01010000 Key: 11001100 11001100 11001100 11001100 XOR ------------------------------------------ Ciphertext: 10000100 10001001 10000000 10011100

Mr. X sends the ciphertext bit sequence 10000100 10001001 10000000 10011100 to Mr. Z, who then XORs each byte with the same key to read the original message.

**Mr. Z Decrypts:**

Ciphertext: 10000100 10001001 10000000 10011100 Key: 11001100 11001100 11001100 11001100 XOR ------------------------------------------ Plaintext: 01001000 01000101 01001100 01010000 H E L P

Mr. Z consults an ASCII table to convert each byte back into its alphabetical letter to read the word HELP.

This encoding method is not secure, but it helps show how XOR can be used to reconstruct a missing value from two known values.

## NOT

Logical NOT simply inverts bits. A 1 becomes a 0, and a 0 becomes a 1. Bitwise NOT is the same as 1’s complement.

### Perform a NOT operation on 11000000b.

To form the NOT of any byte, invert the bits.

11000000 > 00111111

## Combining Logic Gates

AND, OR, XOR, and NOT can be combined to form more complex gates and binary adders. In programming, we combine the existing simple bitwise logic (AND, OR, XOR, NOT) to produce more complex forms of logic.

## NAND

NAND is an AND gate that sends its output through a NOT gate. The output is opposite of an AND gate. NAND output is 0 only when both inputs are 1.

## NOR

NOR is OR whose output passes through a NOT gate.

## Exclusive NOR

XNOR inverts regular XOR output.

## Quiz Time!

Consult the truth tables above if necessary. Use pencil and paper. Include all bits in the answers. Assume binary for missing base notation.

### Questions

- 1001
**AND**1010 - 110011
**AND**10010011 - 11010
**OR**101 **NOT**11110000 10100101 (Include all bits in answer)- 1001
**XOR**1010 - 11000000
**XOR**11101110 *Oh, no! Corrupted Data!*Byte 1 is 01100110 and the checksum byte is 11110011. Using**XOR**, find the missing byte.- 0000
**NOR**0000 - 23d
**NAND**96d - 0x17
**AND**0x60

### Answers

- 1000
- 00010011
- 11111 (All 1’s) Remember to pad the bits.
- 00001111 01011010
- 0011
- 00101110
- 10010101 (XOR byte 1 and the checksum)
- 1111
- 11111111b. Convert decimal to binary and then NAND the two values. 23d = 00010111b and 96d = 01100000b.
- 00000000b. Convert hexadecimal to binary, and–
*Surprise!*We see the same binary values we just converted in #9 above. The only difference is that we are ANDing them together instead of NANDing them.