Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Fast bitwise algorithm

Reply
Thread Tools

Fast bitwise algorithm

 
 
in_tyrannos@hotmail.com
Guest
Posts: n/a
 
      04-17-2007
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

 
Reply With Quote
 
 
 
 
user923005
Guest
Posts: n/a
 
      04-17-2007
On Apr 17, 9:17 am, (E-Mail Removed) 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.

 
Reply With Quote
 
 
 
 
Thad Smith
Guest
Posts: n/a
 
      04-18-2007
user923005 wrote:
> On Apr 17, 9:17 am, (E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bitwise 2010 ( IIT Kharagpur ) An Annual Algorithm Intensive OnlinePrograming Contest Bitwise 2010 C Programming 1 01-31-2010 07:41 AM
Bitwise 2010 ( IIT Kharagpur ) An Annual Algorithm Intensive OnlinePrograming Contest Bitwise 2010 C++ 0 01-30-2010 09:32 PM
Bitwise 2K7 - An Algorithm Intensive Time Constrained Online Programming Competition. romram Java 1 01-24-2007 04:05 PM
Bitwise 2K7 - An Algorithm Intensive Time Constrained Online Programming Competition. Romram C Programming 0 01-24-2007 03:04 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM



Advertisments