Converting from byte array to bitarray

Question

I'm learning c# and working with files and types. Problem is that I want to convert byte[] to BitArray, here's screenshot what I get:

enter image description here

On the left is my byte[] B and on the right is BitArray of it. What I want to achieve is BitArray to be 00001010 for byte[0] which is 10, 11001100 for byte1 which is 204 and so on.

I found that sentence " The Least Significant Bit of each byte represents the lowest index value." but I have no idea what it means and how to fix this.

Any ideas, source, info appreciated. I need it so much right now.

It looks like it worked perfectly. Byte 0 became bits 7:0, byte 1 became 15:8, and so on. Exactly what is your concern? — Ben Voigt, May 22 '15 at 19:44

score 3 · Accepted Answer · edited May 23 '17 at 11:51

The order of bits looks reversed, but once you realize that entries in bit array are numbered from least significant to most significant, it all makes sense:

00001010   Index Value
--------   ----- -----
||||||||
|||||||+----- 0  false
||||||+------ 1  true
|||||+------- 2  false
||||+-------- 3  true
|||+----------4  false
||+-----------5  false
|+------------6  false
+-------------7  false

If you would like to invert the order anyway, you can use one of the techniques described in this Q&A - for example, by using a lookup table:

private static byte[] Reverse = new byte[] {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8
,   0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC
,   0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA
,   0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE
,   0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9
,   0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD
,   0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB
,   0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

Now you can reverse bits in a byte simply by referencing Reverse[myByte].

Note : In case you are curious where did this "magic table" come from, here is the code that I used to generate it.

I'm not good at c or c++, those techniques are difficult for me, might be because I'm worked all day and my head is blowing, will check it tommorow, anyway thanks for help ;) — K V, May 22 '15 at 20:27
@GrandaS You are welcome. Please take a look at the edit - you can copy/paste the table into your code, and use it to look up the inverse of each byte (that's a C# version of the answer from the C++ Q&A). — Sergey Kalinichenko, May 22 '15 at 20:29
oh, I got it! thank you so much, you saved several hours of my worthless life! I would kiss you if I could :) — K V, May 22 '15 at 20:48

score 0 · Answer 2 · answered May 22 '15 at 19:44

0

Your bits are in opposite Endian order to what you're expecting. If you look at each eight bits they are the reverse of what you expected.

If really needed, you can reverse every eight bits.

answered May 22 '15 at 19:44

Steve Lillis

3,263
5
22
41

Thank you! I couldn't see that myself. Maybe you could help me with short code (function) how to achieve that reverse manually? – K V May 22 '15 at 19:51
My phone is playing up, but simply put iterate over the bitarray in steps of 8, working in reverse for 8 bits. Or iterate over the bitarray in steps of 1, copying the bits to a boolean array in reverse order. – Steve Lillis May 22 '15 at 19:55
I got the idea, but don't know how to do it right. I believe it's kind of magic that c# has, like linq or something. Anyway, big thanks for your help. – K V May 22 '15 at 20:04
What is it you need to do with these bits? Perhaps then I can give a more concrete description – Steve Lillis May 22 '15 at 20:06
It's huffman algorythm, I had byte[] which I encoded in bitarray and now I have to decode that. That's why the order must be the same as it was before. – K V May 22 '15 at 20:10
Ah I see! Funnily enough I was playing with Huffman coding recently. So you were expecting to do for int I = 0 ... ++I. Instead, do for int x = 7 ... x += 8, then nest for int y=7,y>=0,--y. Then get your expected bit as bitarray[x-y]. Then you'll be receiving them as expected – Steve Lillis May 22 '15 at 20:17
thanks, I'll keep in mind this idea too, I still want to be able to use foreach(bit in bits) and go through every bit without confusing indexes. – K V May 22 '15 at 20:23
Well just use the methodology I described and copy the boolean values into new list of booleans. Then instantiate a new bitarray from that list. Apologies for not being able to provide an example. If youre struggling I'll add one tomorrow – Steve Lillis May 22 '15 at 20:25
I am thinking about the same idea now, but i'm too tired to make it myself, but I'll give it a try tommorow, but would be nice to have an answer with code example, because one day someone might have a same problem too. :) – K V May 22 '15 at 20:30
I got the answer by using that lookup table, so it's not necessary to code it, unless you have a time and want to show good practise for me and others. thanks in advance :) – K V May 22 '15 at 20:53

atlaste · Answer 3 · 2015-05-22T21:00:31.080

Well one simple trick that you can use independent of little/big endian (explained on wikipedia) is to use the power of 'OR', 'AND', 'XOR' and 'SHIFT'.

 // initialized to 0
uint[] mask = new uint[(numberVals.Length + 31) / 32];

for (int i=0; i<numberVals.Length; ++i) 
    if (numberVals[i]) 
        mask[i/32] |= 1<<(i%32); // set bit with 'shift' and 'or'

Test for value id:

return mask[id/32] & (1<<(id%32))!=0;

If you want your bits the other way around, I'm sure you can do the math.

As for performance: not to worry, the modulo won't be a modulo if 32 is a constant; it'll be optimized by your JIT'ter. And if your JIT'ter is in a good mood, it'll do some other fancy things as well.

When do you need endianness

Basically if you're encounter things like 'network byte order' in protocols or when you're dealing with binary file formats. There are some other cases, but these are the most common IMO.

Bit magic

Swapping bits around can be a lot of fun. :-)

In all these cases assume you need a method like byte swaparound(byte i).

The most trivial way to do this is by using shifts.

return ((i & 0x80)>>7) | ((i & 0x40)>>5) | ((i & 0x20)>>3) | // ... boring

Well that was a lot of fun... Now let's make it cool, shall we?

A lookup table is often helpful for stuff like this. In this case a 256-byte lookup table will do the trick:

// initialize in static ctor
byte[] lookup = new byte[256];
for (int i=0; i<256; ++i) { lookup[i] = trivial_swaparound((byte)i); }

// use in swaparound
return lookup[b];

Another trick is to use a 64-bit integer temporary to do your magic. The easiest way to do this is by fanning out your bits to bytes in a temporary, and shifting it back into the world of a byte:

return ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

There are some alternatives to this, I'm pretty sure they can be found on the Bit Twiddling Hacks page.

I like your answer, but it's too difficult to understand for me, I've never worked with bytes, bits, shifts and other stuff, I'm glad, that I could understand (with help of guys here), that each byte in bitarray is reversed, now i only need a method to do that reverse of each 8 bits in bitarray. thank you for trying to help me :) — K V, May 22 '15 at 20:18

Converting from byte array to bitarray

3 Answers3