驗證大整數的二進制模式（BigInteger）

我想測試一個正整數來查看它的二進制表示是否以零或多個1開始，然後是一個或多個0。驗證大整數的二進制模式（BigInteger）

00000000 // Valid 
10000000 // Valid 
11000000 // Valid 
11100000 // Valid 
11110000 // Valid 
11111100 // Valid 
11111110 // Valid 
11111110 // Valid 
11111111 // Not Valid 
// Any other combination is Not Valid

表達式與正則表達式相同將是^ [1] * [0] + $。當然，這只是爲了澄清，我們不能使用正則表達式。

的蠻力方法：

創建多個位掩碼，共同確定的結果。
用動態掩碼循環顯示每個數字以確定結果。

問題是我正在處理巨大的正整數，它可能有數十萬個數字，並且需要爲數千個這樣的數字執行此測試。

是否有更有效的方法來確定這種二進制模式？

UPDATE

這裏是我試過的實現。還沒有比較時間與其他答案。

public static bool IsDiagonalToPowerOfTwo (this System.Numerics.BigInteger number) 
{ 
    byte [] bytes = null; 
    bool moreOnesPossible = true; 

    if (number == 0) // 00000000 
    { 
     return (true); // All bits are zero. 
    } 
    else 
    { 
     bytes = number.ToByteArray(); 

     if ((bytes [bytes.Length - 1] & 1) == 1) 
     { 
      return (false); 
     } 
     else 
     { 
      for (byte b=0; b < bytes.Length; b++) 
      { 
       if (moreOnesPossible) 
       { 
        if (bytes [b] == 255) 
        { 
         // Continue. 
        } 
        else if 
        (
         ((bytes [b] & 128) == 128) // 10000000 
         || ((bytes [b] & 192) == 192) // 11000000 
         || ((bytes [b] & 224) == 224) // 11100000 
         || ((bytes [b] & 240) == 240) // 11110000 
         || ((bytes [b] & 248) == 248) // 11111000 
         || ((bytes [b] & 252) == 252) // 11111100 
         || ((bytes [b] & 254) == 254) // 11111110 
        ) 
        { 
         moreOnesPossible = false; 
        } 
        else 
        { 
         return (false); 
        } 
       } 
       else 
       { 
        if (bytes [b] > 0) 
        { 
         return (false); 
        } 
       } 
      } 
     } 
    } 

    return (true); 
}

來源

2012-08-05 Raheel Khan

你實際上是在使用它們*作爲整數*，還是就像位存儲一樣？坦率地說，如果這些是唯一有效的集合，我會使用不同的表示法，即。「數量，零的數量」。當然，如果你需要做算術不工作等 – 2012-08-05 15:59:40

http://graphics.stanford.edu/~seander/bithacks.html – 2012-08-05 16:09:42

我不知道什麼是HUME大整數，這是如何表示的。淨？我想數組的ubyte/uint/etc ......是這樣嗎？ @MarcGravell已經問過，但是，你是用這些數據做一些算術還是隻是一種表示？ – devundef 2012-08-05 16:25:00

假設的整數被存儲在二進制，歸納爲一個數組x []無符號整數，則可以做到這一點：

Define UINT to be the unsigned integer type you are using for the grouped bits. 
Define UMAX to be the maximum value of that type (all bits are on). 

// Find first word that has a zero bit. 
int i; 
for (i = highest word in x; 0 <= i; --i) 
    if (x[i] != UMAX) 
     break; 

// Return true if all bits in all of x[] are on. 
if (i < 0) 
    return true; 

// Test whether word conforms to the ones-then-zeroes rule. 
UINT y = x[i]; 
if (y + (y & -y)) 
    return false; 

// Test whether all remaining words are zero. 
for (; 0 <= i; --i) 
    if (x[i]) 
     return false; 

return true;

在y + (y & -y)，y & -y返回最低位在y中設定。（證明作爲讀者的練習。）如果y中的所有高位都打開，則添加最低位將導致進位通過所有這些位傳播，並將其更改爲零。如果任何一個高位關閉，進位停止，結果不爲零。否則，結果爲零。

你可以改進上述嗎？假設比較和分支比像AND這樣的操作成本更高。在這種情況下，您可以使用二進制搜索來查找數組中所有值都從零變爲全零或不變的位置。測試如上所述的關鍵詞，然後將所有更高的值和在一起，並測試所有1的結果，然後將所有更低的值合併，並測試所有零的結果。

這就給了你一個二進制搜索，然後一個負載和一個AND或OR每個字。這很難改進。

來源

2012-08-05 18:01:40

謝謝。我會嘗試這兩種方法，然後回覆多少改進，與從左到右的字節數組掩碼進行比較，預定義掩碼爲128,192,224,240,252和254. – 2012-08-05 18:46:08

非常優雅：y +（ y＆-y）。我用我的答案。 – devundef 2012-08-06 15:14:01

謝謝。 BigInteger類公開ToByteArray函數。轉換爲long/ulong等數組會導致額外的開銷。你的函數是否有任何理由不適用於字節數組？ – 2012-08-07 14:18:01

在最壞的情況下，而無需關於存儲，不能做得比一個O（Ñ）算法更好輸入附加的數據 - 其中Ñ是比特數 - 因爲需要檢查數字中的每一位。

如果您可以跟蹤例如在以前的操作過程中「最右邊1」和「最左邊0」，您可以通過檢查這些確實是否爲「10」來立即獲得答案。

否則，你只需要有效地迭代比特來檢查它是否正確。請注意，從左側開始數字直到您點擊1，然後檢查所有內容爲0（具有適當的角落案例）爲O（n），而具有O的完整列表（n）可能的值和檢查它是否等於（推測是？）O（n）比較中的任何一個是O（n^2），因此是一個壞主意。

來源

2012-08-05 16:05:08 Sharkos

鴻溝您的二進制數據轉換成具有固定尺寸... 32位... 64位的塊 - >將它們視爲無符號整數

製備含有所有有效圖案的兩個包含HashMap和逆圖案（帶開始「0」，而如果最左邊的塊被包含在相反的圖案HashMap的「1」）......再次無符號整數

現在測試結束...如果不是 - >模式是無效的
現在測試，如果最右邊（非零）塊包含在正常模式hashmap中...如果不是 - >模式無效

現在測試所有其他塊是否等於所有比特設置的模式（這應該是一個無符號整數的比較）...如果全部相等 - >模式有效...否則...圖案是無效

來源

2012-08-05 16:14:01 DarkSquirrel42

驗證大整數的二進制模式（BigInteger）

回答

相關問題