Efficiently Check Bitflag Invariant (possible bit-twiddle)

Question 1

I haven't profiled this, so no promises, but you could try:

int check(char b)
{
    return ! ( (b << 1) & b & 0xaa );
}

You could do away with the inversion ! if you accepted non-zero (not just 1) as a fail, and zero as a pass.

Alternatively, you could just use the lookup table you already generated:

int check(char b)
{
    return truth[(unsigned char)b];
}

Whatever you try, please profile!

(oh, and I'd recommend using unsigned chars rather than signed chars for storing bit-fields like this, as the behaviour is better defined for things like bit-shifts and booleans. Most compilers will probably do what you expect, but better safe than sorry).

Question 2

You essentially have four tristate values: either option 1 is set, or option 2 is set, or neither. You might want to consider using bit fields in a struct to explicitly get nsigned integers of two bits each to track these tristates:

struct Flags {
    unsigned opt1: 2;
    unsigned opt2: 2;
    unsigned opt3: 2;
    unsigned opt4: 2;
};
const unsigned NEITHER = 0;
const unsigned FIRSTOPT = 1;
const unsigned SECONDOPT = 2;
const unsigned INVALIDOPT = 3;

With this setup, your question boils down to checking that all four fields are not equal to INVALIDOPT. Your check function could thus be

bool IsValid(struct Flags flags) {
    return flags.opt1 != INVALIDOPT &&
           flags.opt2 != INVALIDOPT &&
           flags.opt3 != INVALIDOPT &&
           flags.opt4 != INVALIDOPT;
}

This also means that instead of twiddling bits to set which option is selected, you can just do normal variable reads and writes with the named constants. It should be much easier and much safer.

Hope this helps!

Question 3

To prevent it in the first place:

#define NONE_SET 0 // 00
#define FIRST_SET 1 // 10
#define SECOND_SET 2 // 01

int magic(int AB, int CD, int EF, int GH) {
  return (((AB*3+CD)*3+EF)*3+GH)*3
}

Better yet, use an enum instead of #defines

Example invocation (e.g. for ABCDEFGH=10000100)

int magic_number = magic(FIRST_SET, NONE_SET, SECOND_SET, NONE_SET);

no bit twiddling, just some multiplications. (This can obvoiusly be automated)

If you just want to check if pairs of bits in a byte are not both set:

uint8_t in; // the input byte
uint8_t out = in & (in >> 1) & 0x55; 
// if out != 0, the invariant is violated

note: 0x55 is 01010101 in binary (i.e. we are masking off adjacent pairs like BC, leaving only those like AB and CD)