🌱 Keegan's Digital Garden

05. Bit Manipulation

2 min read

Bit Manipulation

General Use

  • Bit manipulation is used in a variety of problems:
    • Sometimes explicitly required by the question.
    • Other times it’s a useful technique for optimizing solutions.

Bit Facts and Tricks

  • Useful expressions in bit manipulation:

    • x ^ 0s = x (XOR with 0s leaves bits unchanged)
    • x ^ 1s = ~x (XOR with 1s flips bits)
    • x ^ x = 0 (XOR of identical bits cancels out)
    • x & 0s = 0 (AND with 0s clears bits)
    • x & 1s = x (AND with 1s leaves bits unchanged)
    • x & x = x (AND of identical bits remains the same)
    • x | 0s = x (OR with 0s leaves bits unchanged)
    • x | 1s = 1s (OR with 1s sets bits to 1)
    • x | x = x (OR of identical bits remains the same)

  • Bit-by-Bit Operations:

    • Operations occur on each bit independently.
    • If a rule applies to a single bit, it applies to all bits in the sequence.

Two’s Complement and Negative Numbers

  • Two’s complement is the standard representation for signed integers.
    • Positive numbers and 0 are represented as usual.
    • Negative numbers are represented by flipping all bits of the positive equivalent and adding 1.
  • Bit manipulation tasks often rely on this representation for signed integers.

Arithmetic vs. Logical Right Shifts

  • Arithmetic Right Shift (>> in most languages):

    • Preserves the sign bit for signed numbers.
    • Useful for dividing signed numbers by powers of 2.

  • Logical Right Shift (>>> in most languages):

    • Shifts bits to the right and fills with 0s.
    • Does not preserve the sign bit, so it’s used for unsigned numbers.

Common Bit Tasks

  1. Get a Bit:

    • Check if the ith bit is set:
      • (x >> i) & 1

  2. Set a Bit:

    • Set the ith bit to 1:
      • x | (1 << i)

  3. Clear a Bit:

    • Clear the ith bit (set it to 0):
      • x & ~(1 << i)

  4. Update a Bit:

    • Set the ith bit to a specific value (v is 0 or 1):
      • x = (x & ~(1 << i)) | (v << i)

Key Tips

  • Understand why each bit trick works instead of memorizing them.
  • Practice visualizing binary numbers and common bit operations.
  • Bit manipulation is particularly powerful in problems involving:
    • Flags.
    • Subset generation.
    • Optimizing space or runtime for algorithms.

Graph View