Speicher int Wert von Bitmaske - Extrakt 1 bewertete Bits

Question

I am Berechnung des int Äquivalent eines gegebenen Satzes von Bits und Speichern, die im Speicher. Von dort würde Ich mag all 1-Wert-Bits aus dem ursprünglichen Bitmaske bestimmen. Beispiel:

33 -> [1,6]
97 -> [1,6,7]

Ideen für eine Implementierung in Java?

Answer 1

Auf BitSet

Verwenden Sie java.util.BitSet zu speichern, na ja, ein Satz von Bits.

Hier ist, wie man von einem int zu einem BitSet umwandeln kann, basierend auf welche Bits in der int eingestellt ist:

static BitSet fromInt(int num) {
    BitSet bs = new BitSet();
    for (int k = 0; k < Integer.SIZE; k++) {
        if (((num >> k) & 1) == 1) {
            bs.set(k);
        }
    }
    return bs;
}

So, jetzt können Sie die folgenden Aktionen ausführen:

System.out.println(fromInt(33)); // prints "{0, 5}"
System.out.println(fromInt(97)); // prints "{0, 5, 6}"

Und nur der Vollständigkeit halber, hier ist die Rücktransformation:

static int toInt(BitSet bs) {
    int num = 0;
    for (int k = -1; (k = bs.nextSetBit(k + 1)) != -1; ) {
        num |= (1 << k);
    }
    return num;
}

beide zusammen also komponieren, wir immer die Zahl wieder zurück:

System.out.println(toInt(fromInt(33))); // prints "33"
System.out.println(toInt(fromInt(97))); // prints "97"

---

Eine 0-basierte Indizierung

Beachten Sie, dass diese Verwendungen 0-basierte Indizierung, die die am häufigsten verwendeten Indizierung für Bits ist (und die meisten alles andere in Java). Das ist auch richtig. Im Folgenden ^ Bezeichnet Potenzierung:

33 = 2^0 + 2^5 = 1 + 32          97 = 2^0 + 2^5 + 2^6 = 1 + 32 + 64
33 -> {0, 5}                     97 -> {0, 5, 6}

Wenn Sie darauf bestehen, dass 1-basierte Indizierung, können Sie jedoch bs.set(k+1); und (1 << (k-1)) in dem oben genannten Schnipsel verwenden. Ich würde raten dringend diese Empfehlung jedoch.

Verwandte Fragen

• Was bedeutet der ^ Operator in Java tun ? - - es ist eigentlich nicht Potenzierung

Answer 2

Für Bit Fiedeln, hat java.lang.Integer einige sehr hilfreiche statische Methoden. Versuchen Sie diesen Code als Ausgangsbasis für Ihr Problem:

public int[] extractBitNumbers(int value) {
    // determine how many ones are in value
    int bitCount = Integer.bitCount(value);
    // allocate storage
    int[] oneBits = new int[bitCount];
    int putIndex = 0;
    // loop until no more bits are set
    while (value != 0) {
        // find the number of the lowest set bit
        int bitNo = Integer.numberOfTrailingZeros(value);
        // store the bit number in array
        oneBits[putIndex++] = bitNo+1; 
        // clear the bit we just processed from the value
        value &= ~(1 << bitNo);      
    }
    return oneBits;
}

Answer 3

Ich kann Ihnen C # -Implementierung zeigen, Java sollte sehr ähnlich sein.

int value = 33;
int index = 1;

while (value > 0)
{
   if ((value % 2) == 1)
      Console.WriteLine(index);

   index++;
   value /= 2;
}

Answer 4

Wenn Sie wollen, wie ein Array erhalten, dass Sie wahrscheinlich die Anzahl der Bits benötigen Sie eine Schleife überprüfen möchten & die ganze Zahl mit einem Bit 1 für jeden Schritt verschoben.

So etwas wie (pseudo):

Init array
mask = 1
for (0 to BitCount):
  if Integer & mask
    array[] = pos
  mask << 1

Answer 5

Ein bisschen-Knirschen Variation wäre so etwas wie:

int[] getBits(int value) {
  int bitValue = 1;
  int index = 1;
  int[] bits = new int[33];

  while (value >= bitValue)
  {
    bits[index++] = (value & bitValue);
    bitValue << 1; // or: bitValue *= 2;
  }
  return bits;
}

Beachten Sie, dass, da die Bits von 1 indiziert sind, wie Sie verlangten, bits[0] nicht verwendet wird.