Bit Manipulation Crash Course

Introduction

Focus on concepts needed for problems ranging from easy to hard
Resources and notes available on CODwithin.com (not yet uploaded)

What is Bit Manipulation?

Algorithmically manipulating bits (0s and 1s)
Similar to how binary numbers are used in programming
Convert decimal to binary and vice versa
- Decimal: 10, 15, 20, etc.
- Binary: (e.g. 5 -> 101)

Converting Decimal to Binary

Convert normal decimal numbers (10, 15, etc.) to binary
Conversion example: Decimal 5 to Binary 101

Steps to convert decimal to binary programmatically

Divide by 2, take remainder
Write from right to left
Collect remainders to form binary representation
Example: 5 -> 5/2=2 remainder 1, 2/2=1 remainder 0, 1/2=0 remainder 1 (Binary: 101)

Python Pseudocode

binary_vector = []
index = 0
while n > 0:
    remainder = n % 2
    binary_vector.append(remainder)
    n = n // 2
    index += 1
binary_vector.reverse()  # Ensure correct order

Time Complexity

Every time dividing number by 2
O(log n) base 2

Space Complexity

O(log n) based on the size of binary_vector

Converting Binary to Decimal

Power of 2 for each bit position
Collect contribution from set bits
Example: 101 -> 12^2 + 02^1 + 12^0 = 5

Python Pseudocode

def binary_to_decimal(binary_vector):
    power_of_two = 1
    decimal_number = 0
    for bit in binary_vector:
        decimal_number += bit * power_of_two
        power_of_two *= 2
    return decimal_number

Binary Numbers in Programming

32-bit integer (-2^31 to 2^31 - 1)
64-bit integer (long long)
Negative numbers representation using one's complement and two's complement
- One's complement: Flip the bits
- Two's complement: Add 1 to the one's complement result

Adding & Subtracting Binary Numbers

Binary addition with carry over
Binary subtraction by borrowing

Bitwise Operators

AND (&) - Shrinks or keeps value same
- 1 & 1 = 1 (only when both have 1)
OR (|) - Increases or keeps value same
- 0 | 1 = 1
XOR (^) - Flips specific bits
- 1 ^ 1 = 0 (same bits zero out)
NOT (~) - Flips all bits
- ~010 => 101

Masking Bits

Highlight specific bit using masks
Mask: Boolean representation that only affects a specific bit
Used to specifically work on a single bit

Creating a Mask

Left Shift (<<)
- Shifting bits to left multiplies value by 2
- Example: 1 << 1 = 10 (binary for 2)
Right Shift (>>)
- Shifting bits to right divides value by 2
- Example: 2 >> 1 = 1

Setting, Unsetting, and Checking Bits

Setting: Use OR (|) operation with mask
Unsetting: Use AND (&) with NOT of mask
Checking: Use AND (&) with mask, check if result is greater than 0

Practical Use Case

Represent an array as a binary number to optimize memory usage (e.g., in graph or string problems)

Removing the Rightmost Set Bit

Two methods:
1. ID and -ID (Two's complement)
  - Get mask of the rightmost set bit
  - Subtract mask to remove it
2. N & (N - 1) Method
  - Directly removes the last set bit
  - Used in power of two checking

Conclusion

Mastery of bit manipulation includes knowledge of operators, binary conversions, masks, setting/unsetting/checking bits.
Apply concepts in practical problems to strengthen understanding.

Additional Resources:

Online portals for coding practice
Join relevant study groups and forums.