bit-manipulationbitwise-operators

Is it possible to test if a number is either even or '1', using only bitwise operators?


Is it possible to achieve using only bitwise operators, ie without logical/comparison/relation operators?

This would essentially be equivalent to the following.

(a & 1 == 0) || (a == 1)

I accept that in many languages a final equality comparison may need to be done to convert the result to a true/false value, but I am not considering that in the question. An answer which accepts an input bit array and returns the same output bit array for an even number as for '1' is essentially what I am after. Either that or a reason why it is not possible.


Solution

  • Although I would not recommend to do this at all, but I was able to achieve it in C, but with only making a to be anunsigned char. It could work with others too, but that would lengthen the condition.

    #include <stdio.h>
    
    int main() {
        for (unsigned char a = 0; a < 255; a++) {
            if ((~a & 1) | (1 >> (a & 0x0E | a >> 4)))
                printf ("%d is even or 1\n", a);
            else
                printf("%d is odd\n", a);
        }
        return 0;
    }
    

    (~a & 1) will yield 1 if a is even. (a & 0x0E | a >> 4) will yield 0 when a is either 1 or 0. Therefore in those cases (1 >> (a & 0x0E | a >> 4))) will be (1 >> 0) which is 1, otherwise the shift value is between 1 and 15 so making the expression 0.

    My initial approach was (1 >> (a >> 1)), but soon realized this cause shift overflow, since the shift amount exceed the max possible. And not just raising that warning, but actually falsely recognize every n * 64 + 1 values as even. So the more complicated approach is there to limit the shift amount to be less than 64 by OR -ing a upper 4 bit with its lower 4 bit, but setting the LSB to 0. This resulting number is <= 15 and only 0 when a is 1 or 0 just as needed.