改進算法的：在計數設置位字節數組

我們存儲在字節數組爲比特知識。計數設置位數很慢。提高算法任何建議，歡迎：改進算法的：在計數設置位字節數組

public static int countSetBits(byte[] array) { 
    int setBits = 0; 

    if (array != null) { 
     for (int byteIndex = 0; byteIndex < array.length; byteIndex++) { 
      for (int bitIndex = 0; bitIndex < 7; bitIndex++) { 
       if (getBit(bitIndex, array[byteIndex])) { 
        setBits++; 
       } 
      } 
     } 
    } 
    return setBits; 
}

public static boolean getBit(int index, final byte b) { 
    byte t = setBit(index, (byte) 0); 
    return (b & t) > 0; 
}

public static byte setBit(int index, final byte b) { 
    return (byte) ((1 << index) | b); 
}

要計算的156'564長度的字節數組的比特需要300毫秒，這太過分了！

來源

2013-02-15 myborobudur

你可以分享'getBit'方法嗎？ – Apurv 2013-02-15 12:18:40

我不知道這是否適用於您的問題，但也許您可以單獨維護計數。 – 2013-02-15 12:18:54

請分享'getBit'功能 – TheBronx 2013-02-15 12:29:11

嘗試Integer.bitcount以獲得每個字節設置的位的數目。這將是更有效的，如果你可以從一個byte陣列切換到int陣列。如果這是不可能的，你也可以建立一個查找表的所有256個字節快速查找計數，而不是遍歷各個位。

如果它總是整個陣列的數量，你有興趣，你可以在存儲計數在一個單獨的整數每當陣列變化的一類包裝的陣列。（編輯：或者說，事實上，在評論中指出，使用java.util.BitSet）

來源

2013-02-15 12:19:04 Arkku

謝謝！只要Integer.bitcount（）使它快12倍！大概我會在稍後看看BitSet到 – myborobudur 2013-02-15 15:24:33

請小心使用Integer.bitcount這種方式，因爲如果你有一個10000000的字節，這是2s恭維的-128，你將它傳遞給Integer.bitcount ，你會得到25（不是1），因爲它需要你投到一個int，它會自動填充它認爲是2s恭維的負數。 – Joel 2014-10-18 01:42:56

我會使用相同的全局循環，但不是每個字節的內部循環，我會簡單地使用的大小爲256映射字節（預計算的）陣列的位計數。這可能是非常有效的。

如果您需要更大的速度，那麼你應該分別保持計數並加和減少它設置位時（但是這將意味着對那些操作大的額外負擔，所以我不知道這對你是適用）。

另一種解決方案將基於BitSet implementation：它使用的長（而不是字節）的數組，這裏是它如何計算：

658  int sum = 0; 
659  for (int i = 0; i < wordsInUse; i++) 
660   sum += Long.bitCount(words[i]); 
661  return sum;

來源

2013-02-15 12:22:39

Integer.bitcount（）改進它！ – myborobudur 2013-02-15 15:25:25

我會用：

byte[] yourByteArray = ... 
    BitSet bitset = BitSet.valueOf(yourByteArray); // java.util.BitSet 
    int setBits = bitset.cardinality();

我不不知道它是否更快，但我認爲它會比你擁有的更快。讓我知道？

你的方法看起來就像

public static int countSetBits(byte[] array) { 
    return BitSet.valueOf(array).cardinality(); 
}

你說：

我們儲存知識的字節數組作爲位。

我建議使用BitSet。它可以讓你方便的方法，你似乎是有意位，不是字節，所以相比byte[]一個更適當的數據類型。（它在內部使用long[]）。

來源

2013-02-15 12:25:38 jlordo

如果意味着作爲OP解決方案的全球替代品，而不僅僅是位計數，它可能更快更好。 – 2013-02-15 12:28:15

@dystroy：看我的編輯;） – jlordo 2013-02-15 12:30:33

我有一個改進與Integer.bitcount（）; BitSet.valueOf（）僅適用於java7 – myborobudur 2013-02-15 15:29:18

-1

按我understaning，

1字節= 8個比特

因此，如果字節數組的大小= n，則不是比特的總數= N * 8？

請糾正我，如果我的理解是錯誤的

感謝維諾德

來源

2013-02-15 13:12:22

這是正確的！ – myborobudur 2013-02-15 13:41:14

這提供了數組中的位數，但實際的問題是計算數組中的位數。 – 2013-02-15 20:12:14

到目前爲止，最快的方法是計數位設置，在「平行」，方法被調用Hamming weight ，並在Integer.bitCount(int i)儘可能實現我所知。

來源

2016-12-06 11:36:41 Jinxmcg

改進算法的：在計數設置位字節數組

回答

相關問題