binary integer logic

[p_eqlz_np]

I have a question I am hoping someone here can help me with. let's say we have a bunch of atomic groups (cannot be broken down further), i will give each of them a bit mask. we also have a bunch of users, and each one has a binary value that tells us which atomic groups the user is in. Example:

Groups
G1 - 00001 - (1)
G2 - 00010 - (2)
G3 - 00100 - (4)
G4 - 01000 - ( 8 )
G5 - 10000 - (16)

Users
U1 - 00011 - User is in groups 1 and 2
U2 - 01100 - in groups 3 and 4
U3 - 00010 - in group 2
U4 - 10000 - in group 5
U5 - 01011 - in groups 1, 2, 4

Now we also have groups of groups which are composed of some basic formula. For Example:

Groups of Groups
GG1 - (G1 && G2) || G3
GG2 - (G2 || G3) && (G1 && G4)
GG3 - (G1 && (G2 || G3)) || G5

Now I want to be able to determine all the users that satisfy the conditions for GG1, GG2 and GG3. So based on the above examples, we have:

Users in GG1: U1, U2, U5
Users in GG2: U5
Users in GG3: U1, U4, U5

How can I algorithmically determine this? The groups, users and groups of groups are stored as you see above. Given a user's binary value I need to be able to "plug" it into the GG formula and determine if it is true or not. Do I have to break apart the GG formulas and dynamically map them into if statements? I am hoping for an easier way since they could possibly get complicated.

Thanks for any help.

[Rashakil Fol]

You can make a mask representing what users are in each group: for example, for G1, that would be 10001, for G2, that would be 10101, and so on. Then combine these masks using regular bitwise operations.

[p_eqlz_np]

I'm not sure I understand what you mean. So in addition to the group's mask, I have another binary value that represents which users are in the group? And then what will I get by combining them?

Keep in mind that I should be able to have hundreds of groups and groups of groups, and thousands of users so I need to be able to store these large values and do operations on them without much of a problem. If I have a thousand users, that's a thousand bit integer right there.

[WaltP]

If these are actual formulas:

Groups of Groups
GG1 - (G1 && G2) || G3
GG2 - (G2 || G3) && (G1 && G4)
GG3 - (G1 && (G2 || G3)) || G5

then
GG1 = G3
GG2 = 0
GG3 = G5

Now I want to be able to determine all the users that satisfy the conditions for GG1, GG2 and GG3. So based on the above examples, we have:

Users in GG1: U1, U2, U5
Users in GG2: U5
Users in GG3: U1, U4, U5

How can I algorithmically determine this?

AND the user with the GGroup. If != 0, user is in the group.

[p_eqlz_np]

If these are actual formulas:
then
GG1 = G3
GG2 = 0
GG3 = G5

AND the user with the GGroup. If != 0, user is in the group.

Sorry, I guess I wasn't clear. You can't just simplify the GG "formulas" like that, they are not actually formulas.

GG1 - (G1 && G2) || G3

Note that the && and || are NOT bit operators.. they are the logical and/or operators. So for example, GG1 contains ALL users that are in BOTH G1 and G2, OR just in G3. So in the end it comes down to true/false. Like U1 who is in G1 and G2, the above "formula" would be

((T && T) || F) which is of course T

[iamthwee]

That makes no sense. :sad:

[p_eqlz_np]

no reason to be sad! i'm terrible at explaining things. i would be the worst teacher in the world.. hehe..

anyway maybe this will help, if you put the GG rules into words.

So first I said GG1 = (G1 AND G2) OR G3. sorry for making it so formula-ish even though its not really one.

in words: the users in GG1 are those that are either BOTH in G1 and G2 OR just in G3.

so if U1 is in (G1,G2) and U2 is in (G3), both U1 and U2 would be part of GG1. hope i am making sense now

[iamthwee]

no reason to be sad! i'm terrible at explaining things. i would be the worst teacher in the world.. hehe..

anyway maybe this will help, if you put the GG rules into words.

So first I said GG1 = (G1 AND G2) OR G3. sorry for making it so formula-ish even though its not really one.

in words: the users in GG1 are those that are either BOTH in G1 and G2 OR just in G3.

so if U1 is in (G1,G2) and U2 is in (G3), both U1 and U2 would be part of GG1. hope i am making sense now

Ok that still don't make any sense.

Ok let's keep it simple. Let's say you have some variables G1,G2,G3...GN. These variables (GN) can take two forms, 0 or 1 true or false.

So essentially you are saying:

Giving various boolean formulas:

(G1 && G2) || G3 
(G2 || G3) && (G1 && G4) 
(G1 && (G2 || G3)) || G5

Determine the final result, i.e it would each expression be either be true or false?

And you want a way to code the expressions dynamically (like say at the command line) rather than having to list a whole bunch of if / and conditions?

[p_eqlz_np]

Ok that still don't make any sense.

Ok let's keep it simple. Let's say you have some variables G1,G2,G3...GN. These variables (GN) can take two forms, 0 or 1 true or false.

So essentially you are saying:

Giving various boolean formulas:

(G1 && G2) || G3 
(G2 || G3) && (G1 && G4) 
(G1 && (G2 || G3)) || G5

Determine the final result, i.e it would each expression be either be true or false?

And you want a way to code the expressions dynamically (like say at the command line) rather than having to list a whole bunch of if / and conditions?

ah.. so the variables (G1..Gn) as you said are more than just true/false. they are bit masks.. so the masks are:
G1: 0001
G2: 0010
G3: 0100
G4: 1000

and then given a user's mask (ie 0110, which states that the user is in G2 and G3 by ANDing against the G2 and G3 bit masks), then yes, i want to determine the final result (true/false) of the expressions. and by dynamically, i mean these expressions are not hard coded anywhere. they are stored somewhere of course, but not in the actual code. given a user's mask and the expression i should be able to call some function which will return true or false.

[iamthwee]

ah.. so the variables (G1..Gn) as you said are more than just true/false. they are bit masks.. so the masks are:
G1: 0001
G2: 0010
G3: 0100
G4: 1000

and then given a user's mask (ie 0110, which states that the user is in G2 and G3 by ANDing against the G2 and G3 bit masks), then yes, i want to determine the final result (true/false) of the expressions. and by dynamically, i mean these expressions are not hard coded anywhere. they are stored somewhere of course, but not in the actual code. given a user's mask and the expression i should be able to call some function which will return true or false.

I'm still struggling to understand, maybe it's just me, but your first example is throwing me of.

Anyway, regardless of GN being just 0 or 1 or a string of zeros and ones, the idea should still be the same.

What you have to do is create an equation parser to handle any type expression. So that your program can handle it rather than just hard coded expressions.

[p_eqlz_np]

oh well, sorry for the confusion. thanks for the help though.

[iamthwee]

oh well, sorry for the confusion. thanks for the help though.

So do you know how to write an equation parser?

[WaltP]

I'm still struggling to understand, maybe it's just me, but your first example is throwing me of.

Look at it this way: (G1 && G2) || G3

You are looking for students in
1) Math-202 (G3) --OR--
2) CompSci-101 (G1) AND Economics-101 (G2)

Using language syntax makes the statement backwards. Use logic syntax like you did later with (G1 AND G2) OR G3. This takes it out ot the boolean syntax -- at least for me.

[Rashakil Fol]

WaltP, if group X is assigned the user mask 1000101, that means that user 1, 3, and 7 are members of group X.

Suppose group X has users 1,3,7, group Y has users 2,4,7, and group Z has users 3, 5. Then the user masks for X, Y, and Z are 1000101, 1001010, and 0010100, respectively.

Suppose group GGK consists of people who are either in X and Y, or are in group Z. Describing GGK the way you have been, you'd say (X && Y) || Z.

Then compute (X & Y) | Z (where these bitwise operators are taken from C and other languages). Well, the value X & Y contains all the users in groups X and Y: X & Y equals 1000000, after all. Then (X&Y)|Z equals 1010100. So users 7, 5, and 3 are members of the group GGK.

If you had a group and wanted to implement a way of combining groups and then to test arbitrary users to see if they're in the group, the strategy for implementation would depend on the programming language you're using. It would be easier in functional programming languages.

[p_eqlz_np]

So do you know how to write an equation parser?

iamthwee, i have not written one before but i have spent my weekend so far writing one and i have actually enjoyed it so far (yes i am a big geek). i like learning new stuff like this.. i was surprised to see how easy it was to get a syntax checker working once you have a context free grammar defined using a recursive descent technique (of course with plenty of help from sites on these topics). thanks for pointing me in this direction. anyway i am now working on the parser using the shunting yard algorithm to convert the expression into reverse polish notation and then finally evaluating it. currently im writing it in perl but if its not fast enough for my needs i will probably port it into C. fun stuff.. :cheesy:

[p_eqlz_np]

WaltP, if group X is assigned the user mask 1000101, that means that user 1, 3, and 7 are members of group X.

Suppose group X has users 1,3,7, group Y has users 2,4,7, and group Z has users 3, 5. Then the user masks for X, Y, and Z are 1000101, 1001010, and 0010100, respectively.

Suppose group GGK consists of people who are either in X and Y, or are in group Z. Describing GGK the way you have been, you'd say (X && Y) || Z.

Then compute (X & Y) | Z (where these bitwise operators are taken from C and other languages). Well, the value X & Y contains all the users in groups X and Y: X & Y equals 1000000, after all. Then (X&Y)|Z equals 1010100. So users 7, 5, and 3 are members of the group GGK.

If you had a group and wanted to implement a way of combining groups and then to test arbitrary users to see if they're in the group, the strategy for implementation would depend on the programming language you're using. It would be easier in functional programming languages.

i had thought about this implementation, and i didnt think it was feasible. keeping the group's user masks updated and current involves too much work. every time a user is added/deleted for example, i would have to go through and change each and every group-user mask.. right?

[iamthwee]

i had thought about this implementation, and i didnt think it was feasible. keeping the group's user masks updated and current involves too much work. every time a user is added/deleted for example, i would have to go through and change each and every group-user mask.. right?

Nah, his example at least makes sense. What's so hard about updating the group's user masks.

Group X = 100100

User 2 decides to join Group X.

Group X = 100110

[p_eqlz_np]

Nah, his example at least makes sense. What's so hard about updating the group's user masks.

Group X = 100100

User 2 decides to join Group X.

Group X = 100110

no.. what i meant was this: let's say there are 1000 groups and that user 3 is in all 1000 groups. now, when user 3 is deleted from the system, i'm gonna have to update all 1000 group-user masks since that bit position will be assigned to some other user now.

[Rashakil Fol]

That's not bad at all. You'd have to store user 3's membership information for each of the 1000 groups anyway, and you'd have to delete that anyway, so this is a linear multiple of the amount of work you'd have to do.

And if by 1000 groups you're including compound groups, then don't store the masks for every user for compound groups; just calculate them user-by-user whenever you need to know all the users that are members.