I start my journey in CP !

Since I started my journey in preparing for coding interview. I encounter a lot of websites that provide questions in preparing in coding interview. I was struggle a lot in a lot of the quesitons at first. But after hours spending on practice, I start enjoy doing algorithms and want to start CP as a side hoppy. I still struggle in a lot of topics in CP. As such, I thought I would want to start sharing some of knowledge I gain on my journey in getting better at CP. The first topic that I would want to improve is bit manipulation.

My experience with bit manipulation.

Bit manipulation was one of the topic, I would like to improve. Some of the problems in CP can be solved using bit. When I first ecountered bit problems, I was amazed at that some of the problems could be solved in constant time.

Bitwise operators operate on a bit string, a bit array or binary numeral at the level of its individual bits.

Some useful bitwise operations:

Not (~) : Flip the bit of a number. For example: 1 -> 0, 0 -> 1

And (&): Bitwise AND operate on number of equal lengths:

1 & 1 -> 1

1 & 0 -> 0

0 & 1 -> 0

0 & 0 -> 0

OR (|): Bitwise OR operate on number of equal length:

1 & 1 -> 1

1 & 0 -> 1

0 & 1 -> 1

0 & 0 -> 0

XOR (^): Bitwise Exclusive OR operate on number of equal length:

1 ^ 1 -> 0

1 ^ 0 -> 1

0 ^ 1 -> 1

0 ^ 0 -> 0

Left shift (<<): shift every bit to the left.

Right shift (>>): shift every bit to the right.

---

Bit facts and tricks.

Q1: get the complement of positive number ?

Brute force:

 public int getComplement(int num){
   int todo = num, bit = 1; 
   while(todo != 0){
     num = num ^ bit; 
     bit = bit << 1;
     todo = todo >> 1;
   }
   return num
 }

JDK algorithms (O(1) time and space))

public int getComplement(int num){
    int mask = num; 
    // create 32 bit mask of 1
    mask |= mask >> 2;
    mask |= mask >> 4; 
    mask |= mask >> 8; 
    mask |= mask >> 16;
    
    return mask ^ num;  

}

If you are a visual learner ?

#bitwise #cs