Fast bit packing?

Hi everyone,

I am looking for a fast way to do bit packing in Matlab (my data set is pretty big). Here is what I mean by bit packing.

>> bits = [0 0 0 0 1 1 1 0]; % bits = vector of 1's or 0's.

I want each set of 4 bits got packed into a unsigned 4-bit integer, i.e.

>> x = [0 15];

bits(1) = most significant bit of the first integer bits(4) = least significant bit of the first integer

bits(5) = most significant bit of the second integer bits(8) = least significant bit of the second integer

Thanks

Answer 1

[Jan]

bits = [0 0 0 0 1 1 1 0];
factor = [8;4;2;1]; 
x = [bits(1:4) * factor, bits(5:8) * factor]

I assume, this is a very efficient task for a C-mex function, because the Matlab version creates large temporary arrays, if "bits" is large.

[Kevin]

Hi Jan & Walter,

Thanks the suggestion. I believe I have tried your algorithm (i.e. do element-by-element multiplication between the bit vector and a vector of power of 2). The problem is that this would fail if I want to pack 64 bits into an uint64. Sorry that I did not mention this in my first post.

For example,

bits = [0 0 0 0, 0 0 0 1, 0 1 0 1, 1 0 1 0, 1 1 0 0, ...

0 1 1 1, 0 1 0 1, 1 1 0 1, 0 0 1 0, 0 1 1 0, ...

1 1 0 1, 0 0 1 1, 0 0 1 1, 1 1 0 0, 1 1 1 1, 0 0 1 1];

After we use the algorithm to convert this into a uint64 number, type "format hex" to show the result in hex format. The result will not match the bits. I think we would run into precision problem (even with 64-bit double precision in Matlab).

Because of this, I end up using bitset() in a for-loop (which can be slow).

Just wondering if there is a Matlab function which already does bit packing very quickly. Or this is not possible in Matlab and so the only way is to write a C mex function myself.

Thanks

kevin

[Walter Roberson]

pack in to 8 or 16 or 32 bits, and typecast() in to 64 bits.

[Jan]

Andrei's "[8,4,2,1]*reshape(bits,4,[])" and Walter's "32bits and TYPECAST" are efficient. But bit-packing seems to be more straight in C, especially for large data.

[Walter Roberson]

If you are going to be packing in to 32 bits, you would reshape() to group 32 bits at a time, and you would use the appropriate list of powers of 2 depending on the bit order you wanted, with (e.g.)

P2 = 2.^(31:-1:0);

in your initialization and

typecast(uint32(P2*reshape(bits,32,[])),'uint64')

Unless, that is, some of the bits from the second group of 32 bits need to be mixed with the first group. If you do need that kind of mixing, reshape to columns of 64, index the resulting matrix at a permutation matrix, reshape to columns of 32, matrix multiply, uint32, typecast.

Answer 2

[Walter Roberson]

sum(bsxfun(@times,reshape(bits,4,[]),[8,4,2,1].'))

[Andrei Bobrov]

variant

[8,4,2,1]*reshape(bits,4,[])