#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    4
    Rep Power
    0

    Deal with very large bit streams


    I want to scan a very large bit stream consisting of 1's and 0's only :)
    I have done it like this
    Code:
     
    
    A=(char *) malloc (l*(sizeof(char))); /* where,    10**4 < l < 10**9 */
    i have to perform certain operations like set, reset, print with the bit stream

    but it is going to be memory limit exceeded in submission :( , please help me to fix this problem.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,365
    Rep Power
    1870
    > i have to perform certain operations like set, reset, print with the bit stream
    Are you required to actually read in the whole stream, to provide random access to any bit to perform the operation?

    You could start by storing 8 bits in each byte, which will save nearly 90% of the memory you're currently trying to use.

    Comments on this post

    • shally agrees : thanks!!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    4
    Rep Power
    0
    Originally Posted by salem
    > i have to perform certain operations like set, reset, print with the bit stream
    Are you required to actually read in the whole stream, to provide random access to any bit to perform the operation?

    You could start by storing 8 bits in each byte, which will save nearly 90% of the memory you're currently trying to use.
    can you please tell me how to do this ? :confused: ?? for this bit stream
    Code:
    l=100
    0100000111010100110101100000001001011110001011111110010001111001010010101001010101011010000111100010
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    unsigned char pack(char s[8]) {
      unsigned char result = 0;
      int i;
      for (i = 0; (s[i]) && (i < 8); ++i)
        result = (result << 1) | ('1' == s[i]);
      return result;
    }
    
    int main() {
      puts("expect 0110 is 6");
      printf("%d\n", pack("0110"));
      return 0;
    }
    You probably don't need to write much code. The gnu multi-precision library probably supports, efficiently, all the bit manipulation operations you'll need.

    Comments on this post

    • shally agrees : Thanks!!
    Last edited by b49P23TIvg; November 10th, 2013 at 10:59 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,091
    Rep Power
    2222
    Originally Posted by shally
    can you please tell me how to do this ? :confused: ?? for this bit stream
    Code:
    l=100
    0100000111010100110101100000001001011110001011111110010001111001010010101001010101011010000111100010
    How are you reading in this bit stream? From a serial port? Through a UART or straight from a peripheral pin? If through a UART, then your program is getting that stream one byte at a time.

    Or is it a character string that you're reading from a disk file? Such that the actual bit pattern would be (in hex): 30313030303030313131303130 ... ? Then the mechanics would be that you would read a block of characters from disk into a buffer and then process the buffer one character at a time.

    If it's binary data that you're reading from a disk file, then the general mechanics would be the same as for character data.

    If you're basically writing a filter, then you don't need much storage, just enough to read in a grouping of bits, process them, and output them. Keep in mind that you can't read in any fewer than 8 bits at a time.
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,365
    Rep Power
    1870
    > can you please tell me how to do this ? ?? for this bit stream
    But you haven't actually told us what you need to do with the bit stream.

    If (for example), the point of the exercise is to flip every 4'th bit, then there's no need to store any of it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    4
    Rep Power
    0
    Originally Posted by salem
    > can you please tell me how to do this ? ?? for this bit stream
    But you haven't actually told us what you need to do with the bit stream.

    If (for example), the point of the exercise is to flip every 4'th bit, then there's no need to store any of it.
    sorry i was not mentioned the question...

    Actual question asked for reset,set and print the decimal value of bit stream for 64 bits from the index (corrosponding indices as input from user)
    eg
    r 31 (reset value at index 31)
    p 30 (print decimal vaue of 64 bit from index 30 in bit stream)
  14. #8
  15. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,365
    Rep Power
    1870
    So do you need to store any more than 64 bits at once?

    How do you step onto the next group of 64 bits?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo