Bit Manipulation | Eliezer Abate

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), \> (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 \ 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.

Applying above rules to 4 x 3 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.