Wie verteilt man Bits in einem Byte?

Question

In Java, ich habe 2 Bytes:

byte b1 = (byte) 0b11111111, b2 = (byte) 0b00000000; 

Ich möchte sie mischen, so dass jedes erste Bit von b1 ist, während der andere von b2 ist (Lesen von links nach rechts). Die erste und die zweite Hälfte der Eingänge sind getrennt, so dass das Ergebnis 2 Bytes beträgt. Das Ergebnis b3 und b4 würde wie folgt aussehen.

byte b3 = (byte) 0b10101010, b4 = 0b10101010; 

Um darzustellen, wie die Bits eindeutig sind (einen Brief unter Verwendung der einzigartigen Bit angeben):

byte b1 = (byte) 0bHGFEDCBA, b2 = (byte) 0bPONMLKJI; 

Das Ergebnis wäre:

byte b3 = (byte) 0bHPGOFNEM, b4 = 0bDLCKBJAI; 

Oder grafisch,

+---+---+---+---+---+---+---+---+ 
b1 | H | G | F | E | D | C | B | A | 
    +---+---+---+---+---+---+---+---+ 
     | | | | | | | | 
     | | | | | | | +--------------------------------------------+ 
     | | | | | | +----------------------------------------+  | 
     | | | | | +------------------------------------+  |  | 
     | | | | +--------------------------------+  |  |  | 
     | | | +-------------------+    |  |  |  | 
     | | +---------------+  |    |  |  |  | 
     | +-----------+  |  |    |  |  |  | 
     +-------+  |  |  |    |  |  |  | 
       |  |  |  |    |  |  |  | 
      +---+---+---+---+---+---+---+---+  +---+---+---+---+---+---+---+---+ 
     b3 | H | P | G | O | F | N | E | M |  b4 | D | L | C | K | B | J | A | I | 
      +---+---+---+---+---+---+---+---+  +---+---+---+---+---+---+---+---+ 
        |  |  |  |    |  |  |  | 
     +-----------+  |  |  |    |  |  |  | 
     | +---------------+  |  |    |  |  |  | 
     | | +-------------------+  |    |  |  |  | 
     | | | +-----------------------+    |  |  |  | 
     | | | | +------------------------------------+  |  |  | 
     | | | | | +----------------------------------------+  |  | 
     | | | | | | +--------------------------------------------+  | 
     | | | | | | | +------------------------------------------------+ 
     | | | | | | | | 
    +---+---+---+---+---+---+---+---+ 
b2 | P | O | N | M | L | K | J | I | 
    +---+---+---+---+---+---+---+---+ 

Was wäre das Einfachen? Auf welche Weise könnte dies erreicht werden?

Answer 1

Wenn, wie Sie sagen, Sie hatten Ihr Herz auf einem Einzeiler, wie etwa:

public static int interleave(short b1, short b2) { 
    return((int)(((b2 * 0x0101010101010101L & 0x8040201008040201L) * 
     0x0102040810204081L >> 49) & 0x5555) | 
     (int)(((b1 * 0x0101010101010101L & 0x8040201008040201L) * 
     0x0102040810204081L >> 48) & 0xAAAA)); 
} 

Diese ein int mit b3 & b4 wie die unteren 16 Bits zurück, die Sie verschieben können und maskieren:

int b3b4 = interleave(b1, b2); 
int b3 = b3b4 >> 8; 
int b4 = b3b4 & 0b11111111; 

Algorithmus mit freundlicher Genehmigung von Interleave bits with 64-bit multiply

Answer 2

Zuerst wird ein Verfahren machen, die Bits in einem Byte ausbreitet, und gibt eine int mit den unteren 16 Bits zu den Bits des ursprünglichen Byte gesetzt:

static int spread(int b) { 
    int res = 0; 
    for (int i = 0 ; i != 8 ; i++) { 
     if ((b & 1<<i) != 0) { 
      res |= 1<<(2*i); 
     } 
    } 
    return res; 
} 

Mit dieser Methode in der Hand, erzeugt das Ergebnis durch das Ergebnis der ersten Ausbreitung mit dem Ergebnis der zweiten Ausbreitung OR-ing verschoben, indem man nach links über:

int res = spread(b1) | (spread(b2) << 1); 

Da Ihre Zahlen klein sind, Sie spread(x) für alle 256 Möglichkeiten precompute können.

Diese produces Morton's table. Kopieren Sie es in Ihrer Klasse, und machen Sie Ihre Lösung ein Einzeiler:

int res = morton[b1] | (morton[b2] << 1); 

// This declaration goes at the bottom of your file. 
// The numbers are copied from the program output at the link above: 
private static final short[] morton = new short[] { 
    0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 
    0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 
    0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 
    0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 
    0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 
    0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 
    0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 
    0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 
    0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 
    0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 
    0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 
    0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 
    0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 
    0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 
    0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 
    0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 
    0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 
    0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 
    0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 
    0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 
    0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 
    0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 
    0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 
    0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 
    0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 
    0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 
    0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 
    0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 
    0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 
    0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 
    0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 
    0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 
};