Using binary number sequence to determine which boxes are filled

Question

I am struggling with programming the following (with GAS):

I have 14 boxes which are either empty or not and I need to keep track of which boxes are empty. My idea is to use a base2 control value to keep track of the which boxes are empty.

To illustrate I will use an example with only 3 boxes

I figured the following scheme would work:

• All boxes empty: 0 control value
• Only box 1 empty: 1 control value
• Only box 2 empty: 2 control value
• Boxes 1 and 2 empty: 3 control value
• Only box 3 empty: 4 control value
• Boxes 1 and 3 empty: 5 control value
• Boxes 2 and 3 empty: 6 control value
• No boxes empty: 7 control value

I need an algorithm to know which boxes are empty and how to update the control value as boxes are filled and/or emptied.

I assume(d) that there must exist ready to use algorithms for this functionality and hence this sort of use of a base2 series have a name that I can use to google, right?

In case this it the wrong place for this question please let me know. Thank you.

Answer 1

(I second the comment that empty would usually be a 0 bit and full a 1 bit, but I can work with this.)

Just use bitwise operators

x & 1 # True if box 1 is empty
x & 2 # True if box 2 is empty
x & 4 # True if box 3 is empty

To switch whether boxes are empty or full:

x ^ 1 # Switches box 1
x ^ 2 # Switches box 2
x ^ 4 # Switches box 3

To make sure a box is empty:

x & 1 # Box 1 is empty
x & 2 # Box 2 is empty
x & 4 # Box 3 is empty

The only one that is tricky is guaranteeing that a box is full.

(x & 1) ^ 1 # Box 1 is full
(x & 2) ^ 2 # Box 2 is full
(x & 4) ^ 4 # Box 3 is full

• Bitwise And(&)

• Bitwise XOR (^)

Answer 2

This is called bitmasks. In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field.

You can represent the state of your problem as a bool array, something like: bool is_empty[14]; But this takes O(N) memory, where N is the number of boxes you have. Instead of using this array you can use the concept of bitmasks to represent every box with one bit of a single number. Let's take an example three boxes:

decimal  binary  meaning
0        000     All three boxes are empty
1        001     Box 1 is full
2        010     Box 2 is full
3        011     Boxes 1, 2 are full
4        100     Box 3 is full
5        101     Boxes 1, 3 are full
6        110     Boxes 2, 3 are full
7        111     All three boxes are full

To check if bit i is set, you just check if mask & 1<<i is not equal to zero.

To turn on bit i, you perform mask = mask | 1<<i;

To turn off bit i, you perform mask = mask & ~(1<<i)

To toggle bit i, you perform mask = mask ^ 1<<i.

A common use of bitmasks is generate all subsets from a set of numbers, here is a C++ to do that:

#include <iostream>
#include <vector>
int main(){
  std::vector<int>a{1, 2, 3};
  int n = static_cast<int>(a.size());
  for(int mask = 0;mask < (1<<n);mask++){
    std::vector<int>subset;
    for(int i = 0;i < n;i++){
      if(mask & 1<<i){
        subset.push_back(a[i]);
      }
    }
    for(auto &&num: subset)std::cout << num << " ";
    std::cout << std::endl;
  }
}