Introduction
Technical interviews at large tech companies such as Facebook, Google, Netflix etc … will test your understanding of fundamental Computer Science techniques.
Bit manipulation questions come up frequently and are intended to test one’s fluency with working with unary bit operators such as: ^ (xor), | (or), & (and), << (left shift), >> (right shift), ~ (not).
For example to check if the 3rd bit of the integer 7 is set (7 is represented as 0111 in binary), all we have to do is the following: (0111) & (1 << 2).
The operation (1 << 2) tells us that we are shifting the integer 0001, two positions to the left, so that it becomes 0100 and the 1 occupies the third position from the right. Then we use the bitwise AND operator, &, to check whether we have a non-zero value: 0111 & 0100 = 0100. This tells us the third bit is set.
So the general formula to determine if the ith bit is on for an integer x, is x & (1 << i-1).
In most interview questions bit manipulation will be simply a tool that we can use to solve a problem and it may not be obvious the question is asking for bit manipulation from the question itself.
An Example
Let's look at an example problem. We have an M x N matrix made up of 0s and 1s where 0 (represents dead) and 1 (represents live). Each cell interacts with all of its eight neighbors (horizontal, diagonal, vertical) according to the following rules:
- A live cell with < 2 live neighbors dies
- A live cell with 2 or 3 live neighbors lives
- A live cell with > 3 neighbors dies
- A dead cell with 3 live neighbors becomes alive
This question asks us to compute the next state of the matrix without utilizing another matrix.
The key insight to solve this problem is to realize that each cell utilizes exactly a single bit to store information even though each cell is made up of 32-bit integers. Thus we can solve this problem by storing the next state in the second least significant bit position and when we are done processing every cell we can shift the value in the second bit back to the least significant bit and return the answer in the original matrix we were given. The solution follows below.
Observe that in line 19 n the number of neighbors and we perform a bitwise OR (|) with the value. If we have a live cell denoted by the integer 1, 01 then the bitwise or of n=2, 10 or n=3 11 and 1 will always be three and we set the second bit by adding 2. For a dead cell, 00, we set the second bit only if the count is n=3, 11 which will result in a value of three when we do 00 | 11.
Finally we move the second bit values to the first bit and place the matrix in its final position.
Some Bit Tricks
Set ith bit: num |= num & (1 << i)
Clear ith bit: num &= ~(1 << i)
Clear least significant set bit: num &= num-1
Practice Problems
EASY
○ Majority Element (hint: try bit by bit construction)
MEDIUM
○ Game of Life (hint: see example above)
○ Maximum XOR of Two Numbers in an Array (hint: try bit by bit construction)
○ Subsets
HARD
○ Minimum One Bit Operations to Make Integers Zero
To learn more about Bit Manipulation refer to the following excellent post.
