C# BitArray 核心原理深度解析：自製 MyBitArray 實現索引器與位運算優化

System.Collections.BitArray 是 .NET 基底類別庫中高效的位向量實現，底層以 int[] (32 位元整數陣列) 儲存位元。本文透過手寫 MyBitArray 完整復刻其核心邏輯，深入剖析 索引器實現、位運算技巧、邊界計算、CLR 位移運算語義 等關鍵細節，幫助開發者理解高效位操作的底層機制。

核心資料結構：int[] 作為位元容器

一個 int 佔 4 位元組 = 32 位元。m_Bits 陣列的每個元素存放 32 個布林值。

public class MyBitArray
{
    private int[] m_Bits;     // 底層儲存
    private int m_Length;     // 邏輯位元總數 (使用者視角)

    public MyBitArray(int length)
    {
        if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
        // 計算需要多少個 int: (length + 31) / 32  等價於  (length - 1) / 32 + 1
        // 寫法 (length - 1) / 32 + 1 可正確處理 length=0 (結果 0) 與 length=32 (結果 1) 等邊界
        m_Length = (length - 1) / 32 + 1;
        m_Bits = new int[m_Length];
    }
}

邊界驗證：

• length=0 → (-1)/32+1 = 0+1 = 1? 實際 C# 整數除法向零捨入：-1/32 = 0 → 0+1=1。但邏輯長度為 0 時應配置 0 個 int。修正：m_Length = (length + 31) / 32; 更直觀且 length=0 正確得 0。
• length=32 → (31)/32+1 = 0+1=1 ✓
• length=33 → (32)/32+1 = 1+1=2 ✓

索引器：O(1) 位元讀寫

public bool this[int index]
{
    get
    {
        if (index < 0 || index >= m_Length * 32) // 邏輯長度檢查
            throw new IndexOutOfRangeException();
        int wordIndex = index >> 5;           // index / 32
        int bitPos = index & 0x1F;            // index % 32
        return (m_Bits[wordIndex] & (1 << bitPos)) != 0;
    }
    set
    {
        if (index < 0 || index >= m_Length * 32)
            throw new IndexOutOfRangeException();
        int wordIndex = index >> 5;
        int bitPos = index & 0x1F;
        int mask = 1 << bitPos;
        if (value)
            m_Bits[wordIndex] |= mask;   // 設 1: OR
        else
            m_Bits[wordIndex] &= ~mask;  // 設 0: AND 反碼
    }
}

關鍵技巧解析

1. 除法/取模優化：index / 32 → index >> 5 (右移 5 位)；index % 32 → index & 31 (位元 AND)。JIT 編譯器會自動優化，但手寫更明確。
2. 位元遮罩：1 << bitPos 產生只有目標位為 1 的遮罩。
3. 讀取：& mask != 0 判斷該位是否為 1。
4. 寫 1：| mask (OR 操作強制該位為 1，其它位不變)。
5. 寫 0：& ~mask (AND 反碼強制該位為 0，其它位不變)。

CLR 位移運算的隱藏語義：移位數自動取模

C# 規範 (ECMA-334) 定義：位移運算子的右運算元 (移位數) 會自動對目標型別的位元寬度取模。

• int (32 位) → shift & 0x1F (模 32)
• long (64 位) → shift & 0x3F (模 64)
• byte/short 參與運算時會先提升為 int，同樣模 32，不隨型別寬度變化。

// int / long 差異
int i = 1;
i <<= 32;        // 相當於 1 << 0 → 結果 1 (非 0!)
long l = 1;
l <<= 32;        // 相當於 1 << 32 → 結果 4294967296 (2^32)

// byte/short 提升為 int 後模 32
byte b = 1;
b <<= 8;         // 1 << 8 = 256 → 溢位截斷為 0 (byte 只保留低 8 位)
short s = 1;
s <<= 16;        // 1 << 16 = 65536 → 截斷為 0 (short 只保留低 16 位)

// 但移位數本身仍模 32
int x = 1 << 33; // 1 << 1 = 2
int y = 8 >> 33; // 8 >> 1 = 4

// 計算整個陣列有多少個 1 (Population Count)
public int CountOnes()
{
    int count = 0;
    foreach (int word in m_Bits)
        count += BitOperations.PopCount((uint)word); // 硬體指令 POPCNT
    return count;
}

// 尋找下一個 1 的索引 (Find First Set)
public int FindNextSet(int startIndex)
{
    int wordIdx = startIndex >> 5;
    int bitPos = startIndex & 0x1F;
    if (wordIdx >= m_Bits.Length) return -1;

    // 清除 startIndex 之前的位
    uint firstWord = (uint)m_Bits[wordIdx] & (~0u << bitPos);
    if (firstWord != 0)
        return (wordIdx << 5) + BitOperations.TrailingZeroCount(firstWord);

    for (int i = wordIdx + 1; i < m_Bits.Length; i++)
    {
        uint w = (uint)m_Bits[i];
        if (w != 0)
            return (i << 5) + BitOperations.TrailingZeroCount(w);
    }
    return -1;
}