Skip to content

Sde104 bitmask

What is a Bitmask?

A bitmask is a sequence of bits (0s and 1s) used to manipulate and query individual bits within a binary number. It’s a powerful tool often used in programming for various tasks such as managing sets, flags, or bitwise operations. Here’s a closer look at what bitmasks are and how they are used:

Understanding Bitmasks

Bit Representation

  • A bitmask consists of a series of bits, where each bit can be either 0 or 1. For example, 101010 is a bitmask with six bits.

Bitwise Operations

  • AND (&): Used to check if certain bits are set. For example, 0101 & 0011 results in 0001, showing where both bitmasks have bits set.
  • OR (|): Used to set specific bits. For example, 0101 | 0011 results in 0111, setting bits where at least one of the bitmasks has bits set.
  • XOR (^): Used to toggle bits. For example, 0101 ^ 0011 results in 0110, toggling bits where the two bitmasks differ.
  • NOT (~): Used to flip all bits. For example, ~0101 results in the bitmask where all bits are flipped.

Applications of Bitmasks

  • Set Representation Bitmasks are commonly used to represent sets of items. Each bit in the mask represents whether a particular item is present (1) or absent (0).
  • Flags and States: Bitmasks are used to manage multiple flags or states within a single variable. For example, you might use a bitmask to track various settings in a system where each bit represents a different setting.
  • Efficient Computation: Operations with bitmasks are generally very fast, as they directly manipulate bits in a binary number. This efficiency is useful in performance-critical applications.

GET/SET/PUT Examples with Bitmasks

GET: Checking if a specific bit is set 

1
2
3
4
5
6
7
# Define a bitmask
bitmask = 0b1010  # Binary representation of 1010

# Check if the 2nd bit (0-based index) is set
bit_position = 1
is_set = (bitmask & (1 << bit_position)) != 0
print(f"Bit at position {bit_position} is set: {is_set}")  # Output: True

SET: Setting a specific bit 

1
2
3
4
5
6
7
# Define a bitmask
bitmask = 0b1010  # Binary representation of 1010

# Set the 1st bit
bit_position = 1
bitmask |= (1 << bit_position)
print(f"Bitmask after setting bit at position {bit_position}: {bin(bitmask)}")  # Output: 0b1011

PUT: Toggling a specific bit 

1
2
3
4
5
6
7
# Define a bitmask
bitmask = 0b1010  # Binary representation of 1010

# Toggle the 3rd bit
bit_position = 3
bitmask ^= (1 << bit_position)
print(f"Bitmask after toggling bit at position {bit_position}: {bin(bitmask)}")  # Output: 0b1110

Limitations and When to Use Bitmasks in Leetcode

Limitations

  • Bitmask Size: Bitmasks are limited by the size of the integer type used. For example, a 32-bit integer can represent up to 32 bits, which may not be sufficient for problems requiring more bits.
  • Complexity of Operations: While bitwise operations are fast, managing and understanding bitmasks can become complex, especially when dealing with multiple bits and their interactions.

When to Use

  • Subset Problems: Bitmasks are ideal for problems involving subsets, where each bit can represent the inclusion or exclusion of an element in the subset.
  • Combinatorial Optimization: Use bitmasks to efficiently explore combinations of items or states, particularly when the number of items is small enough to fit within the bitmask constraints.
  • Flags and States: Use bitmasks to manage multiple flags or states efficiently, especially when you need to keep track of many boolean attributes within a single integer.

In summary, bitmasks are a versatile and efficient tool for manipulating and querying binary data. They are particularly useful in competitive programming and Leetcode problems involving subsets, combinations, or state management, provided the constraints are manageable within the size limits of bitmasks.