Reverse OR Algorithm?

[sachintha81]

Let me first describe my situation.

I have a list of Hex values, which are called BaseID. They are chosen such that logical OR between any number of them will give you a unique ID which is called FinalID. That is, my BaseID values are as follows.

BaseID = { 0x01, 0x02, 0x04, 0x08, 0x10, ... }

The critical point is that I don't know how many BaseIDs that I will have before I run the program (I do get a list of BaseIDs once I run the program as it is read from a file), or how many out of the total number of the BaseIDs will be used to create the FinalID. It is decided based upon other parts of my program. For example, following are two FinalIDs that I might have in my program.

FinalID = ( 0x01 | 0x04 ) = 0x05

FinalID = ( 0x02 | 0x04 | 0x10 ) = 0x16

Now, using OR operation for any number of BaseIDs is the easy part. My problem is, I need to extract from FinalID the BaseIDs used to create that FinalID. Since I've chosen BaseIDs such that they, once the OR operation is used, will ALWAYS give me a unique FinalID, I know that any given FinalID is created using a specific set of BaseIDs. Note that a FinalID can be created using only one BaseID too which is the equivalent of FinalID = ( BaseID | 0x00 ).

I know what I have to do to extract the BaseIDs used to create any particular FinalID; I have to get the complete list of BaseIDs involved, then use OR operator among each and every comibnation of elements to find out if which combination gives the particular FinalID.

However I'm finding it hard to convert this logic into a program. I am using C# with .NET 3.5 Framework. Any suggestions/ideas would be very much appreciated. A code sample is highly appreciated.

Thanks in advance!

[arunkumars]

sachintha,
here you ll have to atleast paste a pseudocode of what your idea is, though the explanation is clear.

Well, you cannot guess the finalId from the baseId like the way you have proposed, u might get a huge combination of probable values and u might have to lose more time in searching through all the list of possible baseIds,
1 thing i can suggest is, if you are the one who is writing into a file those baseIds, follow a seperate data structure which can keep a track of those baseId to get a final Id.

[Momerath]

Given a list of BaseIDs and a FinalID, generating all possible combinations to determine which BaseIDs are used in that FinalID is the hard way to go about it. Iterate through the list of BaseIDs. For each one, AND it against the FinalID and if the result of the AND is equal to the BaseID, then it was used to generate that particular FinalID.

[VIeditorlover]

Generally, you are working with data type set. So use C#/.NET native approach and instead of assembler's save-any-single-byte programming style just add values into list and use built-in functions. Life is much easier if you think in .NET this way.

[skatamatic]

Sorry if this doesn't help solve the problem, but why exactly are you using this ID schema?

[sachintha81]

sachintha,
here you ll have to atleast paste a pseudocode of what your idea is, though the explanation is clear.

Well, you cannot guess the finalId from the baseId like the way you have proposed, u might get a huge combination of probable values and u might have to lose more time in searching through all the list of possible baseIds,
1 thing i can suggest is, if you are the one who is writing into a file those baseIds, follow a seperate data structure which can keep a track of those baseId to get a final Id.

Arun, thanks. But I am not at my liberty to use data structures to keep track of the base IDs. They need to be a simple list in a file where I read from.

[sachintha81]

Given a list of BaseIDs and a FinalID, generating all possible combinations to determine which BaseIDs are used in that FinalID is the hard way to go about it. Iterate through the list of BaseIDs. For each one, AND it against the FinalID and if the result of the AND is equal to the BaseID, then it was used to generate that particular FinalID.

Momerath, this looks like a good suggestion. Let me see if it works and tell you. Thanks!

[sachintha81]

Generally, you are working with data type set. So use C#/.NET native approach and instead of assembler's save-any-single-byte programming style just add values into list and use built-in functions. Life is much easier if you think in .NET this way.

I'm sorry mate but I didn't understand this bit.

[sachintha81]

Sorry if this doesn't help solve the problem, but why exactly are you using this ID schema?

It's hard to explain why since I have to explain pretty much a huge part of my program. Which I'm not allowed to do in the first place.

The simplest explanation is, the total number of BaseIDs as well as the combination of them used in any given instance is determined at runtime.

[sachintha81]

Given a list of BaseIDs and a FinalID, generating all possible combinations to determine which BaseIDs are used in that FinalID is the hard way to go about it. Iterate through the list of BaseIDs. For each one, AND it against the FinalID and if the result of the AND is equal to the BaseID, then it was used to generate that particular FinalID.

Momerath, I tried it and it worked like a charm. Thanks, it's such a simple yet elegant solution.