Check if a number is non zero using bitwise operators in C

The logarithmic version of the adamk function:

int isNotZero(unsigned int n){
  n |= n >> 16;
  n |= n >> 8;
  n |= n >> 4;
  n |= n >> 2;
  n |= n >> 1;
  return n & 1;
};

And the fastest one, but in assembly:

xor eax, eax
sub eax, n  // carry would be set if the number was not 0
xor eax, eax
adc eax, 0  // eax was 0, and if we had carry, it will became 1

Something similar to assembly version can be written in C, you just have to play with the sign bit and with some differences.

EDIT: here is the fastest version I can think of in C:

1) for negative numbers: if the sign bit is set, the number is not 0.

2) for positive: 0 - n will be negaive, and can be checked as in case 1. I don't see the - in the list of the legal operations, so we'll use ~n + 1 instead.

What we get:

int isNotZero(unsigned int n){ // unsigned is safer for bit operations
   return ((n | (~n + 1)) >> 31) & 1;
}

int isNonZero(unsigned x) {
    return ~( ~x & ( x + ~0 ) ) >> 31;
}

Assuming int is 32 bits (/* EDIT: this part no longer applies as I changed the parameter type to unsigned */ and that signed shifts behave exactly like unsigned ones).

Why make things complicated ?

int isNonZero(int x) {
    return x;
}

It works because the C convention is that every non zero value means true, as isNonZero return an int that's legal.

Some people argued, the isNonZero() function should return 1 for input 3 as showed in the example.

If you are using C++ it's still as easy as before:

int isNonZero(int x) {
    return (bool)x;
}

Now the function return 1 if you provide 3.

OK, it does not work with C that miss a proper boolean type.

Now, if you suppose ints are 32 bits and + is allowed:

int isNonZero(int x) {
    return ((x|(x+0x7FFFFFFF))>>31)&1;
}

On some architectures you may even avoid the final &1, just by casting x to unsigned (which has a null runtime cost), but that is Undefined Behavior, hence implementation dependant (depends if the target architecture uses signed or logical shift right).

int isNonZero(int x) {
    return ((unsigned)(x|(x+0x7FFFFFFF)))>>31;
}

int is_32bit_zero( int x ) {
    return 1 ^ (unsigned) ( x + ~0 & ~x ) >> 31;
}

1. Subtract 1. (~0 generates minus one on a two's complement machine. This is an assumption.)
2. Select only flipped bit that flipped to one.
3. Most significant bit only flips as a result of subtracting one if x is zero.
4. Move most-significant bit to least-significant bit.

I count six operators. I could use 0xFFFFFFFF for five. The cast to unsigned doesn't count on a two's complement machine ;v) .

http://ideone.com/Omobw