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.