Bit Manipulation Lecture Notes

Introduction

• Topic: Bit Manipulation
• Covered: Binary number conversion, one's complement, two's complement, bitwise operators (AND, OR, XOR, NOT, shift operations)

Binary Number Conversion

Decimal to Binary

• Example: 7 (base 10) to binary
  • 7 ÷ 2 = 3, remainder = 1
  • 3 ÷ 2 = 1, remainder = 1
  • 1 ÷ 2 = 0, remainder = 1
  • Read remainders bottom to top: 111
  • Binary representation: 7 (base 10) = 111 (base 2)
• Example: 13 (base 10) to binary
  • 13 ÷ 2 = 6, remainder = 1
  • 6 ÷ 2 = 3, remainder = 0
  • 3 ÷ 2 = 1, remainder = 1
  • 1 ÷ 2 = 0, remainder = 1
  • Read remainders bottom to top: 1101
  • Binary representation: 13 (base 10) = 1101 (base 2)

Binary to Decimal

• Example: 1101 (base 2) to decimal
  • 1 × 2³ = 8
  • 1 × 2² = 4
  • 0 × 2¹ = 0
  • 1 × 2⁰ = 1
  • Sum: 8 + 4 + 0 + 1 = 13
  • Decimal representation: 1101 (base 2) = 13 (base 10)

Binary Conversion Functions in Code

Decimal to Binary Function

• Pseudocode overview:
  • Continue dividing number by 2, keep track of remainders
  • Store remainders in a string or list
  • Reverse and return the final result
  • Time complexity: O(log₂n)
  • Space complexity: O(log₂n)

Binary to Decimal Function

• Pseudocode overview:
  • Traverse binary string from right to left
  • Multiply each bit by powers of 2 and sum them up
  • Return the result
  • Time complexity: O(n)
  • Space complexity: O(1)

Computer Binary Storage

• Computers store numbers in binary using 32-bit (int) or 64-bit (long long)
• For int: first bit indicates sign (0 for positive, 1 for negative)
• Positive number example: 13 (base 10) stored as 0000...1101 (base 2)
• Negative number storage: Uses two's complement
  • Example: -3 in binary: Invert bits of 0000...0011, add 1
  • Result: 1111...1101

One's and Two's Complement

One's Complement

• Flip all bits
• Example: 13 (base 10) => 0000...1101 => 1111...0010 (one's complement)

Two's Complement

• Get one's complement, then add 1
• Example: One's complement 1111...0010 + 1 => 1111...0011 (two's complement)

Bitwise Operators

AND Operator (&)

• X & Y: Bit-by-bit comparison
• 1 & 1 = 1, else 0
• Example: 13 & 7
  • 1101 & 0111 = 0101 (In decimal, 5)

OR Operator (|)

• X | Y: Bit-by-bit comparison
• 0 | 0 = 0, else 1
• Example: 13 | 7
  • 1101 | 0111 = 1111 (In decimal, 15)

XOR Operator (^)

• X ^ Y: Bit-by-bit comparison
• Even number of 1's: 0; Odd number of 1's: 1
• Example: 13 ^ 7
  • 1101 ^ 0111 = 1010 (In decimal, 10)

Shift Operators

Right Shift (>>)

• X >> k: Shift bits right by k positions
• Example: 13 >> 1
  • 1101 >> 1 = 0110 (In decimal, 6)
• Effectively divide by 2^k

Left Shift (<<)

• X << k: Shift bits left by k positions
• Example: 13 << 1
  • 1101 << 1 = 11010 (In decimal, 26)
• Effectively multiply by 2^k

NOT Operator (~)

• Flip every bit
• Example: ~5
  • Binary of 5: 0000...0101 (32 bits)
  • Flip all bits => 1111...1010
  • Two's complement: 1111...1010 => -6

Largest and Smallest Stored Value

• Largest positive int: 2^31 - 1
• Smallest negative int: -2^31

Conclusion

• Next time: Diving into bitwise operators problems

Note: Practice the interchangeability between binary and decimal systems for strong fundamental understanding.