Programming Tips And Tricks For Problem-solving

Ideas and Tricks

Unique ID for matrix cells

Use id = row*colSize + col where row and col are the row and column indices of the cell in a matrix/grid. For example, id can be used as a key for a hash table.

Bit Manipulation

Check/Set/Clear/Flip a bit

bool isSet = (mask&(1<<i)) == 0; //check bit
mask |= (1LL << i); //set bit
mask &= ~(1LL << i); //clear bit
mask ^= (1LL << i); //flip bit

// 1<< i makes an integer with only the i-th bit set

Test if a mask contains another mask

bool contains = (mask&sub) == sub;

Turn off the Lowest Set Bit (LSB)

mask = mask & (mask - 1);

//subtracting 1 flips the lowest 1 to 0 and all the trailing 0s to 1; AND removes the lowest 1
//Use cases: iterate through set bits fast, DP transitions

Isolate the Lowest Set Bit (lowbit)

int lsb = mask & -mask;

//-mask is two's complement; AND isolates the lowest set bit
//Use cases: Fenwick tree, extracting one bit at a time