Problem

Implement a bit array.

A bit array is a space efficient array that holds a value of 1 or 0 at each index.

  • init(size): initialize the array with size
  • set(i, val): updates index at i with val where val is either 1 or 0.
  • get(i): gets the value at index i.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
Solution.init(10)
Solution.set(3, 1)
Solution.set(5, 1)
print(Solution.get(3))

Output: 
1

Explanation: The value at index 3 was set to 1, and the value at index 5 was also set to 1.

Solution

Method 1 - Using an array

  • A bit array can be implemented using an array of integers where each integer is used to store multiple bits.
  • For example, a 32-bit integer can store the state of 32 different indices in the bit array.
  • Bitwise operations (&, |, ~, <<, >>) can be used to set, clear, and get the value of specific bits.

Approach

  1. Initialization: Use an integer array (bits) to store the bit states. Calculate the required size of this array based on the given size.
  2. Set Operation:
    • Calculate the index in the integer array and the bit position within that integer.
    • Use bitwise operations to set or clear the specific bit.
  3. Get Operation:
    • Calculate the index in the integer array and the bit position within that integer.
    • Use bitwise operations to retrieve the specific bit.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
    public static class BitArray {
        private int[] bits;
        private int size;

        public void init(int size) {
            this.size = size;
            this.bits = new int[(size + 31) / 32];
        }

        public void set(int i, int val) {
            if (i >= size || i < 0) {
                throw new IndexOutOfBoundsException();
            }
            int arrayIndex = i / 32;
            int bitIndex = i % 32;
            if (val == 1) {
                bits[arrayIndex] |= (1 << bitIndex);
            } else {
                bits[arrayIndex] &= ~(1 << bitIndex);
            }
        }

        public int get(int i) {
            if (i >= size || i < 0) {
                throw new IndexOutOfBoundsException();
            }
            int arrayIndex = i / 32;
            int bitIndex = i % 32;
            return (bits[arrayIndex] >> bitIndex) & 1;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    class BitArray:
        def __init__(self):
            self.bits: List[int] = []
            self.size: int = 0
        
        def init(self, size: int) -> None:
            self.size = size
            self.bits = [0] * ((size + 31) // 32)

        def set(self, i: int, val: int) -> None:
            if i >= self.size or i < 0:
                raise IndexError("Index out of bounds")
            array_index = i // 32
            bit_index = i % 32
            if val == 1:
                self.bits[array_index] |= (1 << bit_index)
            else:
                self.bits[array_index] &= ~(1 << bit_index)

        def get(self, i: int) -> int:
            if i >= self.size or i < 0:
                raise IndexError("Index out of bounds")
            array_index = i // 32
            bit_index = i % 32
            return (self.bits[array_index] >> bit_index) & 1

Complexity

  • ⏰ Time complexity:
    • Initialization (init(size)): O(1) for allocating the array.
    • Set Operation (set(i, val)): O(1) for setting the bit.
    • Get Operation (get(i)): O(1) for retrieving the bit.
  • 🧺 Space complexity: O(size / 32) for the integer array used to store the bits, which is significantly less than O(size) for large size.