2

I have a list of numbers encoded as a boost dynamic bitset. I dynamically choose the size of this bitset depending on the maximum value any number in this list can take. So let's say I have numbers from just 0 to 7, I only need three bits and my string 0,2,7 will be encoded as 000010111.

I now need to change say the 2nd number in this list (2) to another number, say 4. I thought the most efficient way to do this would be to represent 4 as a dynamic bitset of the same length as the list but with all other values set to 1, so 111111011. I would then bitshift this the required amount using with 1s used to fill in values to get 111011111, and then just bitwise AND this with the original bitset to get my desired result.

However, I cannot find a way to do these two things, as it seems with both initialisation of a bitset from an integer, and when bit shifting, the default and fill in values are always set to 0, not 1. How can I get around this problem, or achieve my goal in a different and efficient way.

Thanks

4 Answers 4

2

If that is really the implementation, the most general and efficient method I can think of would be to first mask off all the bits for the part you are replacing:

value &= 111000111;

Then "or" in the actual bits for that position:

value |= 000011000;

Hopefully someone here has a better trick for me to learn, but that's what I do.

2
  • I guess to create the &= mask I would first need to create the necessary amount of 1s, shift it, and then flip it. I'm starting to think it will may just be better to run a loop over the bitset.
    – zenna
    Mar 29, 2011 at 14:36
  • +1 Mask & shift is the way to go. XOR is more difficult to follow.
    – Engineer
    May 11, 2013 at 14:48
1

XOR the old value and the new value:

int valuetoset = oldvalue ^ newvalue;  // 4 XOR 2 in your example

Just shift the value you need to set:

int bitstoset = valuetoset << position; // (4 XOR 2) << 3 in your example

Then XOR again bitstoset with your bitset and that's it !

int result = bitstoset ^ bitset;
1
  • ! should be ~ here, shouldn't it?
    – AShelly
    Apr 6, 2011 at 19:21
0

Would you be able to use a vector of dynamic bitsets? Depending on your needs that might be sufficient and allow for easy updates.

Alternately fill your new bitset similiarly to how you proposed, but exactly inverted. Then right before you do the and at the end, flip all the bits.

1
  • no, I did first use a vector but they are too fat for my purposes.
    – zenna
    Mar 29, 2011 at 14:38
0

I guess your understanding of bitset is elementary wrong: set means it is NOT ordered, and the idea of a bitset is, that only one bit is necessary to show that the element is in-/outside the set. So your original set 0,2,7 would have 8 bits because 0..7 are 8 elements and NOT 3 * 3 (3 bits required to represent 0..7), and the bitmap would look like 10000101. What you describe is just a "packed" coding of the values. In your coding scheme 0,2,7 and 2,0,7 would coded completly different, but in a bitset they are the same.

In a (real) bitset (if that is what you want) you can then really easy "replace" elements by removing the old and adding the new. This happens as T.E.D. describes it.

To get the right mask you can easily use shift operations. So imagine you start counting by 0, you get the mask for value x by doing: 1<<x;

So you remove element x from the set by

value &= ~(1<<x);

and add another elemtn x (which might be the same) with

value | = 1<<x;

From you comment you misuse the bitset, so the masks must be build different (and you already had an almost right idea how to build them).

The command with bitmask for removal of element at position p:

value &= ~(111 p);

This 111 is for the above example where you need 3 bit for a position. If you dont want to hardcode it, you could for just take the next power of 2 and subtract 1 and then you got your only-1-string.

And to add you would just take your suggestest bitlist that contains only the new element and OR it to your bitlist:

value |= new_element_bitlist;
5
  • This is called a "bitmap", not a bitset. The packed encoding is more space-efficient when the set is extremely sparse, the bitmap is faster in most cases and more space-efficient for dense sets.
    – Ben Voigt
    Mar 29, 2011 at 14:56
  • All bitsets I know are implemented as bitmaps. Esp. the poster mentioned boost library does it this way. Maybe there are some exotic library which used bitset/bitmap not synonym and implement bitset as described, but I never head of anyone.
    – flolo
    Mar 29, 2011 at 15:04
  • Thanks. I know a fair amount about sets actually. You are right, I am not using a bitset as perhaps it is designed for. I am using a bitset for a very space efficient representation of a disjoint set (graph partition), using the position in the bitset as an element id, and its value as the set id. 0,1,0 would then for example denote three nodes with node 0 and node 1 in the same group
    – zenna
    Mar 29, 2011 at 15:08
  • Maybe I'm thinking of .NET's BitVector32 class, which actually is a packed encoding of bitfields. Of course, C and C++ has that functionality built-in, using bitfield syntax.
    – Ben Voigt
    Mar 29, 2011 at 15:18
  • @Zenna, Even if you misuse it the above bit shift approach should work. I edit the post to give you the right hints.
    – flolo
    Mar 29, 2011 at 15:29

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.