Bitwise logic checking?

Question

I'm messing around with bitwise operations and wanted to implement the simple logic puzzle where you have a fox(wolf), chicken(goose), grain(corn) and a person trying to cross a river. I'm using the first 4 bits for each one to represent which side of the river they are on.

I'm having a little bit of trouble trying to implement the logic.

How can I check if the two bits are either 1 or 0 but not 1 and 0?

int game()
{
    int state = 0;
    int done = 0;
    while (!done)
    {
        int input = 0;
        input = move();

        /*
           0000 0000
                |||\_grain
                ||\__chicken
                |\___fox
                \____person
           0 = left side of the river
           1 = right side
        */
        if (input == 3)// Moves person and grain
        {
            // Move the grain if the person is on the same side.
            if (!(state & 1 << 3 ^ state & 1<< 0))
            {
                state ^= 1 << 3;
                state ^= 1 << 0;
            }
            else
            {
                // Always switch the person no matter what
                state ^= 1 << 3;
            }
        }
        else if (input == 2) // Moves person and chicken
        {
            // Move Chicken only if person is on the same side
            if (!(state & 1 << 3 ^ state & 1<< 1))
            {
                state ^= 1 << 3;
                state ^= 1 << 1;
            }
            else
            {
                // Always switch the person no matter what
                state ^= 1 << 3;
            }
        }
        else if (input == 1)// Moves person and fox
        {
            // Move the fox if the person is on the same side.
            if (!(state & 1 << 3 ^ state & 1<< 2))
            {
                state ^= 1 << 3;
                state ^= 1 << 2;
            }
            else
            {
                // Always switch the person no matter what
                state ^= 1 << 3;
            }
        }

        // Fox and Chicken on one side and person on the other = lost
        if ((state & 1 << 2 && state & 1 << 1) && ~(state & 1 << 3))
        {
            printf("Failed\n");
        }
    }
    return 1;
}

I'm guessing bitwise checking would be more elegant code but it seems like it's more of a pain. I always end up doing this when I get sick of hitting my head against the wall with bitwise logic.

int game()
{
    int state = 0;
    int done = 0;
    while (!done)
    {
        int input = 0;
        input = move();

        /*
           0000 0000
                   | | | \_grain
                   | | \__chicken
                   | \___fox
                   \____person
           0 = left side of the river
           1 = right side
        */
        if (input == 3)// Moves person and grain
        {
            // Are they on the same side?
            if (state == 9 || state == 11 || state == 13 || state == 15 ||
                state == 0 || state == 2 || state == 4 || state == 6)
            {
                // Move the person and grain
                state ^= 1 << 3;
                state ^= 1 << 0;
            }
            else
            {
                state ^= 1 << 3;
            }
        }
        else if (input == 2) // Moves person and chicken
        {
            // Are they on the same side?
            if (state == 10 || state == 11 || state == 14 || state == 15 ||
                state == 0 || state == 1 || state == 4 || state == 5)
            {
                // Move the person and chicken
                state ^= 1 << 3;
                state ^= 1 << 1;
            }
            else
            {
                state ^= 1 << 3;
            }
        }
        else if (input == 1)// Moves person and fox
        {
            // Are they on the same side?
            if (state == 12 || state == 13 || state == 14 || state == 15 ||
                state == 0 || state == 1 || state == 2 || state == 3)
            {
                // Move the person and fox
                state ^= 1 << 3;
                state ^= 1 << 2;
            }
            else
            {
                state ^= 1 << 3;
            }
        }
        else
        {
            // Always switch the person no matter what
            state ^= 1 << 3;
        }

        //Check if you won or lost
        if (state == 3 || state == 6 || state == 8 || state == 9 || state == 12) // Lost
        {
            return 0;
        }
        if (state == 15) // Won
        {
            return 1;
        }
    }
    return 1;
}

Answer 1

C will evaluate the condition of an if statement to true as long as it is non-zero.

The XOR operator (^) is probably not what you want to use to test whether a bit is set, such as here:

// Move the grain if the person is on the same side.
if (state ^ 1 << 3 && state ^ 1 << 0)

Let's assume that the state variable in this case should fail, ignoring the sizeof int, and using a bit mask of 1110 0001. This places the person on the high order side of the river, grain on the low order side.

The first condition of your if statement, state ^ 1 << 3, will create a temporary mask of 1110 1001. The second, state ^ 1 << 0, will create a bit mask of 1110 0000. This is nonsense, and not what you want.

So, given input that you want to fail (1110 0001), this if statement looks similar to:

if ( 0b11101001 && 0b11100000 )

Which succeeds (which is bad.)

What you probably want to do, is ensure that both the grain and the person are both on the right side of the "river", in their respective places ( 1 << 3 and 1 << 0 ). The best bitwise operator at your disposal is the AND operator.

This smells a little bit like a homework problem, so I'm going to stop short of fully answering your question; but you should have more than enough context here to get yourself pointed in the right direction.

Answer 2

To check if two bits are at the same state, shift one of the bits to the position of the other, XOR them together, AND with the bit indicating the position, and check that the result is zero. For example, to see that bit 1 is the same as bit 3, do this:

// Shift bit 3 to position 1, XOR, mask with 2, and check for zero
if ((2 & ((state >> 2) ^ state)) == 0) {
    ...
}

Answer 3

How can I check if the two bits are either 1 or 0 but not 1 and 0?

How about comparing them for equality?

#define MAN_MASK   (1<<3)
#define GRAIN_MASK (1<<0)

if(  
     ((state & MAN_MASK) == 0)
            == 
     ((state & GRAIN_MASK) == 0)
  );