Week 14 Day 2 - Bitfields

Channel:

Bill Kerney

Subscribers:

2,650

Published on April 15, 2021 4:11:04 AM ● Video Link: https://www.youtube.com/watch?v=7chVVNM2bos

Duration: 1:59:20

171 views

3

Today we encountered the final boss for CSCI 41 - the integer.


Yes - "int x" is a data structure.


On our system, ints are 32 bits, so it is a data structure holding 32 bools in it. For example, if you have a game that has 32 different items in it or less that you can pick up and carry, then you can hold your whole inventory in a single int. (I'd personally use uint32_t to not be surprised if the number of bits changes on a different system - this approach fixes the bits we have at 32.)


To use a bitfield, you need to first name what each of the different bits mean. Since each bit corresponds to a different power of two, each name will be a power of two as well, usually:
const int TELESCOPE = 1;
const int UMBRELLA = 2;
const int KETTLE = 4;
etc.


Then we make our data structure:
uint32_t inv = 0; //Pretty easy, eh?



We can do the usual three operations on a bitfield: insert, search, and delete. All are O(1). In fact, a bitfield can actually do N operations all at once, where N is the size of the bitfield, making its operations O(1/N), kinda, except N doesn't usually scale past 64 or so.


1) Insert. Suppose we want to pick up the umbrella. We would write this code:
inv |= UMBRELLA;


This will add the UMBRELLA (4) to the bitfield if the inventory didn't have it before. If it did have it before, the code does nothing. (No duplicates.)


2) Search. Suppose we want to see if we have the umbrella -
if (inv & UMBRELLA) {
...
}



3) Delete. Suppose we want to get rid of the umbrella:
inv &= ~UMBRELLA;


Done