Bit Masking

Lightweight, small sets of Booleans (native support in C/C++/Java). An integer is stored in a computer’s memory as a sequence/string of bits.

" In computer science, a mask is data that are used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word (etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation " [Mask (computing)]

The binary representations can be used to hold information about subsets of a set.

Ex:  Consider the set/list A = {a, b, c, d, e, f} or set/list B = {10, 20, 25, 15, 30, 40}

We can represent the set B as {1, 1, 1, 1, 1, 1} (the sub set which has all the element)
Sub set {20, 15} of set B can be represent as {0, 1, 0, 1, 0, 0} (20 in decimal format)

• We can multiply/divide using bit shifting

int s = 34;         // 0100010
int a = 34 << 1;    // 1000100 ; this is equal to 34*2 ; 100010 << 1 => 1000100
int b = 34 >> 1;    // 0010001 ; this is equal to 34/2 ; 100010 >> 1 => 0010001
int c = 34 >> 2;    // 0001000 ;

//Notice that the truncation in the shift right operation automatically rounds the division-by-2 down

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• To clear/turn off the j-th item of the set. Use bitwise AND operation S &= ~(1 << j)

int s = 38;  // 100110
int j = 2;  // 0-based index
int a = ~(1 << j);  // 111011
int res = s & a;  // 100010

• To check if the j-th item of the set is on, use the bitwise AND operation T = S & (1 << j)

int s = 38;   // 100110
// is 2nd item is on
int j = 2;
int a = (1 << j); // 000100
int t = s & a;  // 000100 , not zero, to be precise it is (t = a) so 2nd item is on
  
// is 3nd item is on
j = 3;
a = (1 << j);  // 001000
t = s & a;  // 000000 , zero , so 2nd item is off

• To toggle (flip the status of) the j-th item of the set, use the bitwise XOR operation S ^= (1 << j)

int s = 40;  // 101000
int j = 2;
int a = (1 << 2); // 000100
s = s ^ a;  // 101100 , turned on
s = s ^ a;  // 101000 , turned off

• To get the value of the least significant bit that is on (first from the right), use T = (S & (~S))

int s = 40;  // 00000000000000000000000000101000
int nS = -40; // 11111111111111111111111111011000 (two’s complement)
int t = s & nS; // 1000 , 8, 3rd bit from the right is on

• To turn on all bits in a set of size n, use S = (1 << n) - 1
• Iterate through all subsets of a set of size n

int n = 5;
for ( int x = 0; x < (1 << n); ++x ){
 // loop will go for (1 << n) turns
}

• Example of usage

 
for (int i = 0; i < (1 << n); ++i) {  // for each subset, O(2^n)
 for (int j = 0; j < n; ++j) {   // check membership, O(n)
  if ((i & (1 << j)) != 0) {   // test if bit ‘j’ is turned on in subset ‘i’ ?
   // if yes, process ‘j’
  }
 }
}

References : Competitive Programming books

Posted in: