Bitsets

C does not explicitly have a boolean data type. By convention, we use int to represent booleans: 0 is false and 1 is true. However, this means we are using 4 bytes (32 bits) just to represent a single bit of information, which is very inefficient.

Using char or uint8_t is better as it only requires 1 byte (8 bits). However, we cannot do much better than this for a single boolean as this is the smallest data type C provides us. Even a type such as _Bool takes up 1 byte, which may come as a surprise given it is supposed to store just one bit of information (true or false)! See here if you're curious.

That said, encoding multiple booleans efficiently is possible. We did this in lab 1 using bitmasks: We used all 32 bits of int to represent 32 booleans. We considered the least significant bit to be the first boolean (index 0) and the most significant digit to be the last boolean (index 31). Using bitwise operations such as <<, &, and |, we can check whether a bit at a certain "index" is on or off.

In this exercise, you will extend this idea to encode more than just 32 bits. We do not have data types that allow us to encode arbitrarily large values, so we use array of bytes (uint8_t array) instead. The first byte will encode the first 8 booleans from the least significant digit to the most significant digit. The second byte will encode the next 8 booleans, and so on.

For example, the "array of booleans" might be represented using the following array of bytes.

uint8_t data[] = {0x01, 0xF2, 0xFF};
// represents the array {1,0,0,0,0,0,0,0, 0,1,0,0,1,1,1,1, 1,1,1,1,1,1,1,1}

data[0] = 0x01 corresponds to the first 8 booleans 1,0,0,0,0,0,0,0 with the first boolean (value = 1) being stored in bit 0 of data[0].

We will write the following helper functions to manipulate this encoded "array of booleans."

• int get(const uint8_t *data, int i) returns the boolean value at index i, with 1 representing true and 0 representing false.
• int set(uint8_t *data, int i, int v) sets the boolean value at index i to true if v == 1 or false if v == 0.

Exercise 1

Consider the following uint8_t array.

uint8_t data[] = {0xF3, 0x11, 0xA5, 0x00};

Which of the following function calls will return true (1)? Select all that apply.

get(data, 0)

get(data, 3)

get(data, 8)

get(data, 9)

get(data, 12)

get(data, 31)

Loading...

Exercise 2

Complete the code for the functions get and set. We have defined the following constants for you.

#define N 1024 // 1024 booleans
#define BPB 8 // 8 bits per block
uint8_t data[N/BPB]; // populated by test cases

int get(const uint8_t *data, int i) { // your code here. assume 0 <= i < N. return 0; }

Loading...

void set(uint8_t *data, int i, int v) { // your code here. assume 0 <= i < N and v equals 0 or 1. }

Loading...

Set Operations

An array of bits is sometimes called a "bitset" because we can use it to represent a set of items. A bitset of size 8 (i.e. one byte) can represent any subsets of \{0,1,2,3,4,5,6,7\} if we consider the number i to be in the set if and only if the ith bit is on. Using this representation, uint8_t data[] = {0x3F} would represent the set \{0,1,2,3,4,5\}.

This representation yields itself to simple implementations of common set operations like union and intersection. Your task is to implement a few of them without using get or set from earlier. You may assume all arrays here are defined to have size N/BPB which is exactly enough for storing 1024 booleans.

Exercise 3

void set_union(const uint8_t *data1, const uint8_t *data2, uint8_t *output) { // set_union(A, B) = the set of all elements that are in data1 or in data2 // TODO: put the result in output }

Loading...

void set_intersection(const uint8_t *data1, const uint8_t *data2, uint8_t *output) { // set_intersection(A, B) = the set of all elements that are in data1 and in data2 // TODO: put the result in output }

Loading...

void set_difference(const uint8_t *data1, const uint8_t *data2, uint8_t *output) { // set_difference(A, B) = the set of items that are in A but not in B // TODO: put the result in output }

Loading...

You may use get for set_count.

int set_count(const uint8_t *data) { // TODO: count the number of elements in data and return return 0; }

Loading...

Encoding Three States

Consider a system that, at any point in time, can have one of three states represented by the values 0, 1, and -1. If you want to keep track of this system's state over time, the data might look like:

int8_t data[] = {0, -1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}

Storing 300 time steps in this format requires a total of 300 bytes, which is obviously inefficient.

Efficient encoding

We can do better. We can use two bits to represent each possible state: {0,0} can represent state 0, {0,1} can represent state 1, and {1,0} can represent state -1. {1,1} is not used to represent anything. We pack the first four numbers into the first byte, and then the next four numbers into the second byte, and so on. For example, the data above would be represented using the bit sequence {0,0,1,0,0,1,0,0, 0,0,0,0,0,1,0,0, 0,0,0,0,0,0,0,0}, which can be packed into three bytes: uint8_t data[] = {0x24, 0x20, 0x00}.

This method would allow us to store 300 timesteps using only 300 \times 2 = 600 bits, which fits into 75 bytes, a 4x improvement!

Exercise 4

Your task is to write a function that encodes the given original which has length 300 into encoded of length 75. You may call the helper functions get and set.

We define the following constants for you.

#define N 300
#define M 75
#define BPB 8

void encode(const int8_t *original, uint8_t *encoded) { // your code here }

Loading...

More efficient encoding

An array (containing only 0, 1, -1) of length 300 can have at most 3^{300} values, which is about 1.36 \times 10^{143}. If we can create a mapping between all possible arrays and integers from 0 to 3^{300}, then the array can be represented using a number which has only \lceil \log_{2} 3^{300} \rceil = 476 bits (60 bytes). We can use bitsets to represent this big number just fine. So, the solution we have now is not the most efficient possible yet.

Of course, creating such a mapping can be quite a difficult task, so another solution we consider is a hybrid between the two solutions.

We can group original data into blocks of three elements. Each block has 3^{3} = 27 possibilities which fits into a 5-bit number. Let's assume we map the block

• {0, 0, 0} to 0 ({0,0,0,0,0})
• {1, 0, 0} to 1 ({0,0,0,0,1})
• {-1, 0, 0} to 2 ({0,0,0,1,0})
• {0, 1, 0} to 3 ({0,0,0,1,1})
• {1, 1, 0} to 4 ({0,0,1,0,0})
• {-1, 1, 0} to 5 ({0,0,1,0,1})
• {0, -1, 0} to 6 ({0,0,1,1,0})
• and so on, until: {-1, -1, -1} to 26 ({1,1,0,1,0}).

Using this method, we can compress our array of 300 numbers to 500 bits (100 blocks, 5 bits per block) or 63 bytes. This is only slightly worse than the optimal solution but is much more elegant and easier to implement.

We hope that you have gained an appreciation for just how much can be done when we have access to lower level features like the ones provided by the C programming language. After all, actual memory and the hard disk in our computer only allow storing bits with no inherent meaning behind them. Yet, by designing a good encoding and decoding scheme, we can make sense of those bits and see them as whatever data we designed the scheme for, whether that is an array of numbers or a struct representing some real-world composite data.

If you are interested in learning more about this, consider looking into 6.3400 (6.02) or 6.7470 (6.441).