Bitmask: There Is Space at the Bottom

Chidume Nnamdi 🔥💻🎵🎮

Sep 28

There is so much space at the bottom. Deep down in Zeroes and Ones. At the quantum level. Enough space to contain a whole lot of information, we are talking about information > zillions bytes of data.

Those are words you come across in quantum physics. And they are very true.

Calculations are performed in Computer/CPU by pushing around 0s and 1s. We write programs in human-readable form and compilers transforms it into a string of bits that only the Computer/CPU can understand.

And in our programs, we write code to perform different operations using algorithms and algorithms are logic. And logic contains a lot of true and false variables. These eat up precious space in computers and affect the performance of our apps.

What if you could represent all your variables in bits? That you could use the bit states (0,1) of one binary number to represent the states(true, false) of your variables.

This is done through the use of bitmasks.

Bit masks enable the simultaneous storage and retrieval of multiple values using one variable. — abdulapoopola

In this article, we will learn how to use bitmasks and its general applications. With this knowledge, you would save space(reduce your app code size) and make your app code much cleaner and faster on execution.

---

Tip: reduce bundle-size and app weight using Bit. Organize your component collection, choose and use the best ones, and share with your team. It’s OSS.

Bit – Share and build with code components
Bit helps you share, discover and use code components between projects and applications to build new features and…bitsrc.io

Bitmasks

Bits in a number can be set either on or off in a single bitwise operation.

What is a bitwise operation? It is an operation on numbers that operate at the bit level. This is accomplished using bitwise operators : & (AND), | (OR), << (SHIFT LEFT) and >> (SHIFT RIGHT).

Numbers are represented in 0s and 1s on the machine level. For example:

Number | Binary
---------------
1      | 1
2      | 10
3      | 11
4      | 100

We see the binary representation of numbers 1–4. If we apply any of the bitwise operators against any of them. their binary rep. will change thus changing the value of the number.

Let’s shift the bits of 2 to the left just once:

2 << 1

10 (2 in binary)
|
v
100 (4 in binary)

You see << interfered with the bits and it resulted in another value (4).

Now, what is bitmasking?

We saw that numbers are represented in 0 and 1. These bits can actually be used to represent a state in a set.

Suppose, we have a collection of N elements. We can represent these elements in a sequence of N bits.

Let’s elaborate with an example:

[1,2,3,4,5,6,7,8]

Above is our collection of elements (1 -> 8). We can encode the collection of bits:

[1,1,0,1,1,0,1,0]

Credit: Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person)

Each bit in an index represent the state of each element in the collection.

• 0 -> means the state is not set or disabled.
• 1 -> indicates that the element at the index is set/enabled.

Looking at our bits we can see that (1,2,4,5,7) are enabled/set and (3,6,8) are disabled.

The collection of these bits is called a bitmask.

If we remove the , in the bits you will see it will become this [11011010] which is 218 in the number system. So we could just use 218 to represent [1,2,3,4,5,6,7,8]. So much space at the bottom :-).

Another example, we can rep. a human into bits. Actually, the characteristics of a human.

Using conventional programming, we could do this:

typedef struct human {
    int hand,
    int legs,
    int head
}
 human_t

human_t h1
h1.hand = true
h1.legs = false
h1.head = true

We can use the above struct to represent a human when we want to, let’s say clone.

In the cloning machine, the system checks if the human to be cloned has everything set before proceeding.

The human struct can be represented in a string of bits:

typedef struct human {
    int hand,
    int legs,
    int head
}
 human_t

human_t h1
h1.hand = 1
h1.legs = 0
h1.head = 1

We can optimize further by rep the bits as a number.

[1,0,1]

You see the above bits represent what was in the struct. And removing the ,s, it becomes 101, which is 5 in the number system.

We can remove the hand, legs and head properties in the human struct and represent the value of their bits as a single property, like this:

typedef struct human {
    int value,
}
 human_t

human_t h1
h1.value = 5

In the human struct, we have 3 states to represent. We can rep. all states in the range of 0 -> 7 via combinations.

hand | legs | head
                         ------------------
no limbs and no head     | 0 | 0 | 0
no limbs, only head      | 0 | 0 | 1
only legs, no hands/head | 0 | 1 | 0
only hand, no legs/head  | 1 | 0 | 0
no head, only legs/hand  | 1 | 1 | 0
no hand, only legs/head  | 0 | 1 | 1
no head, only hand/legs  | 1 | 1 | 0
all limbs and head       | 1 | 1 | 1

Another, suppose you have a blog and you have writers that can write and post articles on your blog. And there are permissions for who can post, edit or delete a post(s).

owner  ----|- delete
writer --|-|- edit
         |-|- post

We have 3 states: post, edit, post. Writes can only edit or post an article and Owners can post, edit or delete an article.

| post | edit | delete
Owners  | 1 | 1 | 1
Writers | 1 | 1 | 0

You can employ writers with some permissions, maybe only post without edit or delete.

| post | edit | delete
Writers | 1    | 0    | 0

In our program, we can have a struct for permissions:

struct owner {
    //...,
    permission* p    
}

struct writer {
    //...,
    permission* p    
}

typedef struct permission {
    bool post,
    bool edit,
    bool delete
}
 permission_t

we can reduce it to:

struct owner {
    //...,
    permission* p    
}

struct writer {
    //...,
    permission* p    
}

typedef struct permission {
    int flag,
}
 permission_t

:-), so much space.

The post, edit, delete properties in permission structure reduce to just flag.

The next sections Masking Bits/Toggling Bits and Querying Status of Bit were inspired by Wikipedia — Mask(computing).

Masking/Toggling Bits

Bits can be turned on (masked on) or turned off (masked off).

The | operator is used to a bit on.

Looking at an OR table

00 => 0
01 => 1
10 => 1
11 => 1

Whenever a 1 is present, the result is 1. So we can deduce that in an OR operation this general principle is followed:

N | 0 = N
N | 1 = 1

To turn a bit on it must be ORed it with 1.

For example in our blog example, let’s say a writer has the permissions:

ped
110

The writer has only post and edit permission. If we want to give him a delete permission. The d bit has to be masked on, so it’s ORed with 1:

ped
OR  110
    001
    ---
    111
    ---

To turn a bit off, & operator is used. Looking at the AND table:

00 => 0
01 => 0
10 => 0
11 => 1

We see that the general priniciple of the AND operation follows that:

N & 1 => N
N & 0 => 0

So, to turn off a bit, its ANDed with 0, because the result is always 0.

Let’s say we have a writer with permissions:

ped
111

And we no longer want the writer to delete articles from our blog. To do that we AND his d permission with 0:

ped
&   111
    110
    ---
    110
    ---

For a bit to remain unchanged, it is ANDed with its value. That’s the reason we supplied 11 to pe permissions to leave them unchanged.

Querying Status of Bit

We can check the status of a bit by the ANDing the bit by the value of bit you are checking against.

Let’s say a writer has a writer’s permissions 110. To check if he has the post permission, we AND the bitmask 110 with the post flag 100. Let’s say we want to check if the post value of our writer is set 1:

ped
    110
&   100
    ---
    100
    ---

The result is 100 which proves the post permission is set.

If the writer doesn’t have post permission 010:

ped
    010
&   100
    ---
    000
    ---

The result proves the post bit is not set, he has no permission.

Combining Bits

Multiple states can be combined to set all states using the | operator.

Using our blog example,

ped
d 001
e 010
p 100

delete has 001 which is 1 in number system and also we can derive the value by shifting 1 with a zero to the left.

edit has 010 which can be derived by shifting the binary value of 1 to the left once 1 << 1.

post has 100, which can also be derived by shifting the bits of 1 twice to the left.

enum PermissionFlags {
    delete: 1 << 0 // 001,
    edit: 1 << 1 // 010,
    post: 1 << 2 // 100
}

Above is the rep. in C++. Let’s say we have a writers structure like this:

struct writer {
    int _permission
}

It has a _permission property which stores the permissions of the writer.

We create a new writer like this:

writer* w = <writer>malloc(sizeof writer);

Next, we have to assign permissions to the newly created writer w. Let’s say we want our writer to only post and edit but not delete.

To do this, we use | to combine the permissions from the PermissionFlags:

writer* w = <writer>malloc(sizeof writer);

// writer `w` is given  post and edit access
int* permission = PermissionFlags.post | PermissionFlags.edit;

w -> _permission = permission;

The result of the | operation has both post and edit bits enabled.

d -001
e -010
p -100

    010 (post)
|   100 (edit)
    ---
    110
    ---

To set all the bits i.e to give the writer delete, post and edit permissions, we do this:

// ...
// writer `w` is given delete, post and edit access
int* permission = PermissionFlags.post | PermissionFlags.edit |PermissionFlags.delete ;
// ...

Let’s see the operation in binary:

001 (delete)
|   010 (post)
    100 (edit)
    ---
    111
    ---

The result is 111, it has all the permissions bit set. We see that with | we can combine bits or flags or states.

Use Case: Blog Example

Let’s demonstrate what we have learned so far modeling our blog example.

Let’s create three writers each with different permissions.

writer* w1 = <writer>malloc(sizeof writer);
writer* w2 = <writer>malloc(sizeof writer);
writer* w3 = <writer>malloc(sizeof writer);

We will give w1 => post edit, w2 => edit delete, w3 => post edit delete

// ...
w1 -> _permission = PermissionFlags.post | PermissionFlags.edit;
w2 -> _permission = PermissionFlags.edit | PermissionFlags.delete;
w3 -> _permission = PermissionFlags.delete | PermissionFlags.post | PermissionFlags.edit;

We create a function with a switch case to either post, edit delete an article.

void performAction(writer* _w, int type) {
    int permission = w -> _permission;
    switch(type) {
        case 1 /* POST **/: {

        }
        case 2 /* EDIT **/: {

        }
        case 3 /* DELETE **/: {

        }
    }
}

Our performAction function does nothing except match our action type against the switch cases and return.

In each switch case, we will add a logic to check the writer’s permission before running the action. So in post case, the writer must have post permission before he can perform the action, and so on.

void performAction(writer* _w, int type) {
    int permission = _w -> _permission;
    switch(type) {
        case 1 /* POST **/: {
            if((permission & PermissionFlags.post) === PermissionFlags.post){
                cout << 'blog posted!!';
            }else {
                cout << 'Sorry, you don't have POST permission';
            }
        }
        // ...
    }
}

We used the & operator to check if the post bit is set on the writer.

If two states are combined using |. Each of the states can be retrieved from the combination by ANDing it with the desired state. If the result isn’t the desired state then the state is not set.

001 - p
010 - d
100 - e

_v = p | d = 011

001 |
010
---
011
---

_v has p?
011 &
001
---
001 yes
---

_v has d?
011 &
010
---
010 yes
---

_v has e
011 &
100
---
000 no
---

We can do the same for DELETE and EDIT:

void performAction(writer* _w, int type) {
    int permission = _w -> _permission;
    switch(type) {
        case 1 /* POST **/: {
            if((permission & PermissionFlags.post) === PermissionFlags.post){
                cout << 'blog posted!!';
            }else {
                cout << 'Sorry, you don't have POST permission';
            }
        }
        case 2 /* EDIT **/: {
            if((permission & PermissionFlags.edit) === PermissionFlags.edit){
                cout << 'blog edited!!';
            }else {
                cout << 'Sorry, you don't have EDIT permission';
            }
        }
        case 3 /* DELETE **/: {
            if((permission & PermissionFlags.delete) === PermissionFlags.delete){
                cout << 'blog deleted!!';
            }else {
                cout << 'Sorry, you don't have DELETE permission';
            }
        }
    }
}

Let’s see it in action.

const POST = 1;
const EDIT = 2;
const DELETE = 3;

//...

/* remember w1 has only edit and post permissions
*  writer w1 performs a POST action ie to post an article.
**/
performAction(w1, POST); // blog posted!!
// The action is successful because it has post permission.
// If he had tried to delete a blog, it will be denied
performAction(w1, DELETE); // Sorry, you don't have DELETE permission

You can try with writers w2 and w3, and see them flex their permission powers.

Let’s add a function that can give a writer a particular permission.

void givePermission(writer* w, int type) {
    switch(type) {
        case 1 /* POST **/: {
            w -> _permission |= PermissionFlags.post
        }
        case 2 /* EDIT **/: {
            w -> _permission |= PermissionFlags.edit
        }
        case 3 /* DELETE **/: {
            w -> _permission |= PermissionFlags.delete
        }
    }    
}

We learned earlier that | is used to turn on a bit. That’s why we used it here. Each switch case ORs the writer’s permission with the desired state, this sets the permission in the writer’s _permission property.

We know writer w1 has no delete permission, let’s give it a delete power with this function:

//...
performAction(w1, DELETE); // Sorry, you don't have DELETE permission
givePermission(w1, DELETE); /* super power granted **/
performAction(w1, DELETE); // blog deleted!!

Also, we will need a function to remove a permission from a writer’s permission.

void removePermission(writer* w, int type) {
    switch(type) {
        case 1 /* POST **/: {
            w -> _permission &= ~PermissionFlags.post
        }
        case 2 /* EDIT **/: {
            w -> _permission &= ~PermissionFlags.edit
        }
        case 3 /* DELETE **/: {
            w -> _permission &= ~PermissionFlags.delete
        }
    }
}

There is a strange operator here ~. This operator flips the bits of a number to its inverse.

For example:

~ 1010 = 0101

To unset the bits of a state in a combination of states. The state to be unset is flipped to its inverse, the result is then ANDed with the combination.

Looking at our code above, you see that’s what we did.

flip the bits to its inverse and AND with the result.

p = 001
e = 010
d = 100

_v = p | d = 101 (_v has p and d bits set)

001 |
100
---
101
---

check _v has p

101 &
001
---
001 yes, it has p
---

remove p
        101 &
~(001)  110
        ---
   _v=  100
        ---

_v now (100)

check _v is set

100 &
001
---
000 no p set
---

No! writer w1 misused his DELETE super-power!. Let’s strip him of his power.

Here, let’s see how this function removes DELETE permission from w1:

//...
performAction(w1, DELETE); // blog deleted!!
// oh gosh! he deleted another awesome article!!!

removePermission(w1, DELETE); /* super power removed, you are not worthy of this power **/
performAction(w1, DELETE); // Sorry, you don't have DELETE permission

Here is the full source of our example:

enum PermissionFlags {
    delete: 1 << 0,
    edit: 1 << 1,
    post: 1 << 2
}

struct writer {
    int _permission
}

void performAction(writer* _w, int type) {
    int permission = _w -> _permission;
    switch(type) {
        case 1 /* POST **/: {
            if((permission & PermissionFlags.post) === PermissionFlags.post){
                cout << 'blog posted!!';
            }else {
                cout << 'Sorry, you don't have POST permission';
            }
        }
        case 2 /* EDIT **/: {
            if((permission & PermissionFlags.edit) === PermissionFlags.edit){
                cout << 'blog edited!!';
            }else {
                cout << 'Sorry, you don't have EDIT permission';
            }
        }
        case 3 /* DELETE **/: {
            if((permission & PermissionFlags.delete) === PermissionFlags.delete){
                cout << 'blog deleted!!';
            }else {
                cout << 'Sorry, you don't have DELETE permission';
            }
        }
    }
}

void givePermission(writer* w, int type) {
    switch(type) {
        case 1 /* POST **/: {
            w -> _permission |= PermissionFlags.post
        }
        case 2 /* EDIT **/: {
            w -> _permission |= PermissionFlags.edit
        }
        case 3 /* DELETE **/: {
            w -> _permission |= PermissionFlags.delete
        }
    }    
}

void removePermission(writer* w, int type) {
    switch(type) {
        case 1 /* POST **/: {
            w -> _permission &= ~PermissionFlags.post
        }
        case 2 /* EDIT **/: {
            w -> _permission &= ~PermissionFlags.edit
        }
        case 3 /* DELETE **/: {
            w -> _permission &= ~PermissionFlags.delete
        }
    }
}

int main() {
    writer* w1 = malloc(sizeof writer);
    writer* w2 = malloc(sizeof writer);
    writer* w3 = malloc(sizeof writer);

    w1 -> _permission = PermissionFlags.post | PermissionFlags.edit;
    w2 -> _permission = PermissionFlags.edit | PermissionFlags.delete;
    w3 -> _permission = PermissionFlags.delete | PermissionFlags.post | PermissionFlags.edit;

    // play around here

    return 0;
}

Use Case: Angular

Angular made a very heavy use of bitmasks.

• NodeFlags
• ViewState
• DepFlags
• BindingFlags
• ViewFlags

We will look into ViewState because it handles Change Detection which is very vital in any JS framework.

// @angular/core/src/view/types.ts

//...

/**
 * Bitmask of states
 */
export const enum ViewState {
  BeforeFirstCheck = 1 << 0,
  FirstCheck = 1 << 1,
  Attached = 1 << 2,
  ChecksEnabled = 1 << 3,
  IsProjectedView = 1 << 4,
  CheckProjectedView = 1 << 5,
  CheckProjectedViews = 1 << 6,
  Destroyed = 1 << 7,

  // InitState Uses 3 bits
  InitState_Mask = 7 << 8,
  InitState_BeforeInit = 0 << 8,
  InitState_CallingOnInit = 1 << 8,
  InitState_CallingAfterContentInit = 2 << 8,
  InitState_CallingAfterViewInit = 3 << 8,
  InitState_AfterInit = 4 << 8,

  CatDetectChanges = Attached | ChecksEnabled,
  CatInit = BeforeFirstCheck | CatDetectChanges | InitState_BeforeInit
}

Each state has its own bit.

BeforeFirstCheck =  00000001,
  FirstCheck =        00000010,
  Attached =          00000100,
  ChecksEnabled =     00001000,
  IsProjectedView =   00010000,
  CheckProjectedView  00100000,
  CheckProjectedViews 01000000,
  Destroyed =         10000000,

// InitState uses 3 bits off to diff

  InitState_Mask =                    11100000000,
  InitState_BeforeInit =              00000000,
  InitState_CallingOnInit =           100000000,
  InitState_CallingAfterContentInit = 1000000000,
  InitState_CallingAfterViewInit =    1100000000,
  InitState_AfterInit =               10000000000,

CatDetectChanges combines states Attached and ChecksEnabled

Attached      00000100 |
ChecksEnabled 00001000
              --------
              00001100
              --------
CatDetectChanges = 00001100

See bits Attached and ChecksEnabled are set: 00001100

Also, CatInit combines states BeforeFirstCheck ,CatDetectChanges, InitState_BeforeInit

BeforeFirstCheck     00000001 |
CatDetectChanges     00001100
InitState_BeforeInit 00000000
                     --------
CatInit =            00001101
                     --------

You know CatDetectChanges has both Attached and ChecksEnabled flags set. So CatInit also has their flags set along with BeforeFirstCheck and InitState_BeforeInit.

An Angular app is made up of tree of views, each view represents a UI section of the app. Angular renders these views from the root of the tree up to the branches recursively.

On initialization, Angular gives each view a ViewState flag. This flag holds info on whether to render the view or not. And each view on creation is given the CatInit state.

function createView(...): ViewData {
  // ...
  const view: ViewData = {
    //...
    state: ViewState.CatInit, root, renderer,
    oldValues: new Array(def.bindingCount), disposables,
    initIndex: -1
  };
  return view;
}

When a change in the app’s state is captured, a change detection cycle is triggered and UI re-render is initiated.

During UI re-render of the views, the function checkAndUpdateView passes the current view to this function callViewAction.

function callViewAction(view: ViewData, action: ViewAction) {
  const viewState = view.state;
  switch (action) {
    // ...
    case ViewAction.CheckAndUpdate:
      if ((viewState & ViewState.Destroyed) === 0) {
        if ((viewState & ViewState.CatDetectChanges) === ViewState.CatDetectChanges) {
          checkAndUpdateView(view);
        } else if (viewState & ViewState.CheckProjectedViews) {
          execProjectedViewsAction(view, ViewAction.CheckAndUpdateProjectedViews);
        }
      }
      break;
    // ...
  }
}

This function checks whether view state is not destroyed. If not it checks if the CatDetectChanges flags in the view are set. If they are all set it renders the current view, if not the view is not rendered.

See, the use of AND &, like we did in performAction function in our blog example. If the CatDetectChanges flags are set on viewState, the AND operation will return the same flag.

CatDetectChanges = 00001100
viewState =        00001101 (views are created with CatInit flags)

check CatDetectChanges is set in viewState

CatDetectChanges = 00001100 &
viewState =        00001101
                   --------
          result = 00001100
                   --------
the result is the same as CatDetectChanges, so it is set and the view gets rendered.

For some reasons, a view can be chosen not to be rendered. This is done by ViewRef_ class:

export class ViewRef_ implements EmbeddedViewRef<any>, InternalViewRef {
  //...
  detach(): void { this._view.state &= ~ViewState.Attached; }

  reattach(): void { this._view.state |= ViewState.Attached; }
}

The method detach removes a view from the tree of views, it doesn’t actually remove like cutting off but, disabling sorta thing.

It flips the bits of the Attached state to its inverse and runs the AND operation against the view’s state (like we did in removePermission function in the blog example). The result is then, stored in the view’s state.

To remove a state from a combination of states, the bits of the state are inversed and ANDed against the combination of states. The result then becomes the combination of states.

So, you see, the Attached was set. To detach, the Attached state has to be removed. That’s why the Attached flag in the ViewState object was used.

In reality, let’s say we have a view:

const view = {
    state: CatInit //00001101
}

To disable this view, ie to stop from being rendered. We do this:

//...
const viewRef = new ViewRef_()
viewRef.detach(view)

what really happen:

view.state =            00001101 //CatInit
Attached = 00000100 ~ = 11111011 &
                        --------
view.state =            00001001
                        --------

check Attached state is set.

view.state = 00001001 &
Attached =   00000100
             --------
             00000000 - Attached state not set
             --------

Remember, CatDetectChanges sets Attached and ChecksEnabled 00001100.

Next, the reattach method sets the removed Attached flag. See it uses the OR | operator. Just like we did in our givePermission function in our blog example.

//...
const viewRef = new ViewRef_()
viewRef.detach(view)

what really happen:

view.state =            00001101 //CatInit
Attached = 00000100 ~ = 11111011 &
                        --------
view.state =            00001001
                        --------

check Attached state is set.

view.state = 00001001 &
Attached =   00000100
             --------
             00000000 - Attached state not set
             --------

// To reattach `Attached` state
viewRef.reattach(view)

what happens:

view.state = 00001001 (the current state) |
Attached =   00000100
             --------
view.state = 00001101
             --------
check Attached state is set.

view.state = 00001101 &
Attached =   00000100
             --------
             00000100 - the Attached state is now set
             --------

Conclusion

We covered a lot here on bitmasks:

• &, <<, >>, | operators.
• Turning bits on and off.
• Querying status of bits.
• Combining bits.
• Blog and Angular examples to demonstrate their usage.

If you have any question regarding this or anything I should add, correct or remove, feel free to comment, email or DM me. It would be nice if you would play around with the blog example 🙂 Cheers!