Overview

Binary operations are fundamental to computer science, involving the manipulation of numbers at the bit level. These operations are efficient and often used in algorithms for optimization and low-level computations.

Key Concepts

  1. Binary Representation

    • Numbers are represented using bits (0s and 1s).
    • Example: The number 5 is represented as 101 in binary.

  2. Bitwise Operators

    • Perform operations directly on the binary representation of numbers.

Common Bitwise Operators

Operator Symbol Description Example
AND & Sets each bit to 1 if both bits are 1 5 & 3 = 1
OR ` ` Sets each bit to 1 if one of the bits is 1
XOR ^ Sets each bit to 1 if only one of the bits is 1 5 ^ 3 = 6
NOT ~ Inverts all bits ~5 = -6
Left Shift << Shifts bits to the left, padding with 0s 5 << 1 = 10
Right Shift >> Shifts bits to the right 5 >> 1 = 2

Examples of Bitwise Operations

# Example: Bitwise AND
print(5 & 3)  # Output: 1

# Example: Bitwise OR
print(5 | 3)  # Output: 7

# Example: Bitwise XOR
print(5 ^ 3)  # Output: 6

# Example: Left Shift
print(5 << 1)  # Output: 10

# Example: Right Shift
print(5 >> 1)  # Output: 2

Applications of Binary Operations

1. Checking if a Number is Odd or Even

  • Use n & 1.
  • If the result is 1, the number is odd; otherwise, it is even.
# Example: Odd or Even
n = 5
if n & 1:
    print("Odd")
else:
    print("Even")

2. Counting Set Bits

  • Count the number of 1s in the binary representation of a number.
  • Use n & (n-1) to clear the least significant bit.
# Example: Count Set Bits
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

print(count_set_bits(5))  # Output: 2

3. Swapping Numbers Without a Temporary Variable

  • Use XOR to swap two numbers in place.
# Example: Swap Numbers
x, y = 5, 3
x = x ^ y
y = x ^ y
x = x ^ y
print(x, y)  # Output: 3, 5

4. Power of Two Check

  • A number is a power of two if it has exactly one bit set.
  • Condition: n > 0 and (n & (n-1)) == 0.
# Example: Power of Two Check
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(4))  # Output: True

5. Single Number in an Array

  • Given an array where every element appears twice except one, find the single element.
  • Use XOR: a ^ a = 0 and a ^ 0 = a.
# Example: Single Number
nums = [4, 1, 2, 1, 2]
result = 0
for num in nums:
    result ^= num
print(result)  # Output: 4

6. Bit Masking

  • Use a mask to selectively turn on, turn off, or toggle bits in a number.
# Example: Bit Masking
n = 5  # Binary: 101
mask = 1 << 1  # Binary: 010

# Turn on the 2nd bit
n |= mask  # Output: 7 (Binary: 111)

# Turn off the 2nd bit
n &= ~mask  # Output: 5 (Binary: 101)

# Toggle the 2nd bit
n ^= mask  # Output: 7 (Binary: 111)

Advanced Applications

1. Subset Generation

  • Use binary representation to generate all subsets of a set.
# Example: Subset Generation
def generate_subsets(nums):
    n = len(nums)
    subsets = []
    for i in range(1 << n):
        subset = []
        for j in range(n):
            if i & (1 << j):
                subset.append(nums[j])
        subsets.append(subset)
    return subsets

print(generate_subsets([1, 2, 3]))
# Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

2. Gray Code

  • Generate a sequence of binary numbers where two successive numbers differ in only one bit.
# Example: Gray Code
def gray_code(n):
    result = []
    for i in range(1 << n):
        result.append(i ^ (i >> 1))
    return result

print(gray_code(2))
# Output: [0, 1, 3, 2]

3. Bitwise Sieve for Prime Numbers

  • Use bitwise operations to implement an efficient sieve.
# Example: Sieve of Eratosthenes
LIMIT = 100
is_prime = (1 << LIMIT) - 1

for i in range(2, int(LIMIT ** 0.5) + 1):
    if (is_prime >> i) & 1:
        for j in range(i * i, LIMIT, i):
            is_prime &= ~(1 << j)

primes = [i for i in range(2, LIMIT) if (is_prime >> i) & 1]
print(primes)

Summary

Binary operations are powerful and versatile, offering efficient solutions to a variety of problems. Mastering bitwise manipulation helps in solving problems that involve optimization, subset generation, and low-level computations.