Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Space optimization using bit manipulations
2.1.
Example
2.2.
Approach 1 (Simple):
2.3.
Approach 2 (Better than straightforward):
2.4.
Approach 3 (Using Bit Manipulations):
2.5.
Code
3.
Frequently Asked Questions
3.1.
Why is bit control significant?
3.2.
How would you find the force of 2 utilizing bit control?
3.3.
How helpful are bitwise activities?
3.4.
Why is space advancement significant?
3.5.
What is space improvement?
4.
Conclusion
Last Updated: Mar 27, 2024

Space optimization using bit manipulations

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

Introduction

Space advancement is a computerized interaction for distinguishing properties that can be abandoned by moving the tasks and resources inside those properties to different properties with appropriate abundance space. Bit control is the demonstration of algorithmically controlling pieces or other bits of information more limited than a word. PC programming undertakings that require digit control incorporate low-level gadget control, blunder discovery and adjustment calculations, information pressure, encryption calculations, and enhancement.

Space optimization using bit manipulations

There are numerous circumstances where we use whole number qualities as files in the cluster to see presence or nonattendance; we can utilize bit controls to streamline space in such issues.

Allow us to consider underneath issues, for instance.

Given two numbers, say an and b, mark the products of 2 and 5 among an and b utilizing not exactly O(|b - a|) space and result in every one of the products.

Note: We need to stamp the products, i.e., save (key, esteem) matches in memory with the end goal that each key has affection as 1 or 0 addressing as various of 2 or 5 or not separately.

Example

Input : 2 10

Output : 2 4 5 6 8 10

Input: 60 92

Output: 60 62 64 65 66 68 70 72 74 75 76 78 80 82 84 85 86 88 90 92 

Approach 1 (Simple):

Hash the lists in an exhibit from a to b and imprint every one of the records as 1 or 0.

Space complexity : O(max(a, b))

Approach 2 (Better than straightforward):

Save memory by interpreting a to 0th record and b to (b-a)th list.

Space complexity : O(|b-a|).

Approach 3 (Using Bit Manipulations):

Here is a space improvement that utilizes a bit control procedure applied to issues planning two-fold qualities in exhibits.

The size of the int variable in the 64-cycle compiler is 4 bytes. Eight cycle positions in memory address one byte. Thus, 32 cycle positions(4 Bytes) address a whole number in memory. These 32 digit positions can be utilized rather than only one file to hash paired valuesC

Code

// C++ code to for marking multiples
#include <bits/stdc++.h>
using namespace std;

// index >> 5 corresponds to dividing index by 32
// index & 31 corresponds to modulo operation of
// index by 32

// Function to check value of bit position whether
// it is zero or one
bool checkbit(int array[], int index)
{
    return array[index >> 5] & (1 << (index & 31));
}

// Sets value of bit for corresponding index
void setbit(int array[], int index)
{
    array[index >> 5] |= (1 << (index & 31));
}

/* Driver program to test above functions*/
int main()
{
    int a = 2, b = 10;
    int size = abs(b - a);

    // Size that will be used is actual_size/32
    // ceil is used to initialize the array with
    // positive number
    size = ceil(size / 32);
   
    // Array is dynamically initialized as
    // we are calculating size at run time
    int* array = new int[size];

    // Iterate through every index from a to b and
    // call setbit() if it is a multiple of 2 or 5
    for (int i = a; i <= b; i++)
        if (i % 2 == 0 || i % 5 == 0)
            setbit(array, i - a);

    cout << "MULTIPLES of 2 and 5:\n";
    for (int i = a; i <= b; i++)
        if (checkbit(array, i - a))
            cout << i << " ";

    return 0;
}
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

Frequently Asked Questions

Why is bit control significant?

Current programming dialects permit the developer to work straightforwardly with deliberations rather than bits addressing those reflections for most different errands. Cycle control can deter or decrease the need to circle over an information structure and accelerate coding as digit controls are handled equally.

How would you find the force of 2 utilizing bit control?

On the off chance that (x and (x-1)) are zero, the number is a force of 2. For instance, let x be 8 ( 1000 in paired); then, at that point, x-1 = 7 ( 0111 ). This results in the piece's force of 2.

How helpful are bitwise activities?

For the most part, bitwise tasks become an integral factor when you want to encode/unravel information in a reduced and quick way.

Why is space advancement significant?

Without successful space arranging, tasks or whole homes and structures can come short on a solid feeling of format and capacity that makes them alluring and usable.

What is space improvement?

Space advancement is a computerized interaction for recognizing properties that can be cleared by moving the tasks and resources inside those properties to different properties that have appropriate overabundance space.

Conclusion

From the above article, we understand that Space advancement is a computerized interaction for distinguishing properties that can be abandoned by moving the tasks and resources inside those properties to different properties with appropriate abundance space. Bit control is the demonstration of algorithmically controlling pieces or other bits of information more limited than a word. There are numerous circumstances where we use whole number qualities as files in the cluster to see presence or nonattendance; we can utilize bit controls to streamline space in such issues.
Check out this problem - Maximum Product Subarray

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in PygameCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Bit Stuffing and Bit Destuffing
Next article
Find the maximum product of Bitwise AND and Bitwise OR of K-size subarray
Live masterclass