转移Java BitSet
我使用java.util.BitSet来存储密集的位向量。
我想实现一个将位向右移1的操作，类似于>>> on int。
是否有一个库函数可以移动BitSet ？
如果没有，是否有比下面更好的方法？
public static void logicalRightShift(BitSet bs) { for (int i = 0; (i = bs.nextSetBit(i)) >= 0;) { // i is the first bit in a run of set bits. // Set any bit to the left of the run. if (i != 0) { bs.set(i - 1); } // Now i is the index of the bit after the end of the run. i = bs.nextClearBit(i); // nextClearBit never returns -1. // Clear the last bit of the run. bs.clear(i - 1); // 0000111100000... // ab // i starts off the loop at a, and ends the loop at b. // The mutations change the run to // 0001111000000... } }
这应该够了吧：
BitSet shifted = bs.get(1, bs.length());
它会给你一个等于orginial的bitset，但没有最低位。
编辑：
将此概括为n位，
BitSet shifted = bs.get(n, Math.max(n, bs.length()));
可能更有效的替代方案是使用底层的long []。
使用bitset.toLongArray()获取基础数据。 相应地移动那些长点，然后通过BitSet.valueOf(long[])创建一个新的BitSet你必须非常小心地移动底层长点，因为你必须取低位并将其转换为高位在arrays的下一个长。
这应该允许您使用处理器上的本机位移操作一次移动64位，而不是分别迭代每一位。
编辑：根据Louis Wasserman的评论。 这仅适用于Java 1.7 API。 当我写它的时候没有意识到。
请找到BitSet“左移”的代码块
/** * Shift the BitSet to left.
* For example : 0b10010 (=18) => 0b100100 (=36) (equivalent to multiplicate by 2) * @param bitSet * @return shifted bitSet */ public static BitSet leftShiftBitSet(BitSet bitSet) { final long maskOfCarry = 0x8000000000000000L; long[] aLong = bitSet.toLongArray(); boolean carry = false; for (int i = 0; i < aLong.length; ++i) { if (carry) { carry = ((aLong[i] & maskOfCarry) != 0); aLong[i] <<= 1; ++aLong[i]; } else { carry = ((aLong[i] & maskOfCarry) != 0); aLong[i] <<= 1; } } if (carry) { long[] tmp = new long[aLong.length + 1]; System.arraycopy(aLong, 0, tmp, 0, aLong.length); ++tmp[aLong.length]; aLong = tmp; } return BitSet.valueOf(aLong); }
这些函数分别模仿<<和>>>运算符。
/** * Shifts a BitSet n digits to the left. For example, 0b0110101 with n=2 becomes 0b10101. * * @param bits * @param n the shift distance. * @return */ public static BitSet shiftLeft(BitSet bits, int n) { if (n < 0) throw new IllegalArgumentException("'n' must be >= 0"); if (n >= 64) throw new IllegalArgumentException("'n' must be < 64"); long[] words = bits.toLongArray(); // Do the shift for (int i = 0; i < words.length - 1; i++) { words[i] >>>= n; // Shift current word words[i] |= words[i + 1] << (64 - n); // Do the carry } words[words.length - 1] >>>= n; // shift [words.length-1] separately, since no carry return BitSet.valueOf(words); } /** * Shifts a BitSet n digits to the right. For example, 0b0110101 with n=2 becomes 0b000110101. * * @param bits * @param n the shift distance. * @return */ public static BitSet shiftRight(BitSet bits, int n) { if (n < 0) throw new IllegalArgumentException("'n' must be >= 0"); if (n >= 64) throw new IllegalArgumentException("'n' must be < 64"); long[] words = bits.toLongArray(); // Expand array if there will be carry bits if (words[words.length - 1] >>> (64 - n) > 0) { long[] tmp = new long[words.length + 1]; System.arraycopy(words, 0, tmp, 0, words.length); words = tmp; } // Do the shift for (int i = words.length - 1; i > 0; i--) { words[i] <<= n; // Shift current word words[i] |= words[i - 1] >>> (64 - n); // Do the carry } words[0] <<= n; // shift [0] separately, since no carry return BitSet.valueOf(words); }
您可以使用BigInteger而不是BitSet 。 BigInteger已经有ShiftRight和ShiftLeft。
您可以查看BitSet toLongArray和valueOf(long[]) 。
基本上获取long数组，移位long s并从移位数组构造一个新的BitSet 。
为了获得更好的性能，您可以扩展java.util.BitSet实现并避免不必要的数组复制。 这是实现（我基本上重用了Jeff Piersol实现）：
package first.specific.structure; import java.lang.reflect.Field; import java.util.BitSet; public class BitSetMut extends BitSet { private long[] words; private static Field wordsField; static { try { wordsField = BitSet.class.getDeclaredField("words"); wordsField.setAccessible(true); } catch (NoSuchFieldException e) { throw new IllegalStateException(e); } } public BitSetMut(final int regLength) { super(regLength); try { words = (long[]) wordsField.get(this); } catch (IllegalAccessException e) { throw new IllegalStateException(e); } } public void shiftRight(int n) { if (n < 0) throw new IllegalArgumentException("'n' must be >= 0"); if (n >= 64) throw new IllegalArgumentException("'n' must be < 64"); if (words.length > 0) { ensureCapacity(n); // Do the shift for (int i = words.length - 1; i > 0; i--) { words[i] <<= n; // Shift current word words[i] |= words[i - 1] >>> (64 - n); // Do the carry } words[0] <<= n; // shift [0] separately, since no carry // recalculateWordInUse() is unnecessary } } private void ensureCapacity(final int n) { if (words[words.length - 1] >>> n > 0) { long[] tmp = new long[words.length + 3]; System.arraycopy(words, 0, tmp, 0, words.length); words = tmp; try { wordsField.set(this, tmp); } catch (IllegalAccessException e) { throw new IllegalStateException(e); } } } }
使用java SE8，它可以实现更简洁的方式：
BitSet b = new BitSet(); b.set(1, 3); BitSet shifted = BitSet.valueOf(Arrays.stream( b.toLongArray()).map(v -> v << 1).toArray());
我试图弄清楚如何使用LongBuffer来做到这一点，但还是没有完全发挥作用。 希望熟悉低级编程的人可以指出解决方案。
提前致谢！！！