1

I have the following two questions.

  1. I'm aware of the concept of a linked list. What is a linked list of intervals?

  2. I need to store a very huge (more than 100 bits) number in C/C++ and perform bitwise operations on it. Without using any big number library, what would be the best data structure to handle this scenario ?

Thank You

1
  • 1
    "linked list of intervals" Where did you come across this?
    – Lazer
    Aug 22, 2010 at 18:19

4 Answers 4

4
  1. The name doesn't ring any bells. If intervals are objects, then it's just a linked list that stores those objects. Perhaps you mean a skip list?
  2. If you're using C++, use a bitset. Otherwise, I would just use a classic table of four 32 bit ints.
5
  • Thanks for the reply. Can a bitset store 100,000 bits ?
    – James
    Aug 22, 2010 at 8:34
  • @James - it would depend on hardware too of course, but I would say yes, definitely. That's well under a megabyte of memory.
    – IVlad
    Aug 22, 2010 at 9:04
  • as much as I hate to suggest it, if the number of bits isn't known in advance, std::vector<bool> might actually be appropriate to use.
    – jalf
    Aug 22, 2010 at 11:53
  • @jalf: noway, vector<bool> having an actual use? Heresy.
    – Puppy
    Aug 26, 2010 at 14:26
  • @DeadMG: yeah, I know. If it was me, I'd probably prefer to use boost::dynamic_bitset instead, but I guess since they're not deprecating vector<bool> in C++0x, I can't really object if people choose to use it as a dynamic bitset
    – jalf
    Aug 26, 2010 at 19:02
0

If you want to write your own class to handle large bit numbers (I don't know why you would), you could wrap a vector. You'd have to catch your own overflow though. This is a huge pain, and I only bring it up because this was a final project for us for a C++ class I took, lol. I don't recommended this =P

0

I made a comment on this is another question, which was asked by someone else. This seems to be referring to my comment, so I'll explain what I meant. What I was suggesting was:

struct interval_node {
      int index;
      struct interval_node* next;
}

where index stores all the points where the bit "flips". This is a huge memory advantage if you have something like 11111111111100000000000, because it only needs to store the fact that the first bit is 1 (outside of the struct somewhere), as well as that the bit flips in the 12th index (being 0-based), rather than storing each individual bit itself. This can scale to 100,000 bits without eating up as much memory as long as the sequence doesn't have a ton of things like

1010101010101010101010101010101010101010101010

Because the it flips at every bit.

0

For the second part of the question, try std::bitset

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.