---

[!info] related notes 算法面试题型 MOC 异或与位运算技巧

Bitmap / Bitset

Idea

• Use 1 bit per value to represent existence (1 = present, 0 = absent).
• Very space-efficient.
• Main constraint: values must be within a continuous, not-too-large integer range.

Memory

• Range size = N values
• Space ~ N bits = N / 8 bytes

Operations

• add: set bit to 1
• remove: set bit to 0
• toggle: flip bit
• contains: test bit

Java Implementation

public class Bitset {
    private final int[] set;

    public Bitset(int n) {
        // represent [0..n]
        set = new int[(n + 31) / 32];
    }

    public void add(int num) {
        set[num / 32] |= 1 << (num % 32);
    }

    public void remove(int num) {
        set[num / 32] &= ~(1 << (num % 32));
    }

    public void toggle(int num) {
        set[num / 32] ^= 1 << (num % 32);
    }

    public boolean contains(int num) {
        return ((set[num / 32] >>> (num % 32)) & 1) == 1;
    }
}

Related

• 异或与位运算技巧