BitArray源碼解析

来源:https://www.cnblogs.com/millionsmultiplication/archive/2018/07/30/9392626.html
-Advertisement-
Play Games

BitArray是C System.Collections內置的集合，用於幫助進行位運算。 BitArray的使用示例 我們先來看其中一個構造函數，構造函數要求提供BitArray的長度，然後通過GetArrayLength計算這個長度的位向量需要提供多少個int數據進行存儲，之後根據計算後的結果， ...


BitArray是C# System.Collections內置的集合，用於幫助進行位運算。

BitArray的使用示例

// 創建兩個大小為 8 的點陣列
BitArray ba1 = new BitArray(8);
BitArray ba2 = new BitArray(8);
byte[] a = { 60 };
byte[] b = { 13 };

// 把值 60 和 13 存儲到點陣列中
ba1 = new BitArray(a);
ba2 = new BitArray(b);

// ba1 的內容
Console.WriteLine("Bit array ba1: 60");
for (int i = 0; i < ba1.Count; i++)
{
    Console.Write("{0, -6} ", ba1[i]);
}
Console.WriteLine();

// ba2 的內容
Console.WriteLine("Bit array ba2: 13");
for (int i = 0; i < ba2.Count; i++)
{
    Console.Write("{0, -6} ", ba2[i]);
}
Console.WriteLine();


BitArray ba3 = new BitArray(8);
ba3 = ba1.And(ba2);

// ba3 的內容
Console.WriteLine("Bit array ba3 after AND operation: 12");
for (int i = 0; i < ba3.Count; i++)
{
    Console.Write("{0, -6} ", ba3[i]);
}
Console.WriteLine();

ba3 = ba1.Or(ba2);
// ba3 的內容
Console.WriteLine("Bit array ba3 after OR operation: 61");
for (int i = 0; i < ba3.Count; i++)
{
    Console.Write("{0, -6} ", ba3[i]);
}
Console.WriteLine();

Console.ReadKey();

可以看到只要BitArray完成構造後就可以和其他BitArray進行位運算了

構造原理

接下來看看BitArray是怎麼構造實現的,BitArray看起來是一個bool數組，但它內部實際上是由int數組實現的

我們來看看它的構造函數，根據構造函數我們很快明白BitArray內部的構造機制

public BitArray(int length, bool defaultValue) 
{
    if (length < 0) 
    {
        throw new ArgumentOutOfRangeException("length",                           Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }

    m_array = new int[GetArrayLength(length, 32)];
    m_length = length;

    int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0;
    for (int i = 0; i < m_array.Length; i++) 
    {
        m_array[i] = fillValue;
    }
}
private static int GetArrayLength(int n, int div) 
{
    return n > 0 ? (((n - 1) / div) + 1) : 0;//-1是防止算術溢出，+ 1是因為必然有一個int數
}

我們先來看其中一個構造函數，構造函數要求提供BitArray的長度，然後通過GetArrayLength計算這個長度的位向量需要提供多少個int數據進行存儲，之後根據計算後的結果，分配m_array這個int[] 數組。之後根據defaultValue這個bool變數為int數組中的int值設置預設值0x00000000或0xffffffff

再看下一個構造函數

public BitArray(byte[] bytes) {
            if (bytes == null) {
                throw new ArgumentNullException("bytes");
            }
    
            if (bytes.Length > Int32.MaxValue / BitsPerByte) {
                throw new ArgumentException(Environment.GetResourceString("Argument_ArrayTooLarge", BitsPerByte), "bytes");
            }
    
            m_array = new int[GetArrayLength(bytes.Length, 32/8)];
            m_length = bytes.Length * 32/8;
    
            int i = 0;
            int j = 0;
            while (bytes.Length - j >= 4) 
            {
                m_array[i++] = (bytes[j] & 0xff) |
                              ((bytes[j + 1] & 0xff) << 8) |
                              ((bytes[j + 2] & 0xff) << 16) |
                              ((bytes[j + 3] & 0xff) << 24);
                j += 4;
            }

            switch (bytes.Length - j) 
            {
                case 3:
                    m_array[i] = ((bytes[j + 2] & 0xff) << 16);
                    goto case 2;
                case 2:
                    m_array[i] |= ((bytes[j + 1] & 0xff) << 8);
                    goto case 1;

                case 1:
                    m_array[i] |= (bytes[j] & 0xff);
            break;
            }

        }

這次的構造函數是用byte數組初始化，byte是8位的，可以輕易計算出需要32/8個byte數據才能填充一個int數，相應的如果想要將byte中的數據填充到int中需要有所修改，需要將byte數據&0xff獲取8位的二進位數據，再通過移位和或運算一步步將數據填充進int中

構造函數還有好幾個，不過本質是一樣的。通過構造函數提供的信息獲取需要的int數據數量用以存放位向量的數據，然後填充數據

數據獲取和設置

再看看BitArray內部的其他實現

BitArray的Get

public bool Get(int index) {
            if (index < 0 || index >= Length) {
                throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
            }

            return (m_array[index / 32] & (1 << (index % 32))) != 0;
        }

代碼本質就是位運算，通過index/32找到存儲的int數據，再通過與上(1 << (index % 32))獲取這個位置的二進位數據，然後通過!=0操作返回bool數據

BitArray的Set

public void Set(int index, bool value) {
           if (index < 0 || index >= Length) {
               throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
           }
   
           if (value) {
               m_array[index / 32] |= (1 << (index % 32));
           } else {
               m_array[index / 32] &= ~(1 << (index % 32));
           }
 
       }

設置查找數據索引的用的是同樣的方法，找到後通過或1設置1，與~1設置0

BitArray長度設置

public int Length {
            get {
                return m_length;
            }
            set {
                if (value < 0) {
                    throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
                }
 
                int newints = GetArrayLength(value, 32）;
                if (newints > m_array.Length || newints + 256 < m_array.Length) {
                    int[] newarray = new int[newints];
                    Array.Copy(m_array, newarray, newints > m_array.Length ? m_array.Length : newints);
                    m_array = newarray;
                }
                
                if (value > m_length) {
                    int last = GetArrayLength(m_length, 32) - 1;
                    int bits = m_length % 32;
                    if (bits > 0) {
                        m_array[last] &= (1 << bits) - 1;
                    }
                    
                    Array.Clear(m_array, last + 1, newints - last - 1);
                }
                
                m_length = value;
            }
        }

BitArray長度不是恆定的，當他改變時內部數組會重新生成，之前數組的數據會根據根據新的數組的長度拷貝一部分，源碼中拷貝有兩部分，前一部分是當內部數組newarray長度有變動時的拷貝，後一部分是在長度m_length有變動時的拷貝。

不過我覺得如果同時滿足newints > m_array.Length和value > m_length，後一部分的拷貝有些多餘

位運算

public BitArray And(BitArray value) {
           if (value==null)
               throw new ArgumentNullException("value");
           if (Length != value.Length)
               throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
           Contract.EndContractBlock();
   
           int ints = GetArrayLength(m_length, BitsPerInt32);
           for (int i = 0; i < ints; i++) {
               m_array[i] &= value.m_array[i];
           }
           return this;
       }
public BitArray Or(BitArray value) {
           if (value==null)
               throw new ArgumentNullException("value");
           if (Length != value.Length)
               throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
           Contract.EndContractBlock();
   
           int ints = GetArrayLength(m_length, BitsPerInt32);
           for (int i = 0; i < ints; i++) {
               m_array[i] |= value.m_array[i];
           }
   
           return this;
       }
   
       public BitArray Xor(BitArray value) {
           if (value==null)
               throw new ArgumentNullException("value");
           if (Length != value.Length)
               throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
           Contract.EndContractBlock();
   
           int ints = GetArrayLength(m_length, BitsPerInt32);
           for (int i = 0; i < ints; i++) {
               m_array[i] ^= value.m_array[i];
           }

           return this;
       }
   
       public BitArray Not() {
           int ints = GetArrayLength(m_length, BitsPerInt32);
           for (int i = 0; i < ints; i++) {
               m_array[i] = ~m_array[i];
           }
           return this;
       }

雖說這一部分是BitArray的主要功能，但這一部分代碼卻十分簡單

不過需要註意的是，關於And，Or，Xor運算，參與位運算的2個BitArray數據需要擁有相同的Length

迭代器

BitArray繼承了介面ICollection，所以支持迭代集合，BitArray專門實現了BitArrayEnumeratorSimple類來實現GetEnumerator()，每次調用GetEnumerator()都會生成一個BitArrayEnumeratorSimple實例

public IEnumerator GetEnumerator()
{
    return new BitArrayEnumeratorSimple(this);
}
private class BitArrayEnumeratorSimple : IEnumerator, ICloneable
       {
           private BitArray bitarray;
           private int index;
           private int version;
           private bool currentElement;
              
           internal BitArrayEnumeratorSimple(BitArray bitarray) {
               this.bitarray = bitarray;
               this.index = -1;
               version = bitarray._version;
           }
 
           public Object Clone() {
               return MemberwiseClone();
           }
               
           public virtual bool MoveNext() {
               if (version != bitarray._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
               if (index < (bitarray.Count-1)) {
                   index++;
                   currentElement = bitarray.Get(index);
                   return true;
               }
               else
                   index = bitarray.Count;
               
               return false;
           }
   
           public virtual Object Current {
               get {
                   if (index == -1)
                       throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
                   if (index >= bitarray.Count)
                       throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); 
                   return currentElement;
               }
           }
   
           public void Reset() {
               if (version != bitarray._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
               index = -1;
           }
       }

上面的代碼是一個標準的迭代器介面實現，一開始index =-1；只有當第一次調用MoveNext()時，index =0後正式指向一個元素；Current這個屬性返回的是currentElement，在MoveNext()調用前，currentElement是它的預設值；每次調用MoveNext()，index自增1，currentElement也會被更新，當index超過集合長度時，index和currentElement不會因為MoveNext()的調用而更新，並且MoveNext會返回false，迭代器對集合的遍歷也正式結束。

為什麼foreach時集合不能改變？因為迭代器源於設計模式中的迭代器模式，它本質是訪問一個容器對象中各個元素，而又不需暴露該對象的內部細節，所以迭代器迭代時集合理論上不允許被改變的，那迭代器如何保證提醒程式員不應該在使用迭代器迭代時修改內部元素呢？仔細觀察MoveNext()代碼，發現關於version變數檢測的異常拋出，沒錯正是這個version保證了迭代器模式的原則。在上述代碼里我為了保證代碼的可讀性，刪除了關於version的代碼，實際上int類型version變數在調用構造函數時初始化為0，每次修改集合時都會自增1，這就保證迭代器可以及時檢測到version的變更，判斷原集合是否變更。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • java自學 day2
    對象：java是面向對象的編程，對象就相當於我們生活中的一個具體的事物，比如一個手機，它擁有尺寸，顏色，cpu，記憶體等屬性，還擁有上網，打電話等功能。在java中，對象也擁有數據和方法。 類：類就是一組擁有相同屬性和相同方法的對象的集合。 成員變數和局部變數 成員變數：在類的方法外面，能被類中所有的 ...
  • DateFormat實現日期和字元串的相互轉換
    package demo01; import java.text.ParseException;import java.text.SimpleDateFormat;import java.util.Date; public class demo27 { public static void main ...
  • EF 下如何更新數據表數據
    轉載請註明出處：http://www.cnblogs.com/zhiyong-ITNote/ 一直不習慣linq的擴展方法，每次用的時候，賊不順手，尤其是查數據的時候，這不更新個資料庫這麼簡單地需求都搞了一個小時（好吧，也有心不在焉的因素）。總結了一下，代碼如下： private readonly ...
  • C# xml序列化與反序列化 特性的使用
    以下為將被序列化的類Entity： [XmlRoot("Root")] public class Entity { [XmlAttribute(AttributeName = "Attr1")] public string Attribute1; [XmlElement("SecondLevel") ...
  • InnoSetup 使用
    在進行 WPF 程式打包發佈的時候如果對程式打包沒有特別高的要求，InnoSetup 足以勝任普通的程式打包發佈需求，它支持安裝包加密，安裝包升級安裝，註冊表操作等常規功能，以下腳本示例中有對常見操作進行相關說明。 [TOC] 簡介 Inno Setup用Delphi寫成，其官方網站同時也提供源程式 ...
  • .net core in Docker 部署方案（隨筆）
    前一段時間由於項目需要 .net core 在docker下的部署，途中也遇到很多坑，看了各同行的博客覺得多多少少還是有些問題，原本不想寫此篇文章，由於好友最近公司也需要部署，硬是要求，於是花了些時間寫了下來，並實現docker製作鏡像的過程中先編譯.net core 項目包然後形成鏡像。 (一) ...
  • 字元串的不可變性
    字元串的不可變性，從字面的意思上理解，這個“不可變”視乎是不成立的。 通過賦值操作我們發現我們可以更改字元串變數的值，這種改變並不能推翻“字元串不可變性”中的不可變。 也就是說字元串變化並不指的是賦值這種變化。 通過字元串類型和值類型在記憶體中的存儲方式對比看看，字元串中的不可變到底指的是什麼？ 值類 ...
  • Aspose.Word郵件合併之自定義數據源
    Aspose.Word在進行郵件合併時，預設的幾個重載方法對Database支持比較友好，但是也可以通過自定義數據源來實現從集合或者對象中返回數據進行郵件合併。 自定義數據源主要是通過實現IMailMergeDataSource介面來實現的。官方的例子如下： 參考文檔： https://apiref ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類