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

Question

Check whether a number x is nonzero using the legal operators except !.

Examples: isNonZero(3) = 1, isNonZero(0) = 0

Legal ops: ~ & ^ | + << >>

• Note : Only bitwise operators should be used. if, else, for, etc. cannot be used.
• Edit1 : No. of operators should not exceed 10.
• Edit2 : Consider size of int to be 4 bytes.

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

Using ! this would be trivial , but how do we do it without using ! ?

Answer 1

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;
}

Answer 2

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).

Answer 3

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;
}

Answer 4

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

Answer 5

Bitwise OR all bits in the number:

int isByteNonZero(int x) {
    return ((x >> 7) & 1) |
           ((x >> 6) & 1) |
           ((x >> 5) & 1) |
           ((x >> 4) & 1) |
           ((x >> 3) & 1) |
           ((x >> 2) & 1) |
           ((x >> 1) & 1) |
           ((x >> 0) & 1);
}

int isNonZero(int x) {
  return isByteNonZero( x >> 24 & 0xff ) |
         isByteNonZero( x >> 16 & 0xff ) |
         isByteNonZero( x >> 8  & 0xff ) |
         isByteNonZero( x       & 0xff );
}