Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bit Strings: checking if one bitstring is a subset of another

I am representing the set of english alphabets as a 26 bit bitstring. The first bit corresponds to 'a', the set bit to 'b', and so on. Thus,
The string ab is represented as 11000000000000000000000000
Now, given two bit strings, I want to check if bitstring 1 is a subset of bitstring 2. That is, in all places bitstring 1 has a '1', bit string 2 should also have a '1'. This means that all characters in string1 are also present in string2. Can somebody please let me know the best way to do this?
I know a simple way as follows: iterate through bit string1 and check the corresponding bit in bit string2. However, I am wondering if this can be done using some bit wise operator in a more efficient manner

like image 656
TimeToCodeTheRoad Avatar asked Sep 11 '12 07:09

TimeToCodeTheRoad


1 Answers

If you really are using only 26 bits, you can use an integer (32 bits) to represent the bitset, and use the bitwise AND (&) operator, to get the intersection of the two sets.

If a & b == a, a is a subset of b

like image 84
amit Avatar answered Oct 15 '22 00:10

amit