# Fast bitwise algorithm

Discussion in 'C Programming' started by in_tyrannos@hotmail.com, Apr 17, 2007.

1. ### Guest

First, the file is read to the buffer. Now, I want to access this
buffer in the following way. Start index is defined as i =
j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
read from buffer is defined similarly. So basically, I want to read
sequence of bits from buffer at specified bit-location. Further, I
want to do this efficiently.

For example, start index is 13. The length of sequence of bits to be
two bytes to reach position 13 from positon 0. Sequence is now
obtained by reading 3 bits from second byte, then 16 bits (=two
bytes). From the last byte we read only 6 bits. Since c has only
limited number of primitive types, the question becomes: "How to do
this efficiently?" Of course, next the solution should be expandable
to such scheme, where the original is read continuosly to the buffer,
and bit-sequnces are also read continuosly (size of the buffer and
sequnce should be variables)...

Any ideas? Maybe something like this is done when writing file headers
or compressing files?

BR, J

, Apr 17, 2007

2. ### user923005Guest

On Apr 17, 9:17 am, wrote:
> First, the file is read to the buffer. Now, I want to access this
> buffer in the following way. Start index is defined as i =
> j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
> read from buffer is defined similarly. So basically, I want to read
> sequence of bits from buffer at specified bit-location. Further, I
> want to do this efficiently.
>
> For example, start index is 13. The length of sequence of bits to be
> two bytes to reach position 13 from positon 0. Sequence is now
> obtained by reading 3 bits from second byte, then 16 bits (=two
> bytes). From the last byte we read only 6 bits. Since c has only
> limited number of primitive types, the question becomes: "How to do
> this efficiently?" Of course, next the solution should be expandable
> to such scheme, where the original is read continuosly to the buffer,
> and bit-sequnces are also read continuosly (size of the buffer and
> sequnce should be variables)...
>
> Any ideas? Maybe something like this is done when writing file headers
> or compressing files?

It's a FAQ:

20.8: How can I implement sets or arrays of bits?

A: Use arrays of char or int, with a few macros to access the
desired bit at the proper index. Here are some simple macros to
use with arrays of char:

#include <limits.h> /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

(If you don't have <limits.h>, try using 8 for CHAR_BIT.)

References: H&S Sec. 7.6.7 pp. 211-216.

The C-FAQ book has a lot more detail.

user923005, Apr 17, 2007

user923005 wrote:
> On Apr 17, 9:17 am, wrote:
>> First, the file is read to the buffer. Now, I want to access this
>> buffer in the following way. Start index is defined as i =
>> j*size(byte) +k*size(bit) = j*8+k*1. The length of the sequence to be
>> read from buffer is defined similarly. So basically, I want to read
>> sequence of bits from buffer at specified bit-location. Further, I
>> want to do this efficiently.
>>
>> For example, start index is 13. The length of sequence of bits to be
>> two bytes to reach position 13 from positon 0. Sequence is now
>> obtained by reading 3 bits from second byte, then 16 bits (=two
>> bytes). From the last byte we read only 6 bits. Since c has only
>> limited number of primitive types, the question becomes: "How to do
>> this efficiently?" Of course, next the solution should be expandable
>> to such scheme, where the original is read continuosly to the buffer,
>> and bit-sequnces are also read continuosly (size of the buffer and
>> sequnce should be variables)...
>>
>> Any ideas? Maybe something like this is done when writing file headers
>> or compressing files?

>
> It's a FAQ:
>
> 20.8: How can I implement sets or arrays of bits?
>
> A: Use arrays of char or int, with a few macros to access the
> desired bit at the proper index. Here are some simple macros to
> use with arrays of char:
>
> #include <limits.h> /* for CHAR_BIT */
>
> #define BITMASK(b) (1 << ((b) % CHAR_BIT))
> #define BITSLOT(b) ((b) / CHAR_BIT)
> #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
> #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
>
> (If you don't have <limits.h>, try using 8 for CHAR_BIT.)

This works well for accessing single bits. For grabbing fields of bits
limited to a length of a built-in integer type, I would locate the first
byte, concatenate them into a large enough unsigned integer using shift
and bitwise-or,then shift and mask to align properly.

--