How can "x & y" be false when both x and y are true?

Question

Context:

I'm learning C# and have been messing about on the Pex for fun site. The site challenges you to re-implement a secret algorithm, by typing code into the site and examining how the inputs and outputs differ between your implementation and the secret implementation.

Problem:

Anyway, I got stuck on a basic code duel called XAndY.

From the name it seemed obvious that the answer was just:

public static bool Puzzle(bool x, bool y) 
{
    return x && y;
}

However, this was incorrect and Pex informed me that the following inputs produced a different result than the secret implementation:

Input:

x:true y:true (0x02)

Output:

my implementation: true (0x02)

secret implementation: false

Mismatch Your puzzle method produced the wrong result.

Code: Puzzle(true, PexSafeHelpers.ByteToBoolean((byte)2));

After a lot of confusion trying to compare different types of true, I realised that the implementation that Pex was looking for was actually just using a bitwise AND:

return x & y;

Questions:

I thought that for both semantic and short-circuiting reasons you should use logical && for comparing boolean values, but regardless:

1. Does this mean that x & y and x && y definitively do not have the same outputs for all possible bool arguments? (or could it be something buggy in Pex?)
2. Does this mean you can differentiate between different values of bool true in C#? If so, how?

Answer 1

The puzzle is exploiting what, in my opinion, is a bug in the C# compiler. (The bug affects VB.NET as well.)

In the C# 5.0 specification, §4.1.8 says that "The possible values of type bool are true and false", and §7.11.3 says that operator &(bool x, bool y) is a logical operator:

The result of x & y is true if both x and y are true. Otherwise, the result is false.

It's obviously a violation of the specification for true & true to yield false. What's going on?

At run time, a bool is represented by a 1-byte integer. The C# compiler uses 0 to represent false and 1 to represent true. To implement the & operator, the C# compiler emits a bitwise AND instruction in the generated IL. At first glance, this seems to be okay: bitwise AND operations involving 0 and 1 correspond exactly with logical AND operations involving false and true.

However, §III.1.1.2 of the CLI specification explicitly allows a bool to be represented by an integer other than 0 or 1:

A CLI Boolean type occupies 1 byte in memory. A bit pattern of all zeroes denotes a value of false. A bit pattern with any one or more bits set (analogous to a non-zero integer) denotes a value of true.

By going beyond the scope of C#, it is indeed possible—and perfectly legal—to create a bool whose value is, say, 2, thus causing & to behave unexpectedly. This is what the Pex site is doing.

Here's a demonstration:

using System;
using System.Reflection.Emit;

class Program
{
    static void Main()
    {
        DynamicMethod method =
            new DynamicMethod("ByteToBoolean", typeof(bool), new[] { typeof(byte) });
        ILGenerator il = method.GetILGenerator();
        il.Emit(OpCodes.Ldarg_0); // Load the byte argument...
        il.Emit(OpCodes.Ret);     // and "cast" it directly to bool.
        var byteToBoolean =
            (Func<byte, bool>)method.CreateDelegate(typeof(Func<byte, bool>));

        bool x = true;
        bool y = byteToBoolean(2);
        Console.WriteLine(x);               // True
        Console.WriteLine(y);               // True
        Console.WriteLine(x && y);          // True
        Console.WriteLine(x & y);           // False (!) because 1 & 2 == 0
        Console.WriteLine(y.Equals(false)); // False
        Console.WriteLine(y.Equals(true));  // False (!) because 2 != 1
    }
}

So the answers to your questions are:

1. Currently, it's possible for x & y and x && y to have different values. However, this behavior violates the C# specification.
2. Currently, you can use Boolean.Equals (as shown above) to differentiate between true values. However, this behavior violates the CLI specification of Boolean.Equals.

Answer 2

I noticed that this issue has been raised to the Roslyn compiler group. Further discussion.

It had the following resolution:

This is effectively by design and you can find the document detailing that here: https://github.com/dotnet/roslyn/blob/master/docs/compilers/Boolean%20Representation.md

You can see more details and past conversations about this here: #24652

The noted document states:

Representation of Boolean Values

The C# and VB compilers represent true (True) and false (False) bool (Boolean) values with the single byte values 1 and 0, respectively, and assume that any boolean values that they are working with are restricted to being represented by these two underlying values. The ECMA 335 CLI specification permits a "true" boolean value to be represented by any nonzero value. If you use boolean values that have an underlying representation other than 0 or 1, you can get unexpected results. This can occur in unsafe code in C#, or by interoperating with a language that permits other values. To avoid these unexpected results, it is the programmer's responsibility to normalize such incoming values.

(All italics are my own emphasis)

Answer 3

& in C# is not a bitwise operator, assuming that the input values are Boolean values. It is overloaded. There are two entirely separate implementations of the operator. A non-short circuiting logical boolean operator if the inputs are booleans, and a bitwise AND if the values are non-boolean values.

In the code that you have shown, then input is a boolean variable. It's not a numeric value, it's not an expression that resolves to a boolean value (which may have side effects), or anything else.

When the input is two boolean variables there is never going to be any different in the output between & and &&. The only way to have any observable difference between these two is to have a boolean expression that is more complex than just resolving a variable to its value, or some non-boolean input.

If the operands could be of some type other than bool then its pretty trivial to provide a type that has different results for either operator, such as a super mean type that overrides the true operator in a manor inconsistent with it's implicit conversion to bool:

Answer 4

Since the implementation to satisfy the puzzle is entirely up to you, why dont you try:

public static bool Puzzle(bool x, bool y)
{
    return x & !y;
}