c - Bit manipulation, return 0 if x != 0, or nonzero otherwise

Question

I am writing a function is_zero that is supposed to return 0 if x != 0, or nonzero otherwise. I am not allowed to use any constants. For example, x == 0 is not allowed. (the == operator is not allowed either)

The only operators I am allowed to use are =, ~, ^, * (dereferencing), &, |, <<, >> and +.

The way I have the function written now is it will return 0 if x != 0, but it still returns 0 even when x == 0, which is it not supposed to do. I have attempted all sorts of combinations, but this homework question appears impossible given the constraints. I am posting here as a last ditch effort.

Can anybody how me how I can get my code to return something other than 0 when x == 0, while still returning 0 when x != 0?

int is_zero(int x) {
    return (x ^ x);
}

Answer 1

I don't believe it's possible to solve if you want the code to work without assuming a certain size of int and representation. But this works for 32-bit ints and two's complement representation:

int is_zero(int x) {
    int zero = (x^x);
    int one = ~(~zero + ~zero);
    int five = one + one + one + one + one;
    int thirtyone = (one << five) + ~zero;
    return ~((x >> thirtyone) | ((~x + one) >> thirtyone));
}

It uses multiple assignments to construct the constants, but the code could be folded into a single expression if necessary.

How it works

(x >> thirtyone) is -1 if x is negative and 0 otherwise. Similarly, (~x + one) >> thirtyone is -1 if x is positive, and 0 otherwise.

The bitwise or of these two expressions is 0 if x is zero, and -1 otherwise. A bitwise ~ then gives -1 if x is zero, and 0 otherwise.

(Almost) word-size independent solution

It's not perfectly word-size independent, but one can extend the solution above to work for 16, 32 and 64 bit ints (although still depending on two's complement representation). The code is careful to not shift more than 15 bits at a time (otherwise the result is undefined behavior if int is 16 bits):

int is_zero(int x) {
    int zero = (x^x);
    int one = ~(~zero + ~zero);
    int four = one + one + one + one;
    int k15 = (one << four) + ~zero;
    return ~((x >> k15 >> k15 >> k15 >> k15 >> k15) |
             ((~x + one) >> k15 >> k15 >> k15 >> k15 >> k15));
}