CODEWITHSUNDEEP
c#hammingweight
Ola Tuvesson
Ola Tuvesson

Reputation: 5221

Elegantly determine if more than one boolean is "true"

I have a set of five boolean values. If more than one of these are true I want to excecute a particular function. What is the most elegant way you can think of that would allow me to check this condition in a single if() statement? Target language is C# but I'm interested in solutions in other languages as well (as long as we're not talking about specific built-in functions).

One interesting option is to store the booleans in a byte, do a right shift and compare with the original byte. Something like if(myByte && (myByte >> 1)) But this would require converting the separate booleans to a byte (via a bitArray?) and that seems a bit (pun intended) clumsy... [edit]Sorry, that should have been if(myByte & (myByte - 1)) [/edit]

Note: This is of course very close to the classical "population count", "sideways addition" or "Hamming weight" programming problem - but not quite the same. I don't need to know how many of the bits are set, only if it is more than one. My hope is that there is a much simpler way to accomplish this.

Upvotes: 94

Views: 56811

Answers (24)

evorios
evorios

Reputation: 132

For four bools and less my solution may be applicated:

if ($"{b1}{b2}{b3}{b4}".Length % $"{false}".Length != 4)
{
  // then Throw...
}

Or more aggressive for any count of bools:

if ($"{b1}{b2}{b3}{b4}".Split($"{true}").Length > 1)
{
  // then Throw...
}

Upvotes: 0

Frederik Hoeft
Frederik Hoeft

Reputation: 1460

performance oriented solutions

As the following statements are true in .NET

  • sizeof(bool) == 1
  • *(byte*)&someBool == 1 where someBool is true
  • *(byte*)&someBool == 0 where someBool is false

you could fall back to unsafe code and pointer casting (as C# will not allow simply casting bool to byte or int).

Your code would then look something like this

if (*(byte*)&bool1 + *(byte*)&bool2 + *(byte*)&bool3 > 1)
{
    // do stuff
}

The benefit here would be that you don't have any additional branching making this one faster than the obvious myBool ? 1 : 0. The drawback here would be the usage of unsafe and pointers which often isn't a well received solution in the managed .NET world. Also the assumption that sizeof(bool) == 1 could be questioned as this doesn't apply to all languages but at least in C# .NET it holds true.

If the pointer stuff is too annoying for you, you could always hide it in an extension method:

using System.Runtime.CompilerServices;

// ...

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe int ToInt(this bool b) => *(byte*)&b;

your code would then turn into a more readable

if (bool1.ToInt() + bool2.ToInt() + bool3.ToInt() > 1)
{
    // do stuff
}

Obviously you could always combine this with LINQ as you please

if (myBools.Sum(b => b.ToInt()) > 1)
{
    // do stuff
}

or if you value performance over anything else this one's probably faster

bool[] myBools = ...

fixed (bool* boolPtr = myBools)
{
    byte* bytePtr = (byte*)boolPtr;
    int numberOfTrueBools = 0;

    // count all true booleans in the array
    for (int i = 0; i < myBools.Length; numberOfTrueBools += bytePtr[i], i++);

    // do something with your numberOfTrueBools ...
}

Or if you have a huge input array you could even go for a hardware accelerated SIMD solution ...

using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;

// ...

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
public static unsafe int CountTrueBytesSIMD(this bool[] myBools)
{
    // we need to get a pointer to the bool array to do our magic
    fixed (bool* ptr = myBools)
    {
        // reinterpret all booleans as bytes
        byte* bytePtr = (byte*)ptr;

        // calculate the number of 32 bit integers that would fit into the array
        int dwordLength = myBools.Length >> 2;
        
        // for SIMD, allocate a result vector
        Vector128<int> result = Vector128<int>.Zero;
        
        // loop variable
        int i = 0;
        
        // it could be that SSSE3 isn't supported...
        if (Ssse3.IsSupported)
        {
            // remember: we're assuming little endian!
            // we need this mask to convert the byte vectors to valid int vectors
            Vector128<int> cleanupMask = Vector128.Create(0x000000FF);
            
            // iterate over the array processing 16 bytes at once
            // TODO: you could even go to 32 byte chunks if AVX-2 is supported...
            for (; i < dwordLength - Vector128<int>.Count; i += Vector128<int>.Count)
            {
                // load 16 bools / bytes from memory
                Vector128<byte> v = Sse2.LoadVector128((byte*)((int*)bytePtr + i));

                // now count the number of "true" bytes in every 32 bit integers
                // 1. shift
                Vector128<int> v0 = v.As<byte, int>();
                Vector128<int> v1 = Sse2.ShiftRightLogical128BitLane(v, 1).As<byte, int>();
                Vector128<int> v2 = Sse2.ShiftRightLogical128BitLane(v, 2).As<byte, int>();
                Vector128<int> v3 = Sse2.ShiftRightLogical128BitLane(v, 3).As<byte, int>();

                // 2. cleanup invalid bytes
                v0 = Sse2.And(v0, cleanupMask);
                v1 = Sse2.And(v1, cleanupMask);
                v2 = Sse2.And(v2, cleanupMask);
                v3 = Sse2.And(v3, cleanupMask);

                // 3. add them together. We now have a vector of ints holding the number
                // of "true" booleans / 0x01 bytes in their 32 bit memory region
                Vector128<int> roundResult = Sse2.Add(Sse2.Add(Sse2.Add(v0, v1), v2), v3);

                // 4 now add everything to the result
                result = Sse2.Add(result, roundResult);
            }

            // reduce the result vector to a scalar by horizontally adding log_2(n) times
            // where n is the number of words in out vector
            result = Ssse3.HorizontalAdd(result, result);
            result = Ssse3.HorizontalAdd(result, result);
        }
        int totalNumberOfTrueBools = result.ToScalar();

        // now add all remaining booleans together 
        // (if the input array wasn't a multiple of 16 bytes or SSSE3 wasn't supported)
        i <<= 2;
        for (; i < myBools.Length; totalNumberOfTrueBools += bytePtr[i], i++);
        return totalNumberOfTrueBools;
    }
}

Upvotes: 0

Scott Aron Bloom
Scott Aron Bloom

Reputation: 271

I wanted to give a C++11 variadic template answer.

template< typename T>
T countBool(T v)
{
    return v;
}

template< typename T, typename... Args>
int countBool(T first, Args... args)
{
    int boolCount = 0;
    if ( first )
        boolCount++;
    boolCount += countBool( args... );
    return boolCount;
}

simply calling it as follows creates a rather elegant method of counting the number of bools.

if ( countBool( bool1, bool2, bool3 ) > 1 )
{
  ....
}

Upvotes: 1

Charles Bretana
Charles Bretana

Reputation: 146557

How about

  if ((bool1? 1:0) + (bool2? 1:0) + (bool3? 1:0) + 
      (bool4? 1:0) + (bool5? 1:0) > 1)
      // do something

or a generalized method would be... 

   public bool ExceedsThreshold(int threshold, IEnumerable<bool> bools)
    {
       int trueCnt = 0;
       foreach(bool b in bools)
          if (b && (++trueCnt > threshold)) 
              return true;
       return false;          
    }

or using LINQ as suggested by other answers:

    public bool ExceedsThreshold(int threshold, IEnumerable<bool> bools)
    { return bools.Count(b => b) > threshold; }

EDIT (to add Joel Coehoorn suggestion: (in .Net 2.x and later)

    public void ExceedsThreshold<T>(int threshold, 
                      Action<T> action, T parameter, 
                      IEnumerable<bool> bools)
    { if (ExceedsThreshold(threshold, bools)) action(parameter); }

or in .Net 3.5 and later:

    public void ExceedsThreshold(int threshold, 
            Action action, IEnumerable<bool> bools)
    { if (ExceedsThreshold(threshold, bools)) action(); }

or as an extension to IEnumerable<bool>

  public static class IEnumerableExtensions
  {
      public static bool ExceedsThreshold<T> 
         (this IEnumerable<bool> bools, int threshold)
      { return bools.Count(b => b) > threshold; }
  }

usage would then be:

  var bools = new [] {true, true, false, false, false, false, true};
  if (bools.ExceedsThreshold(3))
      // code to execute  ...

Upvotes: 100

dmoore1181
dmoore1181

Reputation: 2102

I was recently having this same issue, where I had three boolean values, which I needed to check that only 1 of them was true at a time. For this I used the xor operator as follows:

bool a = true;
bool b = true;
bool c = false;

if (a || b || c)
{
    if (a ^ b ^ c){
        //Throw Error
    }
}

This code will throw an error as a and b are both true.

For reference: http://www.dotnetperls.com/xor

I have only just found the xor operator in C# if anyone knows of any pit falls of this strategy, please let me know.

Upvotes: 0

finnw
finnw

Reputation: 48659

If your flags are packed into one word then Michael Burr's solution will work. However, the loop is not necessary:

int moreThanOneBitSet( unsigned int v)
{
    return (v & (v - 1)) != 0;
}

example

 v (binary) | v - 1 | v&(v-1) | result
------------+-------+---------+--------
       0000 |  1111 |    0000 |  false
       0001 |  0000 |    0000 |  false
       0010 |  0001 |    0000 |  false
       0011 |  0010 |    0010 |   true
       .... |  .... |    .... |   ....
       1000 |  0111 |    0000 |  false
       1001 |  1000 |    1000 |   true
       1010 |  1001 |    1000 |   true
       1011 |  1010 |    1010 |   true
       1100 |  1011 |    1000 |   true
       1101 |  1100 |    1100 |   true
       1110 |  1101 |    1100 |   true
       1111 |  1110 |    1110 |   true

Upvotes: 7

Ian Mercer
Ian Mercer

Reputation: 39277

If there were millions instead of just 5 you could avoid Count()and do this instead ...

public static bool MoreThanOne (IEnumerable<bool> booleans)
{
    return booleans.SkipWhile(b => !b).Skip(1).Any(b => b);
}

Upvotes: 6

Cameron MacFarland
Cameron MacFarland

Reputation: 71936

While I like LINQ, there are some holes in it, like this problem.

Doing a count is fine in general, but can become an issue when the items your counting take a while to calculate/retrieve.

The Any() extension method is fine if you just want to check for any, but if you want to check for at least there's no built in function that will do it and be lazy.

In the end, I wrote a function to return true if there are at least a certain number of items in the list.

public static bool AtLeast<T>(this IEnumerable<T> source, int number)
{
    if (source == null)
        throw new ArgumentNullException("source");

    int count = 0;
    using (IEnumerator<T> data = source.GetEnumerator())
        while (count < number && data.MoveNext())
        {
            count++;
        }
    return count == number;
}

To use:

var query = bools.Where(b => b).AtLeast(2);

This has the benefit of not needing to evaluate all the items before returning a result.

[Plug] My project, NExtension contains AtLeast, AtMost and overrides that allow you to mix in the predicate with the AtLeast/Most check. [/Plug]

Upvotes: 2

Michael Burr
Michael Burr

Reputation: 340426

You mentioned

One interesting option is to store the booleans in a byte, do a right shift and compare with the original byte. Something like if (myByte && (myByte >> 1))

I don't think that expression will give you the result you want (at least using C semantics, since the expression is not valid C#):

If (myByte == 0x08), then the expression will return true even though there's only one bit set.

If you meant "if (myByte & (myByte >> 1))" then if (myByte == 0x0a) the expression will return false even though there are 2 bits set.

But here are some techniques for counting the number of bits in a word:

Bit Twiddling Hacks - Counting bits

A variation you might consider is to use Kernighan's counting method, but bail out early since you only need to know if there's more than one bit set:

int moreThanOneBitSet( unsigned int v)
{
    unsigned int c; // c accumulates the total bits set in v

    for (c = 0; v && (c <= 1); c++)
    {
      v &= v - 1; // clear the least significant bit set
    }

    return (c > 1);
}

Of course, using a lookup table's not a bad option either.

Upvotes: 0

Partha Choudhury
Partha Choudhury

Reputation: 534

if((b1.CompareTo( false ) + b2.CompareTo( false ) + b3.CompareTo( false ) + ...) > 1)

// More than one of them are true

...

else

...

Upvotes: 0

Daniel Earwicker
Daniel Earwicker

Reputation: 116724

I was going to write the Linq version, but five or so people beat me to it. But I really like the params approach to avoid having to manually new up an array. So I think the best hybrid is, based on rp's answer with the body replace with the obvious Linqness:

public static int Truth(params bool[] booleans)
{
    return booleans.Count(b => b);
}

Beautifully clear to read, and to use:

if (Truth(m, n, o, p, q) > 2)

Upvotes: 126

Jens Wessling
Jens Wessling

Reputation:

If you only have five different values, you can easily do the test by packing the bits in to a short or an int and checking to see if it is any of the zero or one bit answers. The only invalid numbers you could get would be..

0x 0000 0000 
0x 0000 0001
0x 0000 0010
0x 0000 0100
0x 0000 1000
0x 0001 0000

This gives you six values to search for, put them in a lookup table and if it's not in there, you have your answer.

This gives you a simple answer.

   public static boolean moreThan1BitSet(int b)
   {
      final short multiBitLookup[] = { 
            1, 1, 1, 0, 1, 0, 0, 0,
            1, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            1, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0
      };
      if(multiBitLookup[b] == 1)
         return false;
      return true;
   }

This doesn't scale well past 8 bits, but you only have five.

Upvotes: 0

faulty
faulty

Reputation: 8347

if you mean more than or equal to one boolean equals to true, you could do it like

if (bool1 || bool2 || bool3 || bool4 || bool5)

If you need more than one (2 and above) booleans equal to true, you can try

int counter = 0;
if (bool1) counter++;
if (bool2) counter++;
if (bool3) counter++;
if (bool4) counter++;
if (bool5) counter++;
if (counter >= 2) //More than 1 boolean is true

Upvotes: 7

some
some

Reputation: 49632

Shorter and uglier than Vilx-s version:

if (((a||b||c)&&(d||e))||((a||d)&&(b||c||e))||(b&&c)) {}

Upvotes: 4

John Sonmez
John Sonmez

Reputation: 7206

I have a much much better one now and very short!

bool[] bools = { b1, b2, b3, b4, b5 };
if (bools.Where(x => x).Count() > 1)
{
   //do stuff
}

Upvotes: 1

Vilx-
Vilx-

Reputation: 107000

Not exactly pretty... but here's another way to do it:

if (
    (a && (b || c || d || e)) ||
    (b && (c || d || e)) ||
    (c && (d || e)) ||
    (d && e)
)

Upvotes: 1

Garry Shutler
Garry Shutler

Reputation: 32698

It's time for the obligatory LINQ answer, which in this case is actually quite neat.

var bools = new[] { true, true, false, false, false };

return bools.Count(b => b == true) > 1;

Upvotes: 25

Victor
Victor

Reputation: 4721

from the top of my head, a quick approach for this specific example; you could convert the bool to an int (0 or 1). then loop through therm and add them up. if the result >= 2 then you can execute your function.

Upvotes: 2

AndreasN
AndreasN

Reputation: 2897

if (NumberOfTrue(new List<bool> { bool1, bool2, bool3, bool4 }) >= 2)
{
    // do stuff
}

int NumberOfTrue(IEnumerable<bool> bools)
{
    return bools.Count(b => b);
}

Upvotes: 1

rp.
rp.

Reputation: 17683

I'd write a function to receive any number of boolean values. It would return the number of those values that are true. Check the result for the number of values you need to be positive to do something.

Work harder to make it clear, not clever! 

private int CountTrues( params bool[] booleans )
{
    int result = 0;
    foreach ( bool b in booleans )
    {
        if ( b ) result++;
    }

    return result;
}

Upvotes: 6

John Sonmez
John Sonmez

Reputation: 7206

I would do something like this, using the params argument.

        public void YourFunction()
        {
            if(AtLeast2AreTrue(b1, b2, b3, b4, b5))
            {
                // do stuff
            }
        }

        private bool AtLeast2AreTrue(params bool[] values)
        {
            int trueCount = 0;
            for(int index = 0; index < values.Length || trueCount >= 2; index++)
            {
                if(values[index])
                    trueCount++;
            }

            return trueCount > 2;

        }

Upvotes: 1

frankodwyer
frankodwyer

Reputation: 14048

Casting to ints and summing should work, but it's a bit ugly and in some languages may not be possible.

How about something like 

int count = (bool1? 1:0) + (bool2? 1:0) + (bool3? 1:0) + (bool4? 1:0) + (bool5? 1:0);

Or if you don't care about space, you could just precompute the truth table and use the bools as indices:

if (morethanone[bool1][bool2][bool3][bool4][bool5]) {
 ... do something ...
}

Upvotes: 1

Bork Blatt
Bork Blatt

Reputation: 3368

In most languages true is equivalent to a non-zero value while false is zero. I don't have exact syntax for you, but in pseudo code, what about:

if ((bool1 * 1) + (bool2 * 1) + (bool3 * 1) > 2)
{
    //statements here
}

Upvotes: 0

recursive
recursive

Reputation: 86134

I would just cast them to ints and sum.

Unless you're in a super tight inner loop, that has the benefit of being easy to understand.

Upvotes: 16

Related Questions