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
    read is 17. This means that (when reading bytes in c), we first read
    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
    #1
    1. Advertising

  2. user923005 Guest

    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
    > read is 17. This means that (when reading bytes in c), we first read
    > 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
    #2
    1. Advertising

  3. Thad Smith Guest

    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
    >> read is 17. This means that (when reading bytes in c), we first read
    >> 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.

    --
    Thad
    Thad Smith, Apr 18, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page