Best way to check for the combination of 8 bools

I have 8 bools "1,2,3,5,6,7,8" that can be in any combination of true and false for a total of 256 combinations.

one of such combinations can be for example : 1T,2F,3T,4T,5T,6F,7F,8F

I will manually insert what each of these 256 combinations outputs, however my question is:

What is the best way to convert these 8 bools into a value that can be looked up with O(1) speed?

The obvious O(n) is a chain of 256 if elses, but is there a better way to express the combination of these 8 bools so I could use them maybe in a switch? I thought about translating it into a string such as "TTFTFFTF" and use it like this:

switch(combination)
case "TTFTFFTF": etc

But a string feels like a lot of overhead performance wise, is there a way to parse the combination into an int or byte that goes from 0-255, so 1T2T3F4F5T6T7T8F would be equal to 13(arbitrary example) and then I could use it as switch(byte)

Please let me know aswell if none of the implementations I proposed is correct and if there is a better method, Thanks!

 

Ummm. 8 bools? 256 combinatons? like... a Byte? Well, there is a much faster than o(1) method: have each represent a bit in a Byte, then use the reulting Byte an an index into an array that contains the method to invoke or similar

(and yes, that's an ugly hack, but the OP wasn't looking for Beauty ).

 

Usually you would use a bitmask, similar to how you work out the combinations in marching squares / marching cubes.

For in depth explanation on this see the "procedural cave" tutorial here on unity learn. Good luck.

 

Yep, I'd go with a byte/bitmask.

I'd probably even define it as an enum for easy naming too.

Like this example from MSDN (it even defines them in binary so you can see the flags easily... though I'm pretty sure that C# version specific):

Code (csharp):

1.  
2. [System.Flags]
3. public enum Days
4. {
5.      None      = 0b_0000_0000, // 0
6.      Sunday    = 0b_0000_0001, // 1
7.      Monday    = 0b_0000_0010, // 2
8.      Tuesday   = 0b_0000_0100, // 4
9.      Wednesday = 0b_0000_1000, // 8
10.      Thursday  = 0b_0001_0000, // 16
11.      Friday    = 0b_0010_0000, // 32
12.      Saturday  = 0b_0100_0000  // 64
13. }
14.  

https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/enumeration-types

You can check for any combination:

Code (csharp):

1.  
2. var value = Days.Monday | Days.Thursday;
3.  
4. switch(value)
5. {
6.     case Days.Monday | Days.Thursday:
7.         break;
8. }
9.  

You can also check if a specific bit in it is true or not:

Code (csharp):

1.  
2. if ((value & Days.Wednesday) != 0)
3. {
4.  
5. }
6.  

 

If I understood the OP correctly they want to be able to have different results for when e.g. the third and fourth bool are true, versus when the third is true, but the fourth is false, i.e. a full spread of 256 different cases. A bitmask will not help here.

A crude (but fast, since you only have 8 bools, if you have more, use an array and a shifter) to convert you specific problem to an int:

Code (CSharp):

1. // you have 8 bools, named one, two, … , eight
2. Int result = one.ToInt23() + two.ToInt32() * 2 + three.ToInt32() * 4 + four.ToUnt32() * 8 +
3.              five.ToInt32() * 16 + six.ToInt32() * 32 + seven.ToInt32 * 64 + eight.ToInt32() * 128;

You then can use the result integer as an index into your array of things to do with that combination.

Use an array of bool, a shifter and a Loop if you have a varying number of bools

 

I've edited my post to give examples.

 

Oh, I agree with your approach in general, that's how I would do it if the bools were independent. But in a degenerate case (say 100 or more different possible combinations) the OP ends up hand-coding 100 or more cases. This I understood to be the problem.

 

Ignore this, late to the punch and replies already explained what I was asking.

 

Totally agree there.

Not sure what exactly OP expects to be doing.

If it's selecting an object, it may be helpful to use value as an index in array as previously suggested.

But yeah... to settle the code smell would require more information from OP.

 

Thanks everyone for the replies

It's really just these 8 bools, non dynamic always 8 always true or false

Yes it really is 256 unique specific cases, I already have them hand coded =P, my issue is just with the performance of accessing them, well not having this:

if ( one == true && two ==false && three ==true && four == false && five = true && six == false && seven == true && eight == false){
}

x256........ which I already do have but I was looking to optimize

could someone give me a bit of insight on how an array of methods would work? Just used to arrays of primitives, variables, objects etc. Does it have to be initialized in runtime?

 

so I would have something like:

Code (CSharp):

1.  
2.  
3. public method[] combinations = new method[256];
4.  
5. public void TFTFTFTF{
6. //specific stuff
7. } /// etc....... x256
8.  
9. void awake{
10.  
11. method[ 1 + 0 * 2 + 1 * 4 + 0 * 8 +  1 * 16 + 0 * 32 +1 * 64 + 0 * 128] = TFTFTFTF;
12. //// etc....... x256
13.  
14. }
15.  
16. void CallMethod ( bool one, bool two, bool three, bool four, bool five, bool six, bool seven, bool eight ){
17.  
18. byte combo = one.ToInt23() + two.ToInt32() * 2 + three.ToInt32() * 4 + four.ToUnt32() * 8 + five.ToInt32() * 16 + six.ToInt32() * 32 + seven.ToInt32 * 64 + eight.ToInt32() * 128;
19.  
20.      combinations[combo](); // invoke method
21. }
22.  
23.  

Does this seem correct? Though I don't know the implementation for array of methods, this:

Code (CSharp):

1.  public method[]

probably is gibberish

 

That looks like you've got the right concept, but not the right syntax.

If you already have the 8 bools as separate variables and you need to convert them to a single integer (so you can use a switch statement or table look-up), I'd probably write something like this:

Code (CSharp):

1. int result = 0;
2. if (one) result += 1;
3. if (two) result += 2;
4. if (three) result += 4;
5. if (four) result += 8;
6. if (five) result += 16;
7. if (six) result += 32;
8. if (seven) result += 64;
9. if (eight) result += 128;

Optionally you can express those integer literals in some other form to make it more obvious that they are powers of 2.

If you had the bools in an array or list, you could collapse that code to a very short loop using bit-shifts.

Note that there's an arbitrary choice about whether the first boolean translates to the lowest bit or the highest bit; this difference is called endianness. It doesn't matter very much which you choose, but you need to be internally consistent, and if you ever need to interface with someone else's system you'll need to make sure you're compatible.



To create an array of "methods" look into delegates.

 

alright I'll check out the delegates thanks!

So for converting the bools its more efficient to use if sum than the .ToInt32()?

 

bools do not have methods called ToInt23() or ToInt32().

You might be thinking of Convert.ToInt32(bool). I don't know how that compares in efficiency to what I wrote, but I would guess there's very little difference. (It probably uses a conditional branch in its own implementation.) You could try it both ways and run performance tests if you want. I choose the style I did because I think it's more understandable, not for efficiency reasons.

You also could be thinking of BitConverter.ToInt32, but that works on an array of bytes, not bools.

 

I see, well determining the index won't be the bottleneck at any rate, thanks!

 

You might wanna look into all the bitwise operators, but that could be a handful.

 

I had the same issue and ended up using a Dictionary the left number is the “bit mask” the right number the result.

Code (CSharp):

1.     private static Dictionary<int,int> blendLut = new Dictionary<int,int>(){{21,26},{84,27},{81,28},{85,29},{74,30},{75,30},{78,30},{79,30},{91,30},{94,30},{1,15},{4,16},{16,17},{64,18},{5,19},{20,20},{80,21},{65,22},{17,23},{68,24},{69,25},{34,4},{35,4},{38,4},{39,4},{98,4},{99,4},{102,4},{103,4},{50,4},{51,4},{54,4},{55,4},{114,4},{115,4},{118,4},{119,4},{136,5},{140,5},{152,5},{156,5},{137,5},{141,5},{153,5},{157,5},{200,5},{204,5},{216,5},{220,5},{201,5},{205,5},{217,5},{221,5},{10,6},{11,6},{14,6},{15,6},{26,6},{27,6},{30,6},{31,6},{40,7},{44,7},{56,7},{60,7},{104,7},{108,7},{120,7},{124,7},{160,8},{161,8},{224,8},{225,8},{176,8},{177,8},{240,8},{241,8},{130,9},{134,9},{131,9},{135,9},{194,9},{198,9},{195,9},{199,9},{138,10},{139,10},{142,10},{154,10},{202,10},{143,10},{159,10},{207,10},{223,10},{222,10},{219,10},{203,10},{158,10},{218,10},{206,10},{155,10},{42,11},{43,11},{46,11},{58,11},{106,11},{47,11},{59,11},{107,11},{62,11},{110,11},{122,11},{63,11},{126,11},{111,11},{123,11},{127,11},{168,12},{169,12},{172,12},{184,12},{232,12},{173,12},{185,12},{233,12},{188,12},{2,0},{6,0},{3,0},{7,0},{8,1},{12,1},{24,1},{28,1},{32,2},{48,2},{96,2},{112,2},{128,3},{129,3},{192,3},{193,3},{236,12},{189,12},{237,12},{248,12},{249,12},{252,12},{253,12},{162,13},{163,13},{166,13},{178,13},{226,13},{167,13},{179,13},{227,13},{230,13},{183,13},{182,13},{247,13},{231,13},{243,13},{242,13},{246,13},{170,14},{171,14},{174,14},{186,14},{234,14},{175,14},{187,14},{235,14},{190,14},{238,14},{250,14},{191,14},{239,14},{255,14},{254,14},{251,14},{95,30},{41,31},{45,31},{57,31},{61,31},{105,31},{109,31},{121,31},{125,31},{164,32},{165,32},{228,32},{229,32},{180,32},{181,32},{244,32},{245,32},{146,33},{150,33},{147,33},{151,33},{210,33},{214,33},{211,33},{215,33},{18,34},{19,34},{22,34},{23,34},{66,35},{67,35},{70,35},{71,35},{72,36},{76,36},{88,36},{92,36},{9,37},{13,37},{25,37},{29,37},{33,38},{49,38},{97,38},{113,38},{36,39},{52,39},{100,39},{116,39},{132,40},{196,40},{133,40},{197,40},{144,41},{145,41},{208,41},{209,41},{0,42},{82,43},{83,43},{86,43},{87,43},{73,44},{77,44},{89,44},{93,44},{37,45},{53,45},{101,45},{117,45},{148,46},{149,46},{212,46},{213,46}};
2.  
3.  
4.         if(_dirX == -1)
5.         {
6.             int sum = 0;
7.             if((_map[_posX + _dirX,_posY + 1,_posZ - 1] != _emptyValue && _map[_posX + _dirX,_posY + 1,_posZ - 1] != _type) || (_map[_posX,_posY + 1,_posZ - 1] != _type  && _map[_posX,_posY + 1,_posZ - 1] != _emptyValue))
8.                 sum += 1;
9.             if((_map[_posX + _dirX,_posY + 1,_posZ] != _emptyValue && _map[_posX + _dirX,_posY + 1,_posZ] != _type) || (_map[_posX,_posY + 1,_posZ] != _type && _map[_posX,_posY + 1,_posZ] != _emptyValue))
10.                 sum += 2;
11.             if((_map[_posX + _dirX,_posY + 1,_posZ + 1] != _emptyValue && _map[_posX + _dirX,_posY + 1,_posZ + 1] != _type) || (_map[_posX,_posY + 1,_posZ + 1] != _type && _map[_posX,_posY + 1,_posZ + 1] != _emptyValue))
12.                 sum += 4;
13.             if((_map[_posX + _dirX,_posY,_posZ + 1] != _emptyValue && _map[_posX + _dirX,_posY,_posZ + 1] != _type)  || (_map[_posX,_posY,_posZ + 1] != _type && _map[_posX,_posY,_posZ + 1] != _emptyValue))
14.                 sum += 8;
15.             if((_map[_posX + _dirX,_posY - 1,_posZ + 1] != _emptyValue && _map[_posX + _dirX,_posY - 1,_posZ + 1] != _type) || (_map[_posX,_posY - 1,_posZ + 1] != _type && _map[_posX,_posY - 1,_posZ + 1] != _emptyValue))
16.                 sum += 16;
17.             if((_map[_posX + _dirX,_posY - 1,_posZ] != _emptyValue && _map[_posX + _dirX,_posY - 1,_posZ] != _type) || (_map[_posX,_posY - 1,_posZ] != _type && _map[_posX,_posY - 1,_posZ] != _emptyValue))
18.                 sum += 32;
19.             if((_map[_posX + _dirX,_posY - 1,_posZ - 1] != _emptyValue && _map[_posX + _dirX,_posY - 1,_posZ - 1] != _type) || (_map[_posX,_posY - 1,_posZ - 1] != _type && _map[_posX,_posY - 1,_posZ - 1] != _emptyValue))
20.                 sum += 64;
21.             if((_map[_posX + _dirX,_posY ,_posZ - 1] != _emptyValue && _map[_posX + _dirX,_posY ,_posZ - 1] != _type) || (_map[_posX,_posY,_posZ - 1] != _type && _map[_posX,_posY,_posZ - 1] != _emptyValue))
22.                 sum += 128;
23.             return sum;
24.         }
25.  

You can modify it for you needs it should contain all possibility's at least I did not run in to a error yet.

 

Indeed, silly me didn't check. The correct way to convert a bool to int in C# is using Convert.ToInt32(bool).

It's computationally much more efficient than an if clause - the Compiler does exactly nothing on Convert.ToInt32(bool): it simply keeps the value in the Register and now regards it as an int; while an if statement generates code and may in extreme cases even trigger a cache miss during execution.

But this is not where I would start optimization. For code readability I think your list of 'if (bool) result +=' is much better (understandable) than the rather cryptic chain of Conversions followed by multiplications that I suggested.

 

It was my understanding that in CLI, a boolean variable counts as "true" if it contains any bit pattern other than all zeroes. That seems to imply that reinterpreting the same bits as an int isn't guaranteed to produce the number 1 as a result.

 

It's technically correct that most compilers will generate code that interpret a non-zero value as true, and only zero as false. However, this is done only during testing a bool for true/false. Furthermore C# uses strict bools, and therefore the bools we are converting here were initialized to boolean values by code generated by the compiler. That code will not assign a random non-zero value as 'true', but always load the constant 0x1 into the register/memory location. The compiler-internal data structure will now show that this variable is to be interpreted as boolean, but this is only to enforce type safety. Temporarily re-Interpreting the variable's content as int will not generate any additinal code, and is safe ONLY because the compiler's code initialized the boolean variable. If the bolean was assigned via unsafe methods like typecasting a pointer, you are entirely correct. If it was initialized through a safe assignment of 'true' or 'false' or Convert(), it will be either set to 0x0 or 0x1. So, while technically interpreting (type-casting) a bool to int is dangerous, it's safe within the confines of C#, and the compiler knows this. That's the reason why the compiler can get away with a straight typecast.

 

Thanks everyone for the information!

Also I have another question, using this formula:

Code (CSharp):

1. int Index = Convert.ToByte(one) + Convert.ToByte(two) * 2 + Convert.ToByte(three) * 4 + Convert.ToByte(four) * 8 + Convert.ToByte(five) * 16 + Convert.ToByte(six) * 32 + Convert.ToByte(seven) * 64 + Convert.ToByte(eight) * 128;
2.  

could anyone tell me what is the formula to reverse engineer the index?

Say I know the index of the array is [0], how can i know the combination of bools it corresponds to?
with 0 its easy to know that it is 1F2F3F4F5F6F7F8F

but if the index is for example [53] how can I find the value of each bool?

essentially it would be solving the equation for each bool? like

Code (CSharp):

1. Convert.ToByte(one) = Index - Convert.ToByte(two) * 2 - Convert.ToByte(three) * 4 - Convert.ToByte(four) * 8 - Convert.ToByte(five) * 16 - Convert.ToByte(six) * 32 - Convert.ToByte(seven) * 64 - Convert.ToByte(eight) * 128;
2.  

Something to this effect?

 

You are missing some key concepts that would simplify your life greatly here.

First, why does bitmasking work as it does? As you may know, all data in a computer is represented in terms of binary digits. So the digit 53 actually exists as 00110101*, for example.

Bitmasking takes advantage of the fact that in binary, any given number is made up of what is essentially a unique sequence of on and off switches. In your use-case, you have 8 boolean values you want to keep track of. You can assign each boolean value an index inside of a single binary number:

Code (raw):

1. Number 0 0 1 1 0 1 0 1
2. Index  7 6 5 4 3 2 1 0

Notice that the indices increase from right to left, rather than from left to right. This is conventional, since the lowest bits in a number are on the right, the same way that the 3 is the lowest digit in the number 53.

So if your bitmask number is 53, and you examine the underlying bits, you would find that the values of your 8 booleans are encoded right in the number! You can see above that index 0, 2, 4, and 5 are on, whereas everything else is off. If you were to toggle 7, your new number would be 10110101, or 181.

Now that you know how bitmasking works in principle, how do you go from a bitmask to a boolean and back again? You want what is known as bitwise operations. When you do normal math operations, you are working with the numbers as a whole. Adding two numbers together:

Code (raw):

1.  53   00110101
2. +10  +00001010
3.  __   ________
4.  63   00111111

Bitwise operations don't operate on the number, but on the underlying bits that make up the number. There are several that are built in to C#. This article does a good job of introducing the various operators, so I won't explain them again here.

You already basically know how to write a value to a bitmask, but here's what it's doing under the covers:

Code (CSharp):

1. var number = 53;
2.  
3. // To set bit 7 to 1, we can add 128 to the number:
4. number += 128; // This is just an addition operation:
5.                     //   53   00110101
6.                     // +128  +10000000
7.                     //  ___   ________
8.                     //  181   10110101
9.  
10. // If you want to toggle a bit, you can XOR it:
11. number ^= 128;
12.  
13.  
14. number = 181; // 10110101
15. // If you want to unset a bit, you can AND an inverse:
16. number &= ~128; // The bit inverse of 128 is 01111111. We then AND it:
17.                     // 10110101
18.                     // 01111111 &
19.                     // __________
20.                     // 00110101

You can also be more explicit by using

( 1 << 7 )

to represent 128, if you wish. This can make it more clear that you are doing bitwise math, and make it more obvious what you're actually doing to the number.

In order to read the value at an index, you just need to isolate the bit at the index you want, and check if that bit is a 1 or a 0. Let's say you want to check if index 4 is a 1 or a 0 if your number is 53:

Code (CSharp):

1. var number = 53; // 00110101
2.  
3. var four = ( number >> 4 )        //  Shift the number right 4 indices: 00110101 -> 00000011 (bits "fall off" the right end of the number, and zeroes replace the leftmost bits)
4.                            & 1;   //  AND the result with the constant 1:
5.                                             00000011
6.                                             00000001 &
7.                                             __________
8.                                             00000001
9.  
10. // four is now an int that contains 1 if the bit is set, or 0 if it is not.
11. // You can turn this into a boolean simply by comparing it to 0 (or 1)
12.  
13. if( four != 0 ) {
14.     Debug.Log( "The fourth bit is set!" );
15. }

Bringing it all together, you have 8 booleans that you wish to represent as a unique bitmask, and then be able to convert the bitmask back to your 8 booleans. Hopefully now you see that this is a trivial task when thinking about numbers in terms of bits. For creating the bitmask, I personally prefer explicitly listing out the cases (as @Antistone demonstrated), as I think it's far more readable, and saves me a bunch of unnecessary function calls:

Code (CSharp):

1. var bitmask = 0;
2. if( one )   bitmask += 1;
3. if( two )   bitmask += 2;
4. if( three ) bitmask += 4;
5. if( four )  bitmask += 8;
6. if( five )  bitmask += 16;
7. if( six )   bitmask += 32;
8. if( seven ) bitmask += 64;
9. if( eight ) bitmask += 128;

You now have a unique value from 0 - 255 to feed into your array or whatever else you need it to do.

Splitting this back into eight booleans is just as easy:

Code (CSharp):

1. // bitwise operators have very low priority in expressions,
2. // so you will often need to put explicit parentheses
3. one   = ( bitmask >> 0 & 1 ) != 0;
4. two   = ( bitmask >> 1 & 1 ) != 0;
5. three = ( bitmask >> 2 & 1 ) != 0;
6. four  = ( bitmask >> 3 & 1 ) != 0;
7. five  = ( bitmask >> 4 & 1 ) != 0;
8. six   = ( bitmask >> 5 & 1 ) != 0;
9. seven = ( bitmask >> 6 & 1 ) != 0;
10. eight = ( bitmask >> 7 & 1 ) != 0;

You also have the option of dispensing with the explicit boolean fields entirely and using only the bit values. This is most likely how I would approach this problem, but either way works.

* There's an important note that integer values in C# are 32-bit, meaning that in reality, 53 would look like this in binary: 00000000 00000000 00000000 00110101. I'm displaying everything as an 8-bit number for brevity.

 

Thanks a lot for the very informative reply

 

C# has support for flags by default, using the FlagsAttribute on enumerations. You then can use HasFlag to check if a bit is set. Using Extension Methods (C# Programming Guide), you can write your own functions for setting and deleting a flag, which has been done countless times on the Internet. See Check Enum.HasFlag, why no Enum.SetFlag? on Stackoverflow for instance for a SetFlag extension method.

If your eight booleans represent options, that something is available, possible, then this is a highly readable solution for your problem. Additionally, you do not have to worry about shifting stuff yourself, since you can use extension methods, which greatly reduces human errors.