Simple explanation of Bit Manipulation for DSA in Javascript | Bit Masking

This is the second part of the Bit Manipulation two-blog series. Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Bit manipulation is something that has constant time complexity. Bitwise operators are used in programming to manipulate bits, as well as for some boolean operations. In this tutorial, we’re going to go over what Bit Masking is and common Bit manipulation operations.

What is BIT Masking?

A bitmask is a set of Booleans (native support in C/C++/Java) that can be used to represent a lightweight set of Boolean values. All set operations involve the manipulation of these small integer numbers, which makes them much faster than the STL vector, bitset, and set options.

In other words, Bit Masking is a set of operations where we allow only certain bits to pass through while blocking/masking a few other bits.

Example

Let’s say we have an array of numbers [1, 2, 3, 4, 5], and we want to find all the possible subsets of this array. We can represent each subset using a binary number, where each bit corresponds to a particular element in the array. If the bit is 1, it means the element is included in the subset; if the bit is 0, the element is not included.

For example, the binary number 10101 represents the subset [1, 3, 5], because the first, third, and fifth bits are 1 (counting from right to left), indicating that the corresponding elements are included in the subset.

Also read, Basic operations in Graph Data structure

List of Bitwise operators

Bitwise operators are used to manipulate data at the bit level. They are used to make numerical computations faster.

Bitwise operators work on given data bit by bit, starting from the Least Significant Bit (LSB)(rightmost bit) to the Most Significant Bit (MSB)(leftmost bit).

Note – Bitwise operator is only applied to integer data types than float or double data types due to its compatibility.

Bitwise And

Bitwise AND operators result in 1 when both operands are 1 otherwise, the result is always 0. It is represented by & a sign.

x	y	x & y
0	0	0
0	1	0
1	0	0
1	1	1

Bitwise OR

Bitwise Or operators result in 1 when both or any operands are 1 otherwise, the result is always 0. It is represented by the | sign.

x	y	x | y
0	0	0
0	1	1
1	0	1
1	1	1

Bitwise NOT

The Bitwise NOT operator or Bitwise complement operator works with only one operand (unary operator). When the Bitwise NOT operator is applied on operands, it changes all the 1 bits into 0 and vice versa. It is represented by the ~ sign.

x	~ x
0	1
1	0

Also read, Simple Explanation on BFS and DFS Graph Traversal Methods

Bitwise XOR

Bitwise XOR operators result in 1 when only one operand is 1 otherwise, the result is always 0. It is represented by a ^ sign.

x	y	x & y
0	0	0
0	1	1
1	0	1
1	1	0

Bitwise Left & Right Shift

Bitwise shift operators are used to shift the bit patterns either left or right. They are represented as << for the left shift operator or >> for the right shift operator.

Syntax

Operand << n (Left Shift)
Operand >> n (Right Shift)

Here,

• an operand is an integer on which we perform the shift operation.
• ‘n’ is the total number of bit positions that we need to shift in the integer expression.

Example

Let us find out the left shift and right shift values of the number 6.

// For Left shift operator
console.log( 6 << 2 ) // 24

// First we convert given integer into its binary value, 6 -> 00000110
// now we will shift towards left by 2
// now the bit becomes, 00011000, which is 24



// For Right shift operator
console.log( 6 >> 2 ) // 1

// First we convert given integer into its binary value, 6 -> 00000110
// now we will shift towards right by 2
// now the bit becomes, 00000001, which is 1

Also read, Simple Explanation of Tree traversal Operations with JavaScript

Amazing BIT Masking Tricks You Must Know

Finding ith BIT of any given number

If you want to find the bit value at the position of ith, for example,

let us find the 5th-bit value of the binary, 10110101,

• For that first we need to create the mask, we need to create a binary with the value right shift to 5, i.e 00010000, (1 << 5).
• After that, we will use the AND operator to AND mask and give binary.
• If the result is 1, then BIT at the 5th position was 1 otherwise 0.

Example

// find bit value of 3rd position

let number = 6

let mask = 1 << 3

let bit = number & mask

console.log('Bit value of 3rd position is ->', bit) // 0

Setting ith BIT of any given number

Setting ith BIT is also similar to finding the ith BIT, for example,

let us find the 3th-bit value of the binary, 10110101,

• For that first we need to create the mask, we need to create a binary with the value right shift to 3, i.e 00001000, (1 << 3).
• After that, we will use the OR operator to OR mask and give binary.
• Finally, our 3th-bit value of the binary becomes 1.

Example

// Set bit value of 3rd position to 1

let number = 6 
let mask = 1 << 3 
let bit = number | mask 

console.log('Bit value of 3rd position is ->', bit) // 0

Also read, Develop XR with Oracle, Ep 5 Healthcare, Vision AI, Training/Collaboration, and Messaging

Clearing ith BIT of any given number

Clearing ith BIT is also similar to setting the ith BIT, for example,

let us find the 3th-bit value of the binary, 10110101,

• For that first we need to create the mask, we need to create a binary with the value right shift to 3, i.e 00001000, (1 << 3);
• But to set the bit to 0, we first need to invert the mask using the complement operator, 11110111, ~(1<<3).
• After that, we will use the AND operator to AND mask and give binary.
• Finally, our 3th-bit value of the binary becomes 0.

Example

// Set bit value of 3rd position to 0

let number = 6 
let mask = 1 << 3 
let bit = number & ~mask 

console.log('Bit value of 3rd position is ->', bit) // 0

Number of BITs to change to convert a to b

You are given two numbers, i.e a and b, and we need to find how many BITs we have to change in order to convert a into b. For example,

Let the given number a be 10110 and b be 11011,

• To find the number of difference BIT in a and b numbers, we need to simply use the XOR operator.
• Applying XOR with a and b will give a number of bits we need to change, for example, 10110 ^ 110111 = 01101
• Now we can simply apply different techniques two find a number of 1 BIT in the numbers, here is a method you can apply to find a number of 1 BIT in the binary.

a & (a-1)

In order to find the number of Set BIT or 1 BIT, we need to run the loop till the number becomes 0 and increment each time count.

let a = 13 // 1101
let count = 0

while(a!=0){
   count++
   a = a & (a-1)
}

console.log(count)

Example

let a = 13 // 00001101
let b = 42 // 00101010
let diff = a ^ b // 0010111
let count = 0

while(diff!=0){
    count++
    diff = diff & (diff-1)
}

console.log('Number of BITs to change to convert a to b --',count) // 4

Also read, Introduction to Recursion – Learn In The Best Way with JavaScript | Part 1

Generating All the Subsets of a Set using Bit Masking

To generate all possible subsets, we can use a loop to iterate over all possible binary numbers with n bits (where n is the length of the array), and use bit masking to check which elements are included in each subset. Here’s some code to do that:

const arr = [1, 2, 3, 4, 5];
const n = arr.length;

for (let i = 0; i < (1 << n); i++) {
  const subset = [];
  for (let j = 0; j < n; j++) {
    if (i & (1 << j)) {
      subset.push(arr[j]);
    }
  }
  console.log(subset);
}

The 1 << n expression generates a binary number with n bits, where all bits are 0 except the leftmost bit, which is 1. This represents the number 2^n, which is the total number of possible subsets.

The inner loop iterates over the bits of the binary number i, and uses the bitwise AND operator (&) to check if the jth bit of i is 1. If it is, it means the jth element of the array is included in the subset, so we push it to the subset array.

The above code will output all possible subsets of the array:

[]
[ 1 ]
[ 2 ]
[ 1, 2 ]
[ 3 ]
[ 1, 3 ]
[ 2, 3 ]
[ 1, 2, 3 ]
[ 4 ]
[ 1, 4 ]
[ 2, 4 ]
[ 1, 2, 4 ]
[ 3, 4 ]
[ 1, 3, 4 ]
[ 2, 3, 4 ]
[ 1, 2, 3, 4 ]
[ 5 ]
[ 1, 5 ]
[ 2, 5 ]
[ 1, 2, 5 ]
[ 3, 5 ]
[ 1, 3, 5 ]
[ 2, 3, 5 ]
[ 1, 2, 3, 5 ]
[ 4, 5 ]
[ 1, 4, 5 ]
[ 2, 4, 5 ]
[ 1, 2, 4, 5 ]
[ 3, 4, 5 ]
[ 1, 3, 4, 5 ]
[ 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]

Also read, Simple and Best Explanation on Sliding Window Algorithm with Diagram

Few Examples of BIT Masking Problems with Solutions

Now lastly, let us see a few important problems so that we can employ Bitmasking in order to solve problems. But before moving forward I want you to remember two golden rules:-

Two Golden XOR Property

• a ^ a = 0
• a ^ 0 = a

Find only non-repeating element in an array where every other element repeats twice

Suppose you have an array of multiple numbers where all the elements appear twice except one, we have to find that number. ex, [5,4,1,4,3,5,1]

Explanation

We will use the XOR property to solve this problem, Just follow the following steps,

• Let’s take a variable res with the value 0 and XOR for each element of the array.
• Run a loop and whenever we do XOR of the same elements, it gets canceled and eventually, we will be only left with a non-repeating element.

Code

let arr = [5,4,1,4,3,5,1]

let res = 0

for(let i = 0; i < arr.length; i++){
    res = res ^ arr[i]
}

console.log(res) // 3

Also read, Simple explanation of Bit Manipulation for DSA in JavaScript | Number System

Final Words

Bitmasks are a beneficial concept that can help you avoid doing unnecessary work in your code. You may think that it’s mostly just something used by programmers, but there are actually many applications of bitmasks that go way beyond computer science.

If you like this article please share more it with friends, family, and colleagues, also do check out more detailed articles on DSA and also on various topics like React, JavaScript, Coding, and Java.