All numbers represent a polynomial
Where B represents the base of the number (i.e. 10 for decimal, 16 for hexadecimal, 8 for octal or 2 for binary,) and A_{n} represents some digit that is in the base.
0x
0b
Hexadecimal Octal ┌───┬───┬───┬───┐ ┌───┬───┬───┐ 0x │ F │ A │ 2 │ 5 │ 0 │ 7 │ 2 │ 4 │ └───┴───┴───┴───┘ └───┴───┴───┘ │ │ │ │ │ │ │ ┌───┘ ┌─┘ └─┐ └───┐ ┌─┘ │ └─┐ │ │ │ │ │ │ │ ┌──────┬──────┬──────┬──────┐ ┌─────┬─────┬─────┐ │ 1111 │ 1010 │ 0010 │ 0101 │ │ 111 │ 010 │ 100 │ └──────┴──────┴──────┴──────┘ └─────┴─────┴─────┘
All digital circuits in a computer are composed of these operations.
A AND B is true when both A and B are true, false otherwise. ∧ is the mathematical symbol for logical AND.
A AND B
∧
A AND B AND C AND D ... is true only when all operands are true, false otherwise
A AND B AND C AND D ...
Where 1 represents true and 0 represents false. In C Boolean logic any non-zero value represents true and only zero values represent false.
A OR B is true when either A or B are true, false otherwise. ∨ is the mathematical symbol for logical OR.
A OR B
∨
A OR B OR C OR D ... is true when any of the operands are true, false otherwise.
A OR B OR C OR D ...
NOT A is the logical inverse of A. ¬ or a horizontal bar over an operand or expression is the mathematical operator for logical NOT.
NOT A
¬
A XOR B is true if A and B are not the same, this is the same as the "not equal" operation. ⊕ is the mathematical symbol for XOR.
A XOR B
⊕
A XOR B XOR C XOR D ... is true if an odd number of operands are true, false otherwise
A XOR B XOR C XOR D ...
NAND, NOR and XNOR are the inverted result of the AND, OR or XOR operations.
NAND
NOR
XNOR
AND
OR
XOR
The bitwise operators operate similarly to the Boolean operations except they apply the operation to each individual bit of the two operands.
A | B
A & B
A ^ B
~ A
A << N
A >> N
A │ 0 0 1 1 1 0 0 1 & │ & & & & & & & & B │ 1 0 1 1 0 1 0 1 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ A&B │ 0 0 1 1 0 0 0 1
When a integer is binary shifted to the left, each bit in the integer is moved one position upward towards the most significant bits. The first bit is replaced with a 0.
old: 0 1 1 0 1 1 0 1 << 1 ╱ ╱ ╱ ╱ ╱ ╱ ╱ new: 1 1 0 1 1 0 1 0 ← 0
A shift to the left is equivalent to multiplying the value by 2 for each shift.
When shifting to the right, the behavior depends on whether the integer is signed or unsigned. If the integer is unsigned (i.e. can only represent a positive integer,) a shift right is similar to the left shift. The bits are shifted down and the upper bit is replaced with a zero.
old: 1 1 1 0 1 1 0 1 >> 1 ╲ ╲ ╲ ╲ ╲ ╲ ╲ new: 0 → 0 1 1 1 0 1 1 0
If the integer is signed, i.e. can represent both positive and negative values, the behavior is the bits are shifted down as normal, but the upper bit remains the same value it had before the shift.
old: 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 >> 1 │╲ ╲ ╲ ╲ ╲ ╲ ╲ │╲ ╲ ╲ ╲ ╲ ╲ ╲ new: 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0
A shift to the right is equivalent to dividing the number by 2 for each shift. When the number is negative, it should remain negative after a division by 2, thus the reason for preserving the upper most bit (the sign bit) when the integer is signed.
To set a specific bit, you first create the bit to set by shifting a one to the desired location:
mask = 1 << bitpos
This creates a mask with the specific bit set and the rest of the mask are zero'ed bits. the mask is then OR'ed against the number you want to modify:
num | mask
The result will be num with the bit at bitpos set to a 1, as anything OR'ed against 1 will always result in a 1.
┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │ num └───┴───┴───┴───┴───┴───┴───┴───┘ OR ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ (1<<4) └───┴───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ num | (1<<4) └───┴───┴───┴───┴───┴───┴───┴───┘
It should be noted that 1 << N is equivalent to 2^{N}.
1 << N
First create a mask where the bit to be zero'ed is zero and the rest of the mask is all ones. You can do this by inverting the mask after setting the bit to be cleared:
mask = ~ (1 << bitpos)
Then AND the mask against the number to be modified:
num & mask
The bits in num will pass through the mask unmodified where the mask is 1's and will always be 0 at bitpos.
┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │ num └───┴───┴───┴───┴───┴───┴───┴───┘ AND ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 1 │ 1 │ 1 │ 1 │ 0 │ 1 │ 1 │ 1 │ ~(1<<3) └───┴───┴───┴───┴───┴───┴───┴───┘ ↓ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 1 │ num & ~(1<<3) └───┴───┴───┴───┴───┴───┴───┴───┘
To test if a specific bit is set, AND the number against a bitmask for the specific bits:
num & (1<<bitpos)
The result will be zero if the bit is unset and be equal to the bit value (1<<bitpos, i.e. non-zero) if the bit is set.
When an integer is unsigned, the integer has a range of possible values from 0 to 2^{n}-1 where n is the number of bits in the integer. When adding a number to an unsigned integer where the result is too large for the integer to hold, the upper bits of the result will be dropped and the result will be just the value of the lower bits.
n
250 ⟶ 1111 1010 +10 ⟶ 0000 1010 260 ⟶ 1 0000 0100 ⟶ X 0000 0100 ⟶ 4
When the integer is signed the upper bit is used to indicate that the number is negative, however the remaining bits are in two's compliment form. Subtracting from an unsigned integer where the result would be negative is still represented in two's compliment format.
Adding and subtracting works in the same manner as it does in Base-10, but with the limitation that you only have two digits to work with. When adding 1 and 1, the result is 0 with a carry of 1 (i.e. 10 which is 2 in binary.)
If adding bits A and B together, we can use a half-adder circuit to do so. The half adder is an incomplete adder in that it does not accept a carry input (i.e. the carry bit from a previous bit addition.) Later we will show a full adder which does accept the carry as input.
The half adder takes as its input, bits A and B and outputs a sum of the two bits and carry bit (when the sum of A and B is greater than 1.)
From this truth table we can see that the sum is the XOR of A and B and the carry is the AND of A and B.
A ──┬─┌─────┐ │ │ XOR ├── sum B ┬─|─└─────┘ │ │ │ └─┌─────┐ │ │ AND ├── carry └───└─────┘
A full adder would compute the output sum of one bit in an addition, along with the output carry (C_{out}) and would accept as its input the input bits A and B and also an input carry (C_{in}) from the previous bit being added.
Full adders would then be chained together to sum the bits of A and B. The carry out of each full adder is the carry input for the next full adder. This is called a ripple carry adder.
A1 B1 A0 B0 0 ──┐ │ │ ┌───┐ │ │ │ │ │ │ │ │ │ │ │ │ ┌┴───┴──┴┐ │ ┌┴───┴──┴┐ ... │ │ FA │ │ │ FA │ │ └──┬──┬──┘ │ └──┬──┬──┘ │ │ │ │ │ │ └─────┘ │ └─────┘ │ C1 S1 C0 S0
When subtracting 1 from 0, you borrow from the next bit. If there is no next 1 bit to borrow from, you may borrow from an imaginary 1 bit beyond the end of the number being subtracted from.
1 1 1 1 1 (borrows) 0 │ 0 0 0 0 - 1 │ - 0 0 0 1 ─── ─────── -1 1 1 1 1 (two's compliment for -1)
There are half and full subtractor circuits however we can use slightly a slightly modified ripple carry adder once we learn about two's compliment. The idea is that A - B is the same as A + -B. Converting one of the numbers to negative and then adding them will accomplish the same as subtracting.
A - B
A + -B
Two's compliment
To represent a negative number in binary, invert the positive representation of it and add one:
-10 ⟶ 10 ⟶ 0000 1010 ~10 ⟶ 1111 0101 +1 ⟶ 1111 0110 ⟶ -10
Alternatively you can subtract the number from 0 to arrive at the same result. Two's compliment form is used because it allows normal addition and subtraction of positive and negative values. A negative value need only be converted back to normal in order to print the value.
-10 -> 1111 0110 ~-10 0000 1001 +1 0000 1010
An inverter can be constructed using XOR where one side of the XOR is always 1, the other input will be inverted on the output. If one side is always zero, then the output is the same as the other input.
A 1 A 0 ┌┴─┴┐ ┌┴─┴┐ │XOR│ │XOR│ └─┬─┘ └─┬─┘ ¬A A
When K in the ripple carry adder below is set to 0 it acts as a normal adder, however when set to 1 it will invert the bits of B and use the initial initial carry to do the addition of 1 to the result, turning B into proper twos compliment and then performing the addition of A + -B.
B3 B2 B1 B0 ──────────│─┬────────────│─┬────────────│─┬────────────│─┬────┬─ K A3 ┌┴─┴┐ A2 ┌┴─┴┐ A1 ┌┴─┴┐ A0 ┌┴─┴┐ │ │ │XOR│ │ │XOR│ │ │XOR│ │ │XOR│ │ │ └─┬─┘ │ └─┬─┘ │ └─┬─┘ │ └─┬─┘ │ ┌─┴────┴─┐ ┌─┴────┴─┐ ┌─┴────┴─┐ ┌─┴────┴─┐ │ ... ────┤ FA ├─────┤ FA ├─────┤ FA ├─────┤ FA ├───┘ C3 └─────┬──┘ C2 └─────┬──┘ C1 └─────┬──┘ C0 └─────┬──┘ │ │ │ │ S4 S3 S1 S0
1111 1100 <- carries 42 │ 0010 1010 + -10 │ 1111 0110 ─── │ ───────── 32 │ 0010 0000