Beginner's Guide to Bit-Manipulation: Day 1 Tutorial

Hello there!, we'll be covering Bit-Manipulation concepts (A-Z) and some essential tactics required to tackle DSA problems based on Bit-Manipulation.

Today's Goals:

• Convert decimal to binary

• Convert binary to decimal

1. Convert Decimal to Binary

Convert 13 (decimal) to binary:

• Initialization : res = "";

• Iteration : while(13 is not 0)

  1. Divide 13 by 2:

     • Quotient: 6

     • Remainder: 1 ---> (13%2==1) res.add(1), set 13 to floor(13/2) i.e 6

  2. Divide 6 by 2:

     • Quotient: 3

     • Remainder: 0 ---> (6%2==0) res.add(0), set 6 to floor(6/2) i.e 3

  3. Divide 3 by 2:

     • Quotient: 1

     • Remainder: 1 ---> (3%2==1) res.add(1), set 3 to floor(3/2) i.e 1

  4. Divide 1 by 2:

     • Quotient: 0

     • Remainder: 1 ---> (1%2==1) res.add(1), set 1 to floor(1/2) i.e 0

• Write the Remainders in Reverse Order: The binary representation is 1101.

Code :

string decimalToBinary(int n) {
    if (n == 0) return "0"; // Special case for 0

    string res = "";
    while (n > 0) {
        res += (n % 2) + '0'; // Convert remainder to character and append
        n = n / 2; // Update number
    }

    // Reverse the digits to get the correct binary representation
    reverse(res.begin(), res.end());
    return res;
}

2. Converting Binary to Decimal

Convert 1101 (binary) to decimal

• Initialization:

  • Start with binary = "1101" and decimal = 0.

Process:

1. Start from the Rightmost Bit:

   • Bit: 1 (rightmost bit, position 0)

     • Value: 1×20=11 \times 2^0 = 11×20=1

     • Update decimal: 0+1=10 + 1 = 10+1=1

   • Bit: 0 (next bit, position 1)

     • Value: 0×21=00 \times 2^1 = 00×21=0

     • Update decimal: 1+0=11 + 0 = 11+0=1

   • Bit: 1 (next bit, position 2)

     • Value: 1×22=41 \times 2^2 = 41×22=4

     • Update decimal: 1+4=51 + 4 = 51+4=5

   • Bit: 1 (leftmost bit, position 3)

     • Value: 1×23=81 \times 2^3 = 81×23=8

     • Update decimal: 5+8=135 + 8 = 135+8=13

• Result: The binary representation 1101 converts to 13 in decimal.

• Code :

int binaryToDecimal(const string& binary) {
    int decimal = 0;
    int power = 0;

    // Process each bit from right to left
    for (int i = binary.size() - 1; i >= 0; --i) {
        if (binary[i] == '1') {
            decimal += pow(2, power); // Add 2^power if the bit is 1
        }
        power++;
    }

    return decimal;
}

That's all for today.