Bit Vector

A bit vector is an array of bits or Booleans used to represent a set of items compactly by mapping each item to a single bit. Bit operations allow fast lookups, unions, and intersections on sets.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BitVector {
  byte[] bits;

  public boolean get(int i) {
    int byteIndex = i / 8;
    int bitIndex = i % 8;
    byte b = bits[byteIndex];
    return ((b >> bitIndex) & 1) == 1;
  }
  
  public void set(int i) {
    int byteIndex = i / 8;
    int bitIndex = i % 8;
    byte b = bits[byteIndex];
    bits[byteIndex] = (byte)(b | (1 << bitIndex));
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BitVector {
  vector<bool> bits; 

public:
  bool get(int i) {
    return bits[i]; 
  }

  void set(int i) {
    bits[i] = 1;
  }
};

// Usage:
BitVector bv(100);
bv.set(5);
bool b = bv.get(5); // true

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from bitarray import bitarray

class BitVector:

  def __init__(self, size):
    self.bits = bitarray(size)

  def get(self, i):
    return self.bits[i]  
  
  def set(self, i):
    self.bits[i] = True

bv = BitVector(100)
bv.set(5)
print(bv.get(5)) # True

Bit vectors provide a space-efficient representation for sets and enable fast bitwise operations. Useful for problems involving large binary sets.

Bit vector is an efficient data structure that can be used to solve many problems on LeetCode. It is a space-efficient way to store a set of integers. A bit vector can be used to represent a set of integers by using one bit to represent each integer. The bit corresponding to an integer is set to 1 if the integer is in the set, and 0 otherwise.

Bit vector can be used to solve many problems on LeetCode, such as:

Count the number of elements in a set.
Check if an integer is in a set.
Add an integer to a set.
Remove an integer from a set.
Union of two sets.
Intersection of two sets.
Difference of two sets.
Complement of a set.

Bit vector is a powerful data structure that can be used to solve many problems on LeetCode.

Bit Vector

A Bit Vector, also known as a Bit Array or BitSet, is an array data structure that compactly stores bits. It can be used to represent a set of integers between 0 and n-1, where n is the size of the Bit Vector. Each bit in the array represents whether a particular integer is present in the set. The key takeaway is that Bit Vectors are space-efficient for sets that contain small numbers and provide fast operations like add, delete, and lookup.

Java Code

Java’s standard library offers a BitSet class, but for educational purposes, let’s create a simple Bit Vector using an array of integers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class BitVector {
    private int[] data;
    private int size;

    public BitVector(int size) {
        this.size = size;
        this.data = new int[(size + 31) / 32];
    }

    public void set(int index) {
        int arrayIndex = index / 32;
        int bitIndex = index % 32;
        data[arrayIndex] |= (1 << bitIndex);
    }

    public boolean get(int index) {
        int arrayIndex = index / 32;
        int bitIndex = index % 32;
        return (data[arrayIndex] & (1 << bitIndex)) != 0;
    }
}

set(int index) sets the bit at the given index to 1.
get(int index) checks if the bit at the given index is 1 or 0.

C++ Code

In C++, we can implement a Bit Vector using an array of unsigned integers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
using namespace std;

class BitVector {
private:
    vector<unsigned int> data;
    int size;

public:
    BitVector(int size): size(size), data((size + 31) / 32, 0) {}

    void set(int index) {
        int arrayIndex = index / 32;
        int bitIndex = index % 32;
        data[arrayIndex] |= (1 << bitIndex);
    }

    bool get(int index) {
        int arrayIndex = index / 32;
        int bitIndex = index % 32;
        return (data[arrayIndex] & (1 << bitIndex)) != 0;
    }
};

set(int index) sets the corresponding bit to 1.
get(int index) retrieves the value of the bit at the given index.

Python Code

Python can handle this with a simple list of integers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class BitVector:
    def __init__(self, size):
        self.size = size
        self.data = [0] * ((size + 31) // 32)

    def set(self, index):
        array_index = index // 32
        bit_index = index % 32
        self.data[array_index] |= (1 << bit_index)

    def get(self, index):
        array_index = index // 32
        bit_index = index % 32
        return (self.data[array_index] & (1 << bit_index)) != 0

set(self, index) turns on the bit at the given index.
get(self, index) checks if the bit at the given index is on or off.

In all these implementations, set and get are the core methods, allowing you to manipulate individual bits in a space-efficient manner.