将字符串转换为位数组

问题描述：

我想将包含0和1的字符串转换为位数组。
该字符串是长度〜30000的和是稀疏（主要是0，很少1S）
例如，给定的字符串
“00000000100000000010000100000000001000”
我想将其转换为位的阵列，其将存储
[00000000100000000010000100000000001000]将字符串转换为位数组

我正在考虑使用BitSet或OpenBitSet 有没有更好的方法？用例是有效地执行逻辑或。

我沿着这些线路

final OpenBitSet logicalOrResult = new OpenBitSet(); 
for (final String line : lines) { 

    final OpenBitSet myBitArray = new OpenBitSet(); 
    int pos = 0; 
    for (final char c : str.toCharArray()) { 
     myBitArray.set(pos) = c; 
     pos++; 
    } 
    logicalOrResult.or(myBitArray); 
}

@ StevenA.Lowe它不是。 – Tad 2014-10-02 01:31:08

@ StevenA.Lowe这不是一个好问题，就是一个坏问题。为什么你在乎作业是否功课？ – 2014-10-02 01:31:17

@AnubianNoob：如果它是作业，我告诉OP答案，那么他们什么都没学到。请参阅http://meta.stackexchange.com/questions/18242/what-is-the-policy-here-on-homework半官方政策 – 2014-10-02 01:33:14

答

甲BitSet测距过0和30000之间的值需要一个long阵列大小小于500，所以可以假定BitSet.or（或各自的方法）将足够快，尽管稀疏。它看起来像OpenBitSet比BitSet有更好的性能，但除此之外，它使用哪个并不重要，它们都将有效地执行or。但是，请确保将字符串的长度传递给(Open)BitSet构造函数，以避免在构造过程中重新分配内部的long数组！

如果你的字符串是更长的时间，你的稀疏性极端情况下，你也可以考虑将它们作为Integer秒的排序列表（或int S，如果你使用像特罗韦库），较其含有1指数。一个按位or可以以合并（排序）方式实现，这是非常有效的（时间O（n + m），其中n，m是每个字符串中的数字）。我怀疑在你的情况下，它会比BitSet的方法慢。

我的BitSet的范围将超过值1和0 - 不是0和30000.这是你的意思吗？ – Tad 2014-10-02 11:45:25

不可以。您的'BitSet' *表示0到某个上限之间的一组整数。例如，位集01001101表示集合{0,2,3,6} - 索引集合被设置为1.这也构成了“BitSet”的'toString（）'表示。由于您的字符串的长度为〜30000，因此相应的1-indices集合的范围介于0和30000之间。 – misberner 2014-10-02 18:40:08

答

您可以通过每个字符迭代想：

boolean[] bits = new boolean[str.length]; 

for (int i=0;i<str.length;i++) { 
    if (str.charAt(i).equals("1") 
     bits[i] = true; 
    else if (str.charAt(i).equals("0") 
     bits[i] = false; 
}

如果你想成为高效存储，你可以尝试RLE (Run Length Encoding)。

我喜欢这种方法，但我已阅读http://stackoverflow.com/questions/383551 /使用BitSet的布尔变量大小是什么比使用布尔数组有更好的优化。我也在考虑RLE，这很好，因为我的数组很稀疏，但我不确定如何对压缩数组执行逻辑OR操作 - 我想我需要先解压它，除非我错过了某些东西。 – Tad 2014-10-02 01:55:07

答

BigInteger可以解析它并将其存储，并执行按位运算：

BigInteger x = new BigInteger(bitString, 2); 
BigInteger y = new BigInteger(otherBitString, 2); 
x = x.or(y); 
System.out.println(x.toString(2));

您是否知道BigInteger和OpenBitSet以及BitSet（或任何其他库）之间是否有任何基准执行逻辑OR？ – Tad 2014-10-02 01:46:26

@Tad我不知道，但您可以通过在预期应用程序中执行基准来轻松比较它们。 – Boann 2014-10-02 01:51:13

将字符串转换为位数组

相关推荐