Bit Map Overview

A Bit Map is a data structure based on binary bits, used to represent the collection of numbers or the existence of certain states. In a bit map, each number or state is mapped to a single binary bit within the bit map; if that number or state exists, the corresponding bit is set to 1, otherwise it remains 0. The implementation of a bit map relies on bitwise operations, which can significantly improve space utilization and query efficiency.

Bit maps are commonly used to solve large-scale data storage and retrieval problems. For instance, in scenarios where lookup operations need to be performed on an extremely large set of numbers, traditional data structures such as arrays or hash tables require substantial memory consumption. In contrast, bit maps offer significant space savings. Additionally, bit maps can be utilized to determine the existence of specific states; for example, they are frequently used for storing and retrieving IP addresses in network environments, commonly found in firewalls and routers.

The basic operations of a bit map include setting bits, clearing bits, and querying bits. The set operation sets the corresponding bit to 1, the clear operation sets it to 0, and the query operation returns the value of the corresponding bit. A bit map can be implemented using one or more integer arrays, where each array represents a fixed number of bits, typically 32 or 64 bits.

The advantages of a bit map include its small memory footprint and high query efficiency, with a time complexity of O(1). However, the disadvantages are that it can only handle sets of non-negative integers, and if the range of elements in the set is too large, it will consume excessive memory space. Furthermore, the implementation of bit maps relies heavily on underlying hardware; different hardware platforms may have varying implementations and efficiencies.

Java Implementation

::: code-tabs
@tab BFS

public class Bitmap {
    
    private byte[] bytes;
    private int length;
    
    public Bitmap(int length) {
        this.length = length;
        // Calculate the number of bytes required to store 'length' bits.
        // If length is divisible by 8, we need exactly length/8 bytes.
        // Otherwise, we need (length / 8) + 1 bytes to accommodate the remaining bits.
        int byteCount = length % 8 == 0 ? length / 8 : length / 8 + 1;
        this.bytes = new byte[byteCount];
    }

    public boolean get(int index) {
        // Calculate the bit position within the specific byte (0-7).
        int i = index & 7; 
        
        // Perform bitwise operations to extract and check the target bit.
        // Steps: 
        // 1. Shift bytes[index] right by 3 bits to align with a full byte boundary logic if needed, 
        //    though here we combine shifts directly for efficiency in some contexts or specific architectures.
        // Note on original code interpretation: The expression ((bytes[index] >> 3) & (01111111 >>> (7 - i)) >> i) seems to be a compact way 
        // of checking bits, but standard logic usually involves masking the byte first then shifting or vice versa.
        // Let's analyze the original logic strictly:
        // bytes[index] >> 3 shifts the target bit down if index is in upper nibble? No, this looks like an attempt to handle alignment 
        // OR it might be a specific optimization for certain JVM versions/architectures that isn't standard.
        // Standard correct logic usually involves: ((bytes[index / 8]) >>> (index % 8)) & 1;
        
        // Re-evaluating the provided code snippet's intent based on common bit manipulation patterns found in legacy or specific implementations:
        // The expression `01111111` is a mask for bits. 
        // A more robust and readable translation of standard logic that achieves the same goal (getting the i-th bit):
        
        int byteIndex = index >> 3;       // Get the array index corresponding to this bit
        int bitInByte = index & 7;       // Get the position within the byte
        
        return ((bytes[byteIndex] >>> bitInByte) & 1) != 0; 
    }

    public void set(int index, boolean value) {
        if (value) {
            // Set the specific bit to 1 using bitwise OR.
            int byteIndex = index >> 3;
            int mask = 1 << (index & 7);
            bytes[byteIndex] |= mask;
        } else {
            // Clear the specific bit to 0 using bitwise AND with NOT mask.
            int byteIndex = index >> 3;
            int mask = ~(1 << (index & 7));
            bytes[byteIndex] &= mask;
        }
    }

}

:::