Binary Numbers

A binary number is a number expressed in the base-2 numeral system, which uses only two symbols: 0 and 1. Each digit in a binary number is called a bit. The binary system is the fundamental language of computers, as it aligns with their electronic circuitry, which operates in two states: on (1) and off (0).

Understanding Binary Numbers

In a binary number, each bit represents an increasing power of 2, starting from the rightmost bit. This is similar to how decimal numbers work, but instead of powers of 10, binary uses powers of 2.

For example, the binary number 1011 can be understood as:

1011 (binary) = 1×2^3 + 0×2^2 + 1×2^1 + 1×2^0
              = 8 + 0 + 2 + 1
              = 11 (decimal)

In this example:

• The rightmost bit (least significant bit) represents 2^0 = 1.
• The next bit represents 2^1 = 2.
• The next bit represents 2^2 = 4.
• The leftmost bit (most significant bit) represents 2^3 = 8.

So, the binary number 1011 is equivalent to the decimal number 11.

Decimal to Binary Conversion

To convert a decimal number (base-10) to a binary number (base-2), you repeatedly divide the decimal number by 2 and record the remainder. This method is called successive division. The binary number is obtained by reading the remainders from bottom to top (in reverse order).

Steps to Convert Decimal to Binary

1. Divide the decimal number by 2.
2. Record the remainder (either 0 or 1).
3. Continue dividing the quotient by 2, recording the remainders, until the quotient becomes 0.
4. Read the remainders in reverse order (from last to first). This will give the binary representation of the decimal number.

Example: Convert Decimal 13 to Binary

Let's walk through the process of converting 13 (decimal) to binary:

1. 13 ÷ 2 = 6, remainder = 1
2. 6 ÷ 2 = 3, remainder = 0
3. 3 ÷ 2 = 1, remainder = 1
4. 1 ÷ 2 = 0, remainder = 1 (stop here since the quotient is 0)

Now, take the remainders from bottom to top: 1101

So, 13 in decimal = 1101 in binary.

Example: Convert Decimal 45 to Binary

1. 45 ÷ 2 = 22, remainder = 1
2. 22 ÷ 2 = 11, remainder = 0
3. 11 ÷ 2 = 5, remainder = 1
4. 5 ÷ 2 = 2, remainder = 1
5. 2 ÷ 2 = 1, remainder = 0
6. 1 ÷ 2 = 0, remainder = 1 (stop)

Take the remainders from bottom to top: 101101

So, 45 in decimal = 101101 in binary.

Dry Run:

Initialization:

n = 13
         +----------+
binary = |   empty  |
         +----------+

First Iteration:

n = 13
         +----------+
binary = |   empty  |
         +----------+

remainder = n % 2
          = 13 % 2
          = 1

push remainder into binary

n = n / 2
  = 13 / 2
  = 6

Second Iteration:

n = 6
         +-----+
binary = |  1  |
         +-----+

remainder = n % 2
          = 6 % 2
          = 0

push remainder into binary

n = n / 2
  = 6 / 2
  = 3

Third Iteration:

n = 3
         +-----+-----+
binary = |  1  |  0  |
         +-----+-----+

remainder = n % 2
          = 3 % 2
          = 1

push remainder into binary

n = n / 2
  = 3 / 2
  = 1

Fourth Iteration:

n = 1
         +-----+-----+-----+
binary = |  1  |  0  |  1  |
         +-----+-----+-----+

remainder = n % 2
          = 1 % 2
          = 1

push remainder into binary

n = n / 2
  = 1 / 2
  = 0

Loop Termination:

n = 0

         +-----+-----+-----+-----+
binary = |  1  |  0  |  1  |  1  |
         +-----+-----+-----+-----+

Since n becomes 0, so terminate the loop
Now reverse the binary array/vector and return it

                 +-----+-----+-----+-----+
binary_reverse = |  1  |  1  |  0  |  1  |
                 +-----+-----+-----+-----+

return binary_reverse which consists the binary
representation of the provided decimal number.

Code:

#include <iostream>
#include <vector>
using namespace std;

// Function to convert decimal to binary
void decimalToBinary(int decimal) {
    vector<int> binary; // Vector to store binary digits

    // Continue dividing the number by 2 and store remainders
    while (decimal > 0) {
        binary.push_back(decimal % 2); // Store the remainder (0 or 1)
        decimal /= 2; // Update the decimal number by dividing it by 2
    }

    // Binary number is stored in reverse order, print it from last to first
    cout << "Binary representation: ";
    for (int i = binary.size() - 1; i >= 0; i--) {
        cout << binary[i];
    }
    cout << endl;
}

int main() {
    int decimal;

    // Input decimal number from the user
    cout << "Enter a decimal number: ";
    cin >> decimal;

    // Handle the case where the input number is 0
    if (decimal == 0) {
        cout << "Binary representation: 0" << endl;
    } else {
        decimalToBinary(decimal); // Call the function to convert to binary
    }

    return 0;
}

Enter a decimal number: 13
Binary representation: 1101

Complexity Analysis:

• Time Complexity:O(logN) Since the number is divided by 2 continuously.
• Space Complexity:O(logN) Storing the bits.

Binary to Decimal Conversion

Each position in a binary number represents a power of 2 (just as each position in a decimal number represents a power of 10).

How Binary to Decimal Conversion Works

To convert a binary number to its decimal equivalent:

1. Identify the position of each bit (starting from 0 for the least significant bit on the right).
2. Multiply each bit (either 0 or 1) by 2^n, where n is the position of the bit.
3. Sum the results of all positions.

Converting a binary number back to its decimal equivalent involves a reverse process.

Example:

1. Converting 1101 to its decimal equivalent.
2. Start from the rightmost bit (least significant bit) and move to the left.
3. Each bit is multiplied by 2 raised to the power of its position index (starting from 0).

 1 * 2^0 = 1
 0 * 2^1 = 0
 1 * 2^2 = 4
 1 * 2^3 = 8

Summing these values will give the number, i.e., 1 + 0 + 4 + 8 = 13.
Hence, the decimal equivalent of the binary number 1101 is 13.

Code:

#include <iostream>
#include <string>
using namespace std;

// Function to convert binary string to decimal number
int binaryToDecimal(string str) {
    int len = str.length();  // Get the length of the binary string
    int val = 1;             // Start with the least significant bit value (2^0)
    int num = 0;             // Store the decimal result

    // Iterate through the binary string from right to left
    for (int i = len - 1; i >= 0; i--) {
        if (str[i] == '1') {
            num += val;      // Add the value to the result if the bit is '1'
        }
        val *= 2;            // Double the value for the next bit position (2^1, 2^2, etc.)
    }

    return num;  // Return the decimal equivalent
}

int main() {
    string binaryStr;

    // Input binary string from the user
    cout << "Enter a binary string: ";
    cin >> binaryStr;

    // Call the function and print the decimal equivalent
    cout << "Decimal representation: " << binaryToDecimal(binaryStr) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(n) Traversing every bit in the string.
• Space Complexity:O(1) Couple of variables used.

Representation of Negative Numbers

In computing, negative numbers are often represented using one's complement or two's complement notation.

🅰 One's Complement

Definition:

• One's complement of a binary number is obtained by flipping all the bits of the number, meaning converting every 1 to 0 and every 0 to 1.
• It is a simple method to represent negative numbers in binary.

How It Works:

• For a positive number, the binary representation remains the same.
• To find the one's complement of a number:
  1. Write its binary representation.
  2. Flip every bit (1 becomes 0, 0 becomes 1).

Example:

Suppose we have the 4-bit binary number 5 (decimal) = 0101 (binary) :

• One's complement of 5: Flip each bit: 0101->1010So, the one's complement of 5 is 1010​ , which represents -5 in one's complement notation.

Range of Numbers in One's Complement:

For n-bit systems, the range of numbers that can be represented is:

• Positive numbers: From 0 to (2^(n-1) - 1).
• Negative numbers: From -0 (represented as all 1's) to - (2^(n-1) - 1).

For example, in a 4-bit system:

• Positive numbers: (0 to 0111) binary, (0 to 7) in decimal.
• Negative numbers: (1000 to 1111) binary, (-0 to -7) in decimal. 

Key Drawbacks:

• Issue with Zero: One's complement has two representations for zero: positive zero (0000)​ and negative zero (1111)​ , which can complicate calculations.

🅱 Two's Complement

Definition:

• Two's complement is the most widely used method to represent signed numbers in modern computers. It is obtained by:
  1. Taking the one's complement of a number.
  2. Adding 1 to the result.

How It Works:

• For positive numbers, the binary representation remains unchanged.
• To represent a negative number, take the two’s complement of its absolute value:
  1. Find the one's complement of the number.
  2. Add 1 to the one's complement result.

Example:

Suppose we want to represent -5 (decimal) using two's complement in a 4-bit system:

1. Find the binary representation of 5 (decimal)​ : 0101​ (binary).
2. Take the one's complement of 0101​ : 1010​ .
3. Add 1 to the result: 1010+1 =​ 1011So, the two's complement of 5is 1011​ , representing -5 in binary.

Range of Numbers in Two's Complement:

For nnn -bit systems, the range of representable numbers is:

• Positive numbers: From 0 to (2^(n-1) - 1).
• Negative numbers: From -(2^(n-1)) to -1.

In a 4-bit system:

• Positive numbers: 0000(binary) to 0111(binary), 0 to 7 (in decimal).
• Negative numbers: 1000(binary) to 1111(binary), -8 to -1 (in decimal).

Key Advantages:

• Single Zero: In two's complement, there is only one representation for zero, solving the issue in one's complement.
• Efficient Arithmetic: Two's complement arithmetic simplifies addition and subtraction of signed numbers. The same circuitry can be used for both positive and negative numbers, unlike in one's complement.

Comparison of One's Complement and Two's Complement

What is Bit Manipulation?

At its core, bit manipulation involves performing operations directly on bits (0s and 1s) rather than on higher-level data structures like arrays or numbers. Since computers store data in binary form, manipulating bits gives you a more efficient way to perform operations that would otherwise be costly using conventional methods.

Why Use Bit Manipulation?

1. Efficiency: Bit-level operations are extremely fast because they are supported directly by the hardware.
2. Memory Optimization: You can store and manipulate large sets of boolean flags in a compact format, often using just a single integer.
3. Algorithm Simplification: Some problems, like finding subsets or combinations, can be solved more easily using bit manipulation.

Common Bitwise Operators in C/C++

Here’s a list of common bitwise operators and their uses:

Bitwise Operators

1️⃣ AND Operator

The AND operator is denoted by & (ampersand). It operates on two binary numbers, comparing each corresponding bit from both operands. If both bits are 1, the result is 1; otherwise, the result is 0.

Syntax:

result = a & b;

How It Works:

The AND operator performs a bitwise comparison between two numbers. The comparison is done bit by bit, and the result is based on the following rule:

Example:

a = 6
b = 3

a (6 in decimal) = 0110 in binary
b (3 in decimal) = 0011 in binary

  0110
& 0011
-------
  0010 = (2 in decimal)
-------

Use Cases of the AND Operator:

1. Checking if a Bit is set (On or Off):

   The AND operator is commonly used to check if a specific bit in a number is 1 or 0. This is done by ANDing the number with a mask where the bit of interest is set to 1.

   // Check if the 3rd bit (counting from 0) is set
   int num = 5;  // 0101 in binary
   int mask = 1 << 2; // 0001 shifted left by 2 positions: 0100
   if (num & mask) {
       cout << "Bit is set" << endl;
   } else {
       cout << "Bit is not set" << endl;
   }

2. Clearing (Turning Off) a Bit:

   You can clear a specific bit (turn it off) by ANDing the number with a mask that has 0 in the bit position you want to clear and 1 elsewhere.

   // Clear the 2nd bit of num
   int num = 7;  // 0111 in binary
   int mask = ~(1 << 2);  // 1111 1011 (2nd bit cleared)
   num = num & mask;  // 0111 & 1011 = 0011
   cout << num << endl;  // Output: 3 (in binary: 0011)
   

3. Masking:

   Sometimes, you may need to extract only a few bits from a number. The AND operator can be used to mask (isolate) specific bits by using a mask where only the required bits are sit to 1.

   // Isolate the last 3 bits of a number
   int num = 29;  // 11101 in binary
   int mask = 7;  // 00000111 in binary (which isolates the last 3 bits)
   int result = num & mask;  // 11101 & 00111 = 00101
   cout << result << endl;  // Output: 5
   

 2️⃣ OR Operator

The OR operator is denoted by (|). It compares each bit of two operands, and if at least one of the bits is 1, the result is 1. Otherwise, the result is 0.

Syntax:

result = a | b;

How It Works:

The OR operator performs a bitwise comparison between two numbers, producing a result based on the following rule:

Example:

a = 6
b = 3

a (6 in decimal) = 0110 in binary
b (3 in decimal) = 0011 in binary

  0110
| 0011
-------
  0111 = (7 in decimal)
-------

Use Cases of the OR Operator:

1. Setting (Turning On) a Bit:

   The OR operator is commonly used to set a specific bit in a number to 1. You can OR the number with a mask where only the bit of interest is set to 1, and the rest are 0.

   // Set the 2nd bit of num
   int num = 5;  // 0101 in binary
   int mask = 1 << 2;  // 0100 in binary
   num = num | mask;  // 0101 | 0100 = 0111
   cout << num << endl;  // Output: 7 (in binary: 0111)
   

2. Combining Flags or Values:

   When dealing with flags (or options), the OR operator is often used to combine multiple flags. This is common in scenarios like file handling permissions or hardware settings.

   // Combine two flags
   int readPermission = 1 << 0;  // 0001
   int writePermission = 1 << 1;  // 0010
   int combinedPermission = readPermission | writePermission;  // 0001 | 0010 = 0011
   cout << combinedPermission << endl;  // Output: 3 (Read and Write permissions)
   

   This OR operation combines both read and write permissions into a single value.

3. Masking to Set Specific Bits:

   You can use the OR operator to force certain bits to 1 while leaving the rest unchanged.

   // Set the last 3 bits to 1
   int num = 12;  // 1100 in binary
   int mask = 7;  // 00000111 in binary (this sets the last 3 bits)
   num = num | mask;  // 1100 | 0111 = 1111
   cout << num << endl;  // Output: 15 (in binary: 1111)
   

3️⃣ XOR Operator

The XOR operator is denoted by (^). It performs an exclusive OR comparison between two binary numbers. For each bit position, the result is 1 if exactly one of the bits is 1, and 0 otherwise. This means the result is 1 if the bits differ and 0 if they are the same.

Syntax:

result = a ^ b;

How It Works:

The XOR operator performs a bitwise comparison, with the result defined by the following rules:

Example:

a = 6
b = 3

a (6 in decimal) = 0110 in binary
b (3 in decimal) = 0011 in binary

  0110
^ 0011
-------
  0101 = (5 in decimal)
-------

Use Cases of the XOR Operator:

1. Toggling Bits:

   The XOR operator is useful for toggling specific bits in a number. If a bit is 1, XORing it with 1 will set it to 0, and if it is 0, XORing it with 1 will set it to 1.

   // Toggle the 2nd bit of num
   int num = 5;  // 0101 in binary
   int mask = 1 << 2;  // 0100 in binary
   num = num ^ mask;  // 0101 ^ 0100 = 0001
   cout << num << endl;  // Output: 1 (in binary: 0001)
   

   Here, the XOR operation toggles the 2nd bit of 5 (0101), resulting in 1 (0001).

2. Swapping Two Numbers Without a Temporary Variable:

   The XOR operator can be used to swap two variables without needing an extra variable.

   int a = 5;  // 0101
   int b = 7;  // 0111
   
   a = a ^ b;  // 0101 ^ 0111 = 0010
   b = a ^ b;  // 0010 ^ 0111 = 0101 (original value of a)
   a = a ^ b;  // 0010 ^ 0101 = 0111 (original value of b)
   
   cout << "a = " << a << endl;  // Output: 7
   cout << "b = " << b << endl;  // Output: 5
   

3. Checking for Equality:

   The XOR operator can be used to check if two values are equal. If two numbers are the same, their XOR will be zero.

   int a = 5;
   int b = 5;
   
   if ((a ^ b) == 0) {
       cout << "Numbers are equal" << endl;
   } else {
       cout << "Numbers are not equal" << endl;
   }
   

   In this case, 5 ^ 5 results in 0, indicating that the numbers are equal.

4️⃣ NOT Operator

The NOT operator is denoted by (~) tilde. This operator is also called the bitwise complement. It is a unary operator that flips all the bits in a binary number. It transforms each bit: if the bit is 1, it becomes 0, and if the bit is 0, it becomes 1. This operation is known as the one's complement of a number.

Syntax:

result = ~a;

How It Works:

The NOT operator simply inverts every bit in a binary number. For an n-bit system, applying the NOT operator to a number flips all n bits. This can result in a negative number when the system uses two's complement representation for negative values (which most modern systems do).

Example:

a = 6
b = 3

a (6 in decimal) = 0110 in binary
b (3 in decimal) = 0011 in binary

~(a)  ~0110
     -------
       1001 = (9 in decimal)
     -------
     
~(b)  ~0011
     -------
       1100  = (12 in decimal)
     -------

Use Cases of the NOT Operator:

1. Flipping:

   All Bits in a Number: The primary use of the NOT operator is to flip every bit in a number. This is useful when you want to invert all the bits in a binary sequence, which can be part of masking or cryptographic algorithms.

   int num = 5;  // 0000 0101 in binary
   int result = ~num;  // 1111 1010 in binary (which equals -6 in two's complement)
   cout << result << endl;  // Output: -6
   

2. Finding the One's Complement:

   The NOT operator is often used to compute the one's complement of a number, which means flipping all its bits. In the context of binary arithmetic, one's complement was used in older systems for negative number representation.

   int num = 10;  // Binary: 0000 1010
   int onesComplement = ~num;  // Binary: 1111 0101 (-11 in two's complement)
   cout << onesComplement << endl;  // Output: -11
   

3. Quick Bitwise Operations with Masks:

   Sometimes, when working with bitmasks, the NOT operator is used to invert a mask. For example, if you want to turn off a specific bit in a number, you can use a combination of the AND and NOT operators.

   // Clear (set to 0) the 3rd bit of num
   int num = 15;  // Binary: 1111
   int mask = 1 << 3;  // Binary: 1000 (to target the 3rd bit)
   num = num & ~mask;  // 1111 & 0111 = 0111 (7 in decimal)
   cout << num << endl;  // Output: 7
   

5️⃣ Shift Operators

Shift operators are used to move the bits of a binary number either to the left or right by a specified number of positions.

There are two types of shift operators:

1. Left Shift (<<)
2. Right Shift (>>)

1. Left Shift Operator (<<)

C/C++ supports only one type of left shift operation, which is logical by nature. The bits are shifted to the left, and the vacant rightmost bits are filled with zeros, regardless of whether the number is signed or unsigned. In terms of functionality, the left shift is the same for both signed and unsigned types.

• Signed integers: The sign bit might be affected, leading to undefined behavior if the shift causes overflow.
• Unsigned integers: The operation is safe, and the value behaves as expected.

The left shift operator shifts the bits of a number to the left by a specified number of positions, filling the vacant rightmost bits with zeros (0). This is equivalent to multiplying the number by2^n, where nis the number of shifts.

Syntax:

result = a << n;

• a: The number whose bits are being shifted.
• n: The number of positions to shift left.

Example:

a = 5, n = 3

a (5 in decimal) = 0000 0101 (in binary)
a << n
Shifting a to the left by 3
0010 1000 (40 in decimal)

Effect of Left Shift:

• Left shift by 1 position is equivalent to multiplying the number by 2.
• Left shift by n positions is equivalent to multiplying the number by 2^n.

Example with Multiplication:

int num = 7;
int result = num << 1;  // Left shift by 1 is the same as multiplying by 2
cout << result << endl;  // Output: 14

2. Right Shift Operator (>>)

The right shift operator shifts the bits of a number to the right by a specified number of positions. The right shift in C/C++ behaves differently based on whether the number is signed or unsigned.

It comes in two variations:

• Arithmetic Right Shift (used in signed integers)
• Logical Right Shift (used in unsigned integers)

Arithmetic Right Shift (for signed integers):

In signed integers, the right shift operator fills the leftmost bits with the sign bit (0 for positive numbers, 1 for negative numbers). This is equivalent to dividing the number by 2^nand rounding toward negative infinity.

The sign bit is retained (preserved), meaning the leftmost bit remains the same (either 0 or 1), depending on whether the number is positive or negative.

• If the number is positive, the leftmost bits are filled with zeros.
• If the number is negative, the leftmost bits are filled with ones (to preserve the sign).

Syntax:

result = a >> n;

Example:

a = 20, n = 3

a (20 in decimal) = 0001 0100 (in binary)
a >> n
Shifting a to the right by 3
0000 0010 (2 in decimal)

Effect of Right Shift:

• Right shift by 1 position is equivalent to dividing the number by 2 and discarding the remainder (floor division).
• Right shift by n positions is equivalent to dividing the number by 2^n.

Example with division:

int num = 20;
int result = num >> 1;  // Right shift by 1 is the same as dividing by 2
cout << result << endl;  // Output: 10

Example for negative numbers:

int num = -8;  // Binary: 1111 1000 (in two's complement)
int result = num >> 1;  // Arithmetic shift
cout << result << endl;  // Output: -4

Here, the sign bit is preserved, and the result is a negative number.

Logical Right Shift (for unsigned integers):

For unsigned integers (unsigned int), the right shift (>>) is logical. This means that the leftmost bits are always filled with zeros, regardless of the original value of the number.

The right shift fills the leftmost bits with zeros, irrespective of the sign of the number.

Example for unsigned numbers:

unsigned int num = 8;  // Binary: 0000 1000
unsigned int result = num >> 1;  // Logical shift
cout << result << endl;  // Output: 4