插入比特流

Question

我正在尋找一種方法來有效地將比特插入到比特流中，並使它'溢出'，填充0。例如，如果你有一個2字節的字節數組：231和109（11100111 01101101），並且做了BitInsert（byteArray，4,00），它會在位偏移4處插入兩位，使11100001 11011011 01000000（225,219 ，24）。即使該方法只允許1位插入，例如BitInsert（byteArray，4，true）或BitInsert（byteArray，4，false），但該方法必須與比特流長度無關（該流可能跨越幾百字節值）。

我做這件事的一種方法，但它必須走與位位掩碼位流，所以我不知道如果有一個簡單的方法......在裝配

答案或C衍生物將不勝感激。

編輯：特定用例是一種編碼方案的實現，它一次讀取6位字節數組，並將它們（用2位填充）編碼爲單個字節。所以每6位，你插入2位。 {33,66,99}這是一個比特流是 001000010100001001100011變得 00001000000101000000100100100011通知插件爲XX： xx001000xx010100xx001001xx100011

我希望換一種方式來做到這一點沒有位行走... （另外如果有人知道這個編碼方案的正式名稱，這將是有益的，因爲我還沒有識別它...當將舊的C程序移植到C＃時出現）

Answer 1

如果你知道你的輸出將適合變成類似int32或int64的東西，你可以使用bitshift操作符>>。

1. 使用一組預定義的蒙版將輸入流分成兩部分。
2. 使用>>將尾端移動的位數等於所需插入的長度。
3. 對插入件做同樣的事情。
4. 使用|操作員將所有3件組合在一起。

Answer 2

我有一個小時，監考測試殺的，這裏的結果：

class BitStream 
{ 
    private List<byte> _bytes; 

    public BitStream() 
    { 
     _bytes = new List<byte>(); 
     _bytes.Add(0); 
    } 

    public byte[] Data 
    { 
     get { return _bytes.ToArray(); } 
    } 

    public void Insert(int index, int value) 
    { 
     if (value < 0) 
      value *= -1; 

     int bit = value % 2; 

     byte bitmask = GetBitmask(index, bit); 

     // perform the right-shift operation 
     int active_byte = index/8; 

     bool padded = PadIfNecessary(); 

     int i; 
     if (padded) 
      i = _bytes.Count - 2; 
     else 
      i = _bytes.Count - 1; 

     for (; i > active_byte; --i) 
     { 
      _bytes[i] = (byte)(_bytes[i] << 1); 

      // carry from earlier byte if necessary 
      if ((_bytes[i - 1] & 128) == 128) 
       _bytes[i] |= 1; 
     } 

     // now shift within the target byte 
     _bytes[active_byte] = ShiftActiveByte(_bytes[active_byte], index); 

     _bytes[active_byte] |= GetBitmask(index, bit); 
    } 

    protected byte ShiftActiveByte(byte b, int index) 
    { 
     index = index % 8; 
     byte low_mask = 0; 
     byte high_mask = 255; 

     for (int i=0; i<index; ++i) 
     { 
      low_mask = (byte)((low_mask << 1) | 1); 
      high_mask = (byte)(high_mask << 1); 
     } 

     byte low_part = (byte)(b & low_mask); 
     byte high_part = (byte)(b & high_mask); 

     high_part <<= 1; 

     return (byte)(low_part | high_part); 
    } 

    protected byte GetBitmask(int index, int value) 
    { 
     return (byte)(value << (index % 8)); 
    } 

    protected bool PadIfNecessary() 
    { 
     if ((_bytes[_bytes.Count - 1] & 128) == 128) 
     { 
      _bytes.Add(1); 
      return true; 
     } 
     else return false; 
    } 
} 

它不會處理超出了內部數組的現有邊界的索引處插入，但在其他方面手柄本身在我的非正式煙霧測試中正確。

Answer 3

高效的選擇將很大程度上取決於您的瓶頸。由於您特別要求插入，所以我認爲您的應用程序需要執行大量的隨機訪問插入操作，而且實際上只需要在一段時間內按順序讀取完整的流。如果是這樣的話，這裏有一些可能的選項：

選項1：字節的鏈表

struct BitStreamNode; 
{ 
    Byte size; 
    Byte bits; 
    BitStreamNode * next; 
}; 

這最適合在情況下，你可以保持一個指向該節點上，你想要插入比特。如果您必須將插入點指定爲數字索引，請參閱選項2.請注意，我已包含大小成員。這將允許你插入兩個位如下：

BitStreamNode newNode; 
newNode.bits = 0x02; // for example 
newNode.size = 2; 

newNode.next = nodeToInsertAfter.next; 
nodeToInsertAfter.next = newNode; 

在現有節點的中間插入當然會要求分割節點分成兩個部分。再次，讓我強調，如果你a）經常這樣做，並且b）在你的流中有大量的位，這隻會比將整個數組移到正確的位置更有效。

選項2：均衡的樹結構

此方法將使用類似的節點作爲選項1中所概述的，但將包括在每個節點處的數值索引，並以較高的和較低的索引節點的鏈路。其基本思想是減少查找流內特定節點的確切位置所需的時間，但增加了到下一節點和前一節點的順序鏈接（以便能夠讀取流爲了）。

更新：確切的定義似乎是一個 「threaded tree」。

這一個需要大量的工作才能正確實施，所以我只會建議你走這條路，如果你確信速度的提升是值得的。即：介紹基本的強力解決方案，然後評估投入額外工作和複雜性的優缺點。