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

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

Answer 2

basically you need to or the bits. For instance, if you know your number is 8 bits wide:

int isNonZero(uint8_t x)
{
    int res = 0;
    res |= (x >> 0) & 1;
    res |= (x >> 1) & 1;
    res |= (x >> 2) & 1;
    res |= (x >> 3) & 1;
    res |= (x >> 4) & 1;
    res |= (x >> 5) & 1;
    res |= (x >> 6) & 1;
    res |= (x >> 7) & 1;

    return res;
}

Answer 3

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

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 6

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 7

int isNonZero(int x)

{

if (  x & 0xffffffff)
    return 1;
else
    return 0;

}

Let assume Int is 4 byte.

It will return 1 if value is non zero

if value is zero then it will return 0.

Answer 8

My solution,though not quite related to your question

int isSign(int x)

{
//return 1 if positive,0 if zero,-1 if negative
return (x > 0) - ((x & 0x80000000)==0x80000000)
}

Answer 9

Here's one that works regardless of the size of integers:

int isNonZero(int x) { return ~( (x & 0) == x ) + 2; }

Breakdown:

(x & 0) == x  // Returns 1 when x is 0, 0 when x <> 0

~( (x & 0) == x )  // Flips the bits, -2 when x is 0, -1 when x <> 0

~( (x & 0) == x ) + 2;  // OR by 2 to make results 0 or 1.
                        // (+ is bitwise OR or ADD, handy and underhanded)

Answer 10

Because I'm snotty:

return x;

works fine. I don't see any explicit requirements about the return value, and this happily yields the correct behavior if you stick the function call into a conditional expression.