Bits and Bytes

Bitwise Operations

This is some basic theory, necessary to understand the bitwise operations that are used to encode and decode these messages. If you’re happy with bitwise operations, ignore this whole section.

Computers store data as bits, grouped into nibbles, bytes and words. A byte, as far as we care, always contains 8 bits, in positions labelled 0–7. The 7^th position is the “most significant” and the 0^th is the “least significant”. When bytes are written, they are usually written 7^th column first.

A byte can be seen as representing a number. This is done by saying that each position, p, represents a number, 2^p. These numbers are summed wherever there is a 1 at a position and this gives the final number. Changes to more significant bits have a greater effect on the number. This is the same process that expresses our everyday decimal numbers, except that the position, q, of a digit means that it is multiplied by 10^q (eg. 203 = 2 × 10² + 3 × 10⁰).

Position	7	6	5	4	3	2	1	0	Total
Value	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	∑_p=0⁷2^p
	128	64	32	16	8	4	2	1	255
Example	1	0	0	0	0	1	1	0	128 + 4 + 2 = 134

Bitwise AND and OR

Taking two bytes, a and b, with bits a_0-7 and b_0-7:

    c = a & b    where  c_i = 1  if  a_i = 1  and  b_i = 1,    i ∈ [0,7]
    d = a | b    where  d_j = 1  if  a_j = 1  or   b_j = 1,    j ∈ [0,7]

Position	7	6	5	4	3	2	1	0	Total
Value	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	∑_p=0⁷2^p
	128	64	32	16	8	4	2	1	255
a	1	0	0	0	0	1	1	0	128 + 4 + 2 = 134
b	1	1	0	0	0	0	1	0	128 + 64 + 2 = 194
c (a & b)	1	0	0	0	0	0	1	0	128 + 2 = 130
d (a \| b)	1	1	0	0	0	1	1	0	128 + 64 + 4 + 2 = 198

Bit Shifting

Bit shifting (left or right) is simply “pushing” all of the bits in a byte left or right, filling the gaps made at one end with zeros, kicking the high bits off the other end. Shifting left is equivalent to multiplying by a power of 2 (a << 3 == a × 2³) as long as only zeros are discarded from the top. Shifting right is equivalent to dividing by a power of 2, discarding any remainder (a >> 4 == ⌊ a ÷ 2⁴ ⌋ == ⌊ a × 2^-4 ⌋).

Position	7	6	5	4	3	2	1	0	Total
Value	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	∑_p=0⁷2^p
	128	64	32	16	8	4	2	1	255
a	1	0	0	0	0	1	1	0	128 + 4 + 2 = 134
a << 1	0	0	0	0	1	1	0	0	8 + 4 = 12
a >> 1	0	1	0	0	0	0	1	1	64 + 2 + 1 = 67

When we’re dealing with integer values, which are generally stored in more than one byte, shifting a value that was stored in only one byte ([0, 255]) left will move those bits into a more significant byte. This way, we can break an integer down into smaller bits and reassemble them later.

Masking

To retrieve the value of one bit, all we have to do is create a “mask” that hides all of the other bits. The solution is, to get the value V of bit i from byte a, we calculate:

    V = ((a & (1 << i)) != 0)

Since many programming languages treat any value except zero as “true”, we can usually forgo the check against zero. We already have a value which will behave correctly as either “true” or “false”.

Position	7	6	5	4	3	2	1	0	Total
Value	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	∑_p=0⁷2^p
	128	64	32	16	8	4	2	1	255
a	1	0	0	0	0	1	1	0	128 + 4 + 2 = 134
1 << 2	0	0	0	0	0	1	0	0	4
a & (1 << 2)	0	0	0	0	0	1	0	0	4 != 0
1 << 3	0	0	0	0	1	0	0	0	8
a & (1 << 3)	0	0	0	0	0	0	0	0	0 == 0

We can use the same technique to select multiple bits and use it to select any combination we want, including whole bytes from out of larger structures, like integers (in decimal, a byte full of ones is 255), so if we have an integer I, held in 16 bits, we can split it into two bytes as follows:

    MSB = (I >> 8),    LSB = (I & 255)

and we can recombine them later:

    I = ((MSB << 8) | LSB)

This technique is used to split and recombine the values from ultrasound, but since data bytes can only range within [0, 127] (using only the least significant 7 of the 8 bits in a byte), we shift by 7 and mask using 0x7F.

Setting and Unsetting Bits

To set a bit (change its value to 1), we have to find an operation which will leave a 1 where we want and leave other bits unchanged. The correct behaviour comes from the following operation, to set bit i in byte a, leaving the result as a_new:

    a_new = a | (1 << i)

Unsetting a bit requires a further operation: a bitwise NOT (written ~). This operation leaves a 0 where there was a 1 and a 1 where there was a 0. This is used as follows (unsetting bit i in byte a):

    a_new = a & ~(1 << i)

Position	7	6	5	4	3	2	1	0	Total
Value	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	∑_p=0⁷2^p
	128	64	32	16	8	4	2	1	255
a	1	0	0	0	0	1	1	0	128 + 4 + 2 = 134
1 << 3	0	0	0	0	1	0	0	0	8
a \| (1 << 3)	1	0	0	0	1	1	1	0	128 + 8 + 4 + 2 = 142
~(1 << 2)	1	1	1	1	1	0	1	1	255 - 4 = 251
a & ~(1 << 2)	1	0	0	0	0	0	1	0	128 + 2 = 130