Przesuwanie zestawu bitów Java

Question

Używam java.util.BitSet do przechowywania gęstego wektora bitów.

Chcę zaimplementować operację, która przesuwa bity o 1, analogicznie do >>> na ints.

Czy istnieje funkcja biblioteki, która przesuwa BitSet s?

Jeśli nie, czy jest lepszy sposób niż poniższy?

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... 
    //  a b 
    // i starts off the loop at a, and ends the loop at b. 
    // The mutations change the run to 
    // 0001111000000... 
    } 
} 

Answer 1

To powinno załatwić sprawę:

BitSet shifted = bs.get(1, bs.length()); 

To da ci bitset równą orginial jeden, ale bez dolnej skrajnej bit.

EDIT:

Uogólniając to n bitów,

BitSet shifted = bs.get(n, Math.max(n, bs.length())); 

Answer 2

Alternatywą, która prawdopodobnie jest bardziej wydajna, byłoby pracować z długością [].

Użyj bitset.toLongArray(), aby uzyskać podstawowe dane. Zmodyfikuj odpowiednio te długie, a następnie utwórz nowy BitSet poprzez BitSet.valueOf(long[]) Musisz być bardzo ostrożny, przesuwając leżące poniżej długie, ponieważ będziesz musiał wziąć bit małego rzędu i przesunąć go do bitu wyższego rzędu na następny długi w tablicy .

Ten powinien pozwala użyć operacji przenoszenia bitów rodzimych na twoim procesorze, aby przesuwać 64 bity na raz, w przeciwieństwie do powtarzania każdego z nich osobno.

EDYCJA: Na podstawie komentarza Louisa Wassermana. Jest to dostępne tylko w języku Java 1.7 API. Nie zdawałem sobie z tego sprawy, kiedy to napisałem.

Answer 3

Można spojrzeć na BitSet toLongArray i valueOf(long[]).
Zasadniczo uzyskaj tablicę long, przesuń long s i skonstruuj nowy BitSet z przesuniętej tablicy.

Answer 4

proszę znaleźć ten blok kodu gdzie BitSet jest „przesunięty w lewo”

/** 
* Shift the BitSet to left.<br> 
* 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); 
} 

Answer 5

Funkcje te naśladować < < i >>> operatorów, odpowiednio.

/** 
* 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] >>> 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); 
} 

Answer 6

W celu osiągnięcia lepszej wydajności można rozszerzyć java.util.BitSet wdrażania i uniknąć niepotrzebnego kopiowanie tablicy. Oto realizacja (ja w zasadzie ponownego wykorzystania Jeff realizację 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); 
      } 
     } 
    } 
} 

Answer 7

Można użyć BigInteger zamiast BitSet. BigInteger ma już ShiftRight i ShiftLeft.

Answer 8

Java SE8, może być osiągnięte bardziej zwięzły sposób:

BitSet b = new BitSet(); 
b.set(1, 3); 
BitSet shifted = BitSet.valueOf(Arrays.stream(
     b.toLongArray()).map(v -> v << 1).toArray()); 

starałem się dowiedzieć, jak używać LongBuffer to zrobić, ale nie bardzo mam go do pracy. Miejmy nadzieję, że ktoś, kto zna programowanie na niskim poziomie, może wskazać rozwiązanie.

Z góry dziękuję !!!