Bitwise operations and the half- and full-adder

Unary bitwise operations

NOT

We can perform basic operations on inputs.

A simple operation is the unary NOT operator, which returns the reverse of the values of all bits.

We also have binary operators, which take two bits and return another bit. Of note are, AND, OR and XOR.

These operations are a model of Boolean algebra. So there are \(16\) possible binary functions and \(4\) possible unary operators.

As in logic, we can combine elementary logical gates to create other logic gates.

These operations can also be performed on a series of bits, however each individual bit is independent of other bits for these operations.

masks in bitwise operations. take only desired part by doing and operation with mask

Setting values

setting values. or operator with target values if want to set to 1. what if want to set 0? invert map and use and. or just use xor

Bitshifts

We can have other operations where bits do interact. An important operator is the bit shift. This takes a series of bits and shifts them to the right or left by one place. This pushes one bit off the end.

The new bit can take a \(0\) or \(1\).

Logic gates are not needed for bit shifts. Instead wiring of inputs to outputs achieves the same effect.

shift left is x2 shift right is /2

Binary bitwise operations

AND, OR and XOR

Combining operations

Simple operators, such as bitwise operators and bit shifts, can be combined to create more complex operators. These could have a large number of inputs, outputs and logical gates.

Arithmetic Logic Units (ALUs)

Half adder

We first introduce the half adder.

Take two inputs \(A\) and \(B\) and put both inputs to two binary operators.

The operators are an XOR gate and an AND gate.

The AND gate only returns \(1\) if both inputs are \(1\). The XOR gate returns \(1\) if only one input is \(1\).

The XOR gate returns the second “digit” while the AND date returns the first.

This means we take two number at either \(0\) or \(1\), and return beteen \(0\) and \(2\) in binary form.

Full adder

If we are adding, say, a 2 bit number, then we need the abilty to carry numbers. The full adder takes two numbers, and also a carry from the previous digit. The full adder then adds these three numbers.

The carry from each full adder (or half adder) is then passed to the next digit.

If the carry is \(1\) for the final digit then there has been an overflow.

\(N\)-bit ALU

An \(8\)-bit ALU processes numbers represented by \(8\) bits. Similar for \(16\)-, \(32\)- and \(64\)-bit ALUs.

Succession

Succession function

We can have a unitary succession function by adding \(1\) to a number using the full adder.