Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement - Bit Stuffing
2.1.
Example
2.2.
Approach
2.3.
Program
2.4.
Complexity Analysis
3.
Problem Statement - Bit De-stuffing
3.1.
Example
3.2.
Approach
3.3.
Program
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is bit stuffing and Destuffing?
4.2.
What is character stuffing and Destuffing?
4.3.
What is the difference between byte stuffing and bit stuffing?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Bit Stuffing and Bit Destuffing

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Starting with the most intuitive brute force solution is the best way to approach a problem. After you've solved it, see if you can improve it in any way. Optimization techniques depend on the nature of the problem and its data structures. Sorting, for example, can often improve the complexity of array and string problems.

These optimization strategies are the result of a lot of trial and error. Try to think about why you've done it and what you've done to find the patterns in question.

Bit Stuffing and Bit Destuffing

Today we'll look at an array problem that appears to be about bits. So, let the party begin.

You can also check, Difference Between Analog and Digital Computer

Problem Statement - Bit Stuffing

You are given an array ‘ARR’ of 0s and 1s. You have to insert a zero in the array such that there are no more than five consecutive 1s in the array.

Example

Bit Stuffing Example

Approach

Let's have a look at what bit stuffing implies. If we have an array of 0s and 1s, we must check if there are any series of 1s whose length is longer than 5, and if so, we must insert a 0 to ensure that there is no series of 1s whose length is longer than 5.

The simplest solution is to loop through the array and count the number of ones, then insert a 0 between them if the count is greater than 5.

Now that we’ve discussed the approach, let’s see how the algorithm works.

  • Initialize a variable 'i', 'COUNT', and an array ‘ANS’ to store the current index, the count of consecutive 1s, and the answer array respectively.
  • Next, loop through the array and if the current element is 1, we will increment ‘i’ until ‘i < ARR.size() and ARR[i] == 1 && COUNT <= 5’ to get the length of series of 1s, and insert the elements in the ‘ANS’ as well..
  • If the length of the current series is greater than 5, we insert a 0 in the ‘ANS’ array if the current element is not zero. Otherwise, insert ARR[i].
  • Next, increment index, ‘i’ and update ‘COUNT’ to zero.

Let’s try to code this solution now.

Program

#include <iostream>
#include <vector>
using namespace std;

// Function for Bit Stuffing.
vector<int> bitStuffing(vector<int> &arr)
{
   // Initialize 'i' with zero to store the current index.
   int i = 0;
   
   // Initialize 'COUNT' with zero to store the count of consecutive 1s.
   int count = 0;
   
   // Declare a vector, 'ANS' to store the array after bit stuffing.
   vector<int> ans;
   
   // Loop through the array.
   while (i < arr.size())
   {
       // Count the number of consecutive 1s.
       while (i < arr.size() && arr[i] == 1 && count < 5)
       {
           ans.emplace_back(arr[i]);
           i++;
           count++;
       }
       
       // If the count of consecutive 1s is greater than five. Skip if the next element is zero, otherwise push a zero..
       if (arr[i] == 0)
       {
           ans.emplace_back(arr[i]);
           i++;
       } else if (count == 5)
       {
           ans.emplace_back(0);
       }
      
       count = 0;
   }
   return ans;
}

// Main.
int main()
{
   int n;
   cout << "Enter the size of the array: ";
   cin >> n;
   vector<int> arr(n);
   cout << "Enter the elements in the array: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   cout << "Before Bit Stuffing: ";
   for (int i = 0; i < n; i++)
   {
       cout << arr[i] << "  ";
   }
   cout << endl;
   arr = bitStuffing(arr);
   cout << "After Bit Stuffing: ";
   for (int i = 0; i < arr.size(); i++)
   {
       cout << arr[i] << "  ";
   }
   cout << endl;
   return 0;
}

Input

Enter the size of the array: 12
Enter the elements in the array: 0 1 1 0 1 1 1 1 1 1 1 0

Output

Before Bit Stuffing: 0 1 1 0 1 1 1 1 1 1 1 0
After Bit Stuffing: 0 1 1 0 1 1 1 1 1 0 1 1 0

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the size of the array ‘ARR’.

Since we traverse the array once, the time complexity is O(N).

Space Complexity

O(N),  where ‘N’ is the size of the array ‘ARR’.

As we are only initializing vector ‘ANS’ of size ‘N’. Hence the space complexity is O(N).

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement - Bit De-stuffing

Bit De-stuffing is the complete opposite of Bit Stuffing. You are given an array 'ARR' of 0s and 1s, and if there are five consecutive 1s followed by a 0, you have to remove this 0 from the array.

Example

Bit De-stuffing example

Approach

The opposite of Bit Stuffing is Bit De-stuffing. To de-stuff the array, all we have to do is loop through it and see if there are any length five series of 1s followed by a zero. If that's the case, we'll get rid of the zero. Let's take a look at how the algorithm functions.

  • Initialize a variable 'i', 'COUNT', and an array ‘ANS’ to store the current index, the count of consecutive 1s, and the answer array respectively.
  • Next, loop through the array till we encounter 1 in the array.
  • If we encounter zero, check if the COUNT has the value 5. If not, then insert the current element in the array otherwise skip the current element.
  • Increment ‘i’ and update the value of ‘COUNT’ to zero.

Let’s code the solution now.

Program

#include <iostream>
#include <vector>

using namespace std;

// Function for Bit De-Stuffing.
vector<int> bitDeStuffing(vector<int> &arr)
{
  // Initialize 'i' with zero to store the current index.
  int i = 0;

  // Initialize 'COUNT' with zero to store the count of consecutive 1s.
  int count = 0;

  // Declare a vector, 'ANS' to store the array after bit de-stuffing.
  vector<int> ans;

  // Loop through the array.
  while (i < arr.size())
  {
      // Count the number of consecutive 1s.
      while (i < arr.size() && arr[i] == 1)
      {
          ans.emplace_back(arr[i]);
          i++;
          count++;
      }

      if (i == arr.size())
          break;

      // If the count of consecutive 1s is not five, insert current element in the 'ANS' array.
      if (count != 5)
      {
          ans.emplace_back(arr[i]);
      }

      // Otherwise, don't insert the element.
      i++;

      // Update the 'COUNT' variable to 0.
      count = 0;
  }

  return ans;
}

// Main function.
int main()
{
  int n;
  cout << "Enter the size of array: ";
  cin >> n;
  vector<int> arr(n);

  cout << "Enter the elements in the array: ";
  for (int i = 0; i < n; i++)
  {
      cin >> arr[i];
  }

  cout << "Before Bit De-stuffing: ";
  for (int i = 0; i < n; i++)
  {
      cout << arr[i] << "  ";
  }
  cout << endl;

  arr = bitDeStuffing(arr);

  cout << "After Bit De-stuffing: ";
  for (int i = 0; i < arr.size(); i++)
  {
      cout << arr[i] << "  ";
  }
  cout << endl;

  return 0;
}

Input

Enter the size of array: 12
Enter the elements in the array: 0 1 1 0 1 1 1 1 1 0 1 0

Output

Before Bit De-stuffing: 0 1 1 0 1 1 1 1 1 0 1 0
After Bit De-stuffing: 0 1 1 0 1 1 1 1 1 1 0

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the size of the array ‘ARR’.

Since we are traversing the array once, the time complexity is O(N).

Space Complexity

O(N),  where ‘N’ is the size of the array ‘ARR’.

As we are only initializing vector ‘ANS’ of size ‘N’. Hence the space complexity is O(N).

Frequently Asked Questions

What is bit stuffing and Destuffing?

Bit stuffing is a method of breaking up a message's sequence for synchronisation purposes by introducing one or more non-information bits into the message that will be delivered. The reverse of bit stuffing is bit destuffing. The receiver automatically destuffs (i.e., deletes) the 0 bit when it observes five consecutively incoming I bits followed by a 0 bit.

What is character stuffing and Destuffing?

Character stuffing, commonly referred to as byte stuffing or character-oriented framing, is similar to bit stuffing in that it manipulates bits, whereas byte stuffing manipulates bytes. Stuffing is the opposite of character destuffing.

What is the difference between byte stuffing and bit stuffing?

When a byte is stuffed into the message to distinguish it from the delimiter, it is referred to as byte-stuffing. Also known as character-oriented framing, this technique. Bit-stuffing is the practise of inserting a pattern of bits into a message to distinguish it from the delimiter. Additionally known as bit-oriented framing.

Conclusion

We’ve solved bit stuffing and de-stuffing by the most straightforward and intuitive approach, i.e., looping through the array and tracking the count of consecutive 1s. This problem was a pure, simple understanding of using loops in arrays.

Check out this course on Bit Manipulation in Competitive Programming 

Recommended Problems


On the Coding Ninjas Platform, we have various such problems and blogs. Additionally, Coding Ninjas has recently introduced the Coding Ninjas Studio Test Series, a dedicated test series for acing interviews.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Java Basics, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Thank you. I hope this blog has been helpful to you.

Previous article
Maximize Bitwise AND of the array by replacing at most one element
Next article
Space optimization using bit manipulations
Live masterclass