Bit Manipulation - DSA: Introduction to Binary, 1's & 2's Complement, and Bitwise Operators

1. Why Do We Need Bit Manipulation?

When writing high-performance algorithms, standard arithmetic operations can sometimes become bottlenecks. Computers operate entirely at the microscopic hardware level using electrical switches representing binary states (0 and 1).

Bit manipulation allows programmers to directly manipulate these individual bits. This unlocks extreme execution speed, minimal memory footprints, and elegant solutions to complex combinatorial problems that would otherwise require heavy data structures.

2. Core Mental Model: How Computers Store Integers

When you declare an integer variable in code, such as:

int x = 13;

The computer never stores the decimal number 13 directly in its memory. Instead, it converts 13 into its binary equivalent (1101) and pads it to fill the hardware's fixed-width register size.

Memory Representation (32-bit Architecture)

An standard signed 32-bit integer (int) allocates exactly 32 bits in memory:

• Bit 31 (The Most Significant Bit / MSB): Reserved entirely as the Sign Bit (0 for positive, 1 for negative).
• Bits 0 to 30: Used to store the actual magnitude of the number.

For positive numbers, the remaining leading bits are simply filled with zeros. For instance, int x = 13 is stored as:

00000000 00000000 00000000 00001101

3. Base Conversions: Decimal to Binary and Back

A. Decimal to Binary Conversion

To convert a positive decimal number to binary, continuously divide the number by 2 and record the remainders until the quotient reaches 1. Then, read the remainders in reverse order (from bottom to top).

Example: Converting 13 to Binary

13 / 2 = 6  | Remainder: 1 (LSB)
 6 / 2 = 3  | Remainder: 0
 3 / 2 = 1  | Remainder: 1
Stop at 1   | Remainder: 1 (MSB)

Reading from bottom to top yields: 1101.

Code Implementation (Decimal to Binary)

def decimal_to_binary(n: int) -> str:
    if n == 0:
        return "0"
    
    result = []
    while n > 1:
        remainder = n % 2
        result.append(str(remainder))
        n //= 2
    
    # When n reaches 1, append the final 1
    result.append("1")
    
    # Reverse because remainders were collected bottom-up
    return "".join(result[::-1])

B. Binary to Decimal Conversion

To convert a binary string back to decimal, start from the rightmost bit (index 0) and move left, multiplying each bit by increasing powers of 2 (2^0, 2^1, 2^2, ...).

Example: Converting 1101 to Decimal

Binary:  1   1   0   1
Index:   3   2   1   0

Calculation:
(1 * 2^3) + (1 * 2^2) + (0 * 2^1) + (1 * 2^0)
= 8       + 4       + 0       + 1       = 13

Code Implementation (Binary to Decimal)

def binary_to_decimal(binary_str: str) -> int:
    length = len(binary_str)
    num = 0
    power_of_two = 1  # 2^0 initially
    
    # Traverse from right to left
    for i in range(length - 1, -1, -1):
        if binary_str[i] == '1':
            num += power_of_two
        power_of_two *= 2  # Increment power of 2 efficiently
        
    return num

4. Complexity Analysis of Conversion Functions

5. 1's Complement and 2's Complement

1's Complement

The 1's complement of a binary number is formed by simply inverting every bit (turning all 0s to 1s and all 1s to 0s).

• Example: If binary is 1101, its 1's complement is 0010.

2's Complement

Computers use 2's complement arithmetic to represent and store negative numbers. This eliminates the ambiguity of having both a positive and negative zero and simplifies hardware addition/subtraction circuitry.

Steps to find the 2's Complement:

1. Step 1: Find the 1's complement of the number (flip all bits).
2. Step 2: Add 1 to the resulting 1's complement.

Example: Finding 2's complement of 13

6. Integer Ranges: INT_MAX and INT_MIN

Maximum Integer (INT_MAX)

In a 32-bit signed integer, the highest bit is reserved for the sign (0 for positive). To get the largest possible positive number, we set the sign bit to 0 and fill all remaining 31 bits with 1s:

Binary representation: 01111111 11111111 11111111 11111111.

Minimum Integer (INT_MIN)

The smallest negative number utilizes the 2's complement representation where the sign bit is 1 and all magnitude bits are 0:

Binary representation: 10000000 00000000 00000000 00000000.

7. Fundamental Bitwise Operators

A. Bitwise AND (&)

• Rule: Returns 1 only if all corresponding bits are 1. If there is even a single 0, the result is 0.
• Example: 13 & 7
  Structure & Concept Flow

  Copy DiagramCopy

  13 -> 1 1 0 1

  7 -> 0 1 1 1

  --------------

  & -> 0 1 0 1 (Decimal: 5)

   

B. Bitwise OR (|)

• Rule: Returns 1 if at least one corresponding bit is 1. Returns 0 only if all bits are 0.
• Example: 13 | 7
  Structure & Concept Flow

  Copy DiagramCopy

  13 -> 1 1 0 1

  7 -> 0 1 1 1

  --------------

  | -> 1 1 1 1 (Decimal: 15)

   

C. Bitwise XOR (^)

• Rule: Returns 1 if the number of set bits (1s) in that column is odd. Returns 0 if the count is even.
• Example: 13 ^ 7
  Structure & Concept Flow

  Copy DiagramCopy

  13 -> 1 1 0 1

  7 -> 0 1 1 1

  --------------

  ^ -> 1 0 1 0 (Decimal: 10)

   

8. Shift Operators

A. Right Shift Operator (>>)

Shifts all bits to the right by k positions. Bits that fall off the right edge are discarded, and the left side is padded with zeros (for positive numbers).

• Formula:

• Example: 13 >> 1
  Structure & Concept Flow

  Copy DiagramCopy

  13 (Binary) -> 1 1 0 1

  Right Shift 1 -> 1 1 0 (Trailing 1 falls off cliff)

  Decimal value -> 6

   
  Verification: $13 / 2^1 = 6$.

B. Left Shift Operator (<<)

Shifts all bits to the left by k positions. The left-most bits fall off, and the right side is padded with zeros.

• Formula:

• Example: 13 << 1
  Structure & Concept Flow

  Copy DiagramCopy

  13 (Binary) -> 1 1 0 1

  Left Shift 1 -> 1 1 0 1 0 (Padded with 0 on right)

  Decimal value -> 26

   
  Verification: $13 \times 2^1 = 26$.

Warning (Overflow): Left shifting beyond the 31st bit boundary in a 32-bit integer causes an overflow, resulting in undefined or unexpected negative values. Always ensure values remain within [INT_MIN, INT_MAX].

9. The Bitwise NOT Operator (~)

The NOT operator (tilde ~) inverts all bits of a number (similar to 1's complement).

How ~ Operates on Positive Numbers:

1. Step 1: Invert all bits of the number (including the sign bit).
2. Step 2: Because the sign bit flips to 1, the computer recognizes the result as a negative number and stores it in its 2's complement form.

Example: ~5

10. Summary and Key Takeaways

• Internal Representation: Computers store all integers in binary (base 2) using fixed-width registers (32-bit for int), where the MSB acts as the sign bit.
• Base Conversions: Decimal to binary conversion relies on successive division by 2 and collecting remainders in reverse order ($\mathcal{O}(\log n)$ time).
• Complement System: Negative numbers are stored using 2's complement (1's complement + 1) to unify arithmetic operations.
• Range Boundaries: Signed 32-bit integers safely store values ranging from $\text{INT\_MIN} = -2^{31}$ to $\text{INT\_MAX} = 2^{31} - 1$.
• AND Operator (&): Yields 1 only when both bits are 1. Frequently used for bitmasking and checking if a bit is set.
• OR Operator (|): Yields 1 if at least one bit is 1. Used to set specific bits.
• XOR Operator (^): Yields 1 when the count of 1s is odd. Properties include $x \mathbin{\hat{}} x = 0$ and $x \mathbin{\hat{}} 0 = x$.
• Right Shift (>>): Efficiently divides a number by $2^k$ ($\text{Num} / 2^k$).
• Left Shift (<<): Efficiently multiplies a number by $2^k$ ($\text{Num} \times 2^k$), with a risk of integer overflow if it exceeds bit limits.
• NOT Operator (~): Flips all bits, effectively computing $-(x + 1)$ due to 2's complement representation.