Bit logic and character codes

A logical operation can be checked all at once with a table listing every combination of inputs. That is a truth table.

With two inputs there are only four combinations: 0 0, 0 1, 1 0 and 1 1. Fill those four rows top to bottom and you have said everything about the operation.

The logical product gives 1 only on the bottom row, 1 1. The logical sum gives 0 only on the top row, 0 0, and 1 everywhere else.

There is only one thing to remember. The logical product is strict and the logical sum is lax. The product will not give a 1 unless everybody is 1, while the sum gives a 1 if even one of them is.

This strict-and-lax business also works backwards. If a logical sum is 1 and you know one side is 0, the other side must be 1. If a logical product is 1, both are 1. Some questions are settled by that alone, without filling in the whole table.

Here is one more operation, fitting neither && nor ||: exclusive or (XOR).

This gives 1 when exactly one of them is 1. Being 0 when both are 1 is the difference from the logical sum, and that is what "exclusive" means in the name.

Put another way, 1 if the two differ and 0 if they are the same. You can read it as simply asking "are these different?" JavaScript has no dedicated operator for it, but it is close to what a !== b does.

That property gives XOR a handy use. Where you XOR with 1 the bit flips, and where you XOR with 0 it stays. So it is the tool for "flip only here". XOR with the same partner again and you are back where you started.

The four operations can also be sorted out with two overlapping circles (a Venn diagram). Draw circle A and circle B overlapping a little.

• Logical product … only the part where the two overlap
• Logical sum … the whole of the two together
• Negation … outside the circle
• Exclusive or … the whole of the two together with the overlap removed

A truth table is a tool for counting rows and a Venn diagram a tool for seeing the relations at a glance. They are two views of the same thing, so recalling whichever suits you is enough.

Check why exclusive or comes out as "the logical sum minus the overlap" against the 1 1 row of the truth table. That row being 0 is exactly what "the overlap removed" corresponds to.

A real computer almost never deals with a single bit. It operates on whole bit strings of eight or sixteen bits.

The method is easy: look only at the same position and compute each place independently. There is no carry at all as there would be in addition. That is the decisive difference from arithmetic addition.

Line up the three operations with 10110011 and 00001111. From the rightmost place onwards, you only compare one bit above against one bit below.

Bit strings are often written in hexadecimal. Since one hex digit = four bits, 0F is 00001111, F0 is 11110000, FF is 11111111 and 7F is 01111111. Learning those four by heart speeds the exam up.

The prime use of bit operations is masking: a way of touching only the places you want and leaving the rest alone. The other bit string (the mask) says which places you are aiming at.

• Extract, keep … AND. Places where the mask is 1 stay as they were; places where it is 0 vanish to 0
• Set (make 1) … OR. Places where the mask is 1 become 1; places where it is 0 stay
• Flip … XOR. Only places where the mask is 1 flip; places where it is 0 stay

Tell them apart as AND clears, OR sets, XOR flips. All three share "leave the places where the mask is 0 alone", and AND alone is easier read the other way, as "leave the places where the mask is 1 alone".

What the exam sets is this paraphrasing. "Extract the lower four bits" is an AND with 0F; "flip every bit" is an XOR with FF; "make the most significant bit 0 and take the rest" is an AND with 7F. The knack is deciding both the operation and the mask from the operation being asked for.

The other tool is the shift operation, which simply moves the whole bit string left or right. Vacated places take a 0 and places pushed off the end are thrown away.

What matters here is that a shift becomes multiplication and division. In binary each place is worth twice the next, so

• Left by one bit … the value doubles
• Right by one bit … the value halves (remainder discarded)

Shift by n bits and it is 2 to the power of n. Left by four bits multiplies by 16, right by four divides by 16. Being faster than multiplication, it is used in real programs.

Combined with hexadecimal there is an even handier reading. Since one hex digit is four bits, a shift of four bits is a move of one hexadecimal digit. Shift 3A7F right by four bits and you get 03A7.

One that always puts 0 into the vacated places is a logical shift. There is also an arithmetic shift, which puts something else in with the sign in mind, but signs belong to the previous lesson, so hold on to the logical shift here.

The rules for rewriting logical expressions are the De Morgan laws. In a phrase: push a negation inwards and AND and OR swap places.

• NOT(A AND B) = (NOT A) OR (NOT B)
• NOT(A OR B) = (NOT A) AND (NOT B)

Checking it in words makes it sit better. "Not both A and B" is the same as "either not A or not B" — if even one is missing, "both" does not hold.

The other direction is the same. "Neither A nor B" is the same as "not A, and also not B".

The way to handle it is changing three things at once. Take off the outer negation, put a negation on each of the two inside, and swap the operation in the middle. Forget one of the three and you have a different expression, and the choices will duly include that "one forgotten" shape.

Learn one more alongside it: two negations cancel. NOT(NOT A) = A. Moving expressions with De Morgan often throws up NOT(NOT ...), and you can clear it away on the spot.

The operations so far, made into electronic components as they stand, are gates. A logic circuit is built by combining them.

Four are basic: the AND gate, the OR gate, the NOT gate and the XOR gate. Think of them as components with input lines going in from the left and an output line leaving on the right.

There are also versions with a negation stuck on the end. NAND is NOT(A AND B) and NOR is NOT(A OR B). The names are just AND and OR with an N (for Not) in front. Their truth tables are the AND and OR results turned exactly upside down.

The interesting part is that NAND alone can build every gate. Feed the same input to both sides and A NAND A = NOT(A AND A) = NOT A, doing the job of a NOT gate. From there the De Morgan laws let you assemble AND and OR too. That is why real ICs are often built from arrays of NANDs.

When reading a circuit of NANDs, the standard move is driving the negations out with De Morgan. An expression like NOT(NOT(A・B) AND NOT(C・D)) unravels in one application all the way to A・B + C・D.

Two gates are enough to build the addition of one binary digit. That is the half adder.

Write out addition of single digits: 0+0=0, 0+1=1, 1+0=1 and 1+1=10. Only the last runs to two digits, producing a carry, and that is the crux.

Think of the answer in two parts: the first digit of the sum and the carry.

• First digit of the sum … the sequence 0 1 1 0. That is the XOR truth table exactly
• Carry … the sequence 0 0 0 1. That is the AND truth table exactly

So feed x and y into both an XOR gate and an AND gate, take the XOR output as the sum and the AND output as the carry. Sum is XOR, carry is AND — that correspondence is all you need.

Note that a half adder cannot take a carry in from the place below. So it cannot be used as it is above the second digit, where you need a full adder, which also has a carry input. A full adder is built from two half adders.

Since there is nothing but bits inside a computer, characters need numbers assigned to them too. That arrangement is a character code.

The oldest and most basic is ASCII, expressing letters, digits and symbols in seven bits (128 possibilities). A is 65 and a is 97, rising by one through the alphabet.

128 is not enough for Japanese, so schemes using two bytes per character were made. Shift JIS and EUC (EUC-JP) are those, and they assign different numbers to the same Japanese. Reading the same document under the wrong scheme gives you mojibake because of that mismatch.

Learning from that split, Unicode was created to gather the characters of the whole world into one table of numbers.

What to distinguish here is Unicode from UTF-8. Unicode is the table of numbers itself, while UTF-8 is a way of writing those numbers out as bytes. UTF-8 varies the length from one to four bytes by character, and is built so that the ASCII range comes out as exactly the same bytes as ASCII. That is why an old file of letters and digits reads straight off as UTF-8.

Data can be corrupted in transit or in storage. The machinery for noticing that it broke is error detection. The common idea is to carry an extra value computed from the body and recompute it at the receiving end.

The parity bit is the simplest: add one bit so that the count of 1s is even (or odd). If one bit is corrupted the parity of the count changes and you notice, but if two bits are corrupted at once the parity returns and it slips past. Also, you cannot tell which place was corrupted, so you cannot correct it. That is what the exam asks about most.

Odd parity and even parity differ only in the agreement on which way to make the count of 1s come out, and their detection power is exactly the same. Choices written as though there were a difference come up, so watch for that.

Adding one per character down the column is vertical parity, and adding one across a whole block is horizontal parity. Combine both and the corrupted place can be pinned down at the intersection of row and column, so a single-bit error can even be corrected.

Line up the other three. A check digit appends a check figure computed from each digit of a code, catching typing mistakes. A Hamming code carries several check bits and can correct a one-bit error and detect a two-bit error. CRC appends the remainder of dividing the bit string by an agreed generator polynomial and the receiver checks whether the same polynomial divides it evenly. It is strong against errors that corrupt a run of bits and is widely used in communication.