Start Bit Manipulation Here

4824

A few days ago, I started learning Bit Manipulation, but it was really difficult to get into and I couldnt come up with any of the solutions. I didnt want to master the topic since it is rarely asked in tech interviews but still I wanted to be able to understand the classical problems.

So I made a list of Important Operators, ideas, and techniques that you will encounter everywhere in Bit Manipulation questions. Once you get familiar with these, your vocabulary will good enough to be able to understand solutions in the discuss tab and you will be able to think at a higher abstraction level.

I assume you are familiar with the basic operators, binary expansions and "get" and "set" bit concepts since there are already tons of posts and videos explaining that.

cout << bitset< 8 >( a ) to get the binary representation of a number
Comes in handy for debugging

^ for cancelling out same bits.
Cancels duplicacy.
Can be used to find single element among duplicates.

<< shift operators.
It is used left shift bits.
1 << i is used to make mask with ith set bit.
a << 1 shifts one bit to the left and vice versa for right shift.

& used to check if ith bit is set using a & ( 1 << i ) [ getting / checking ith bit of a ]

| used to set ith bit using a = a | ( b << i ) [ setting ith bit of a according to b ]

~ used to make masks with the complement of the number.

After working through these concepts on paper and internalising them. You are now ready to go on a solving spree. Below is a list of highly important Bit manipulation problems from interview point of view and I highly recommed you go through them. You will find the above snippets plenty of times in these questions and you will have less trouble going through them.

P.S. Will keep updating this post.

Comments (4)