25

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

8
  • 6
    In C a non-zero number is non-zero. You haven't explicitly required the function to return 1 or 0 (but it is implied). Please explicitly define what your function will return. All you've given are 2 examples.
    – PP.
    Oct 12, 2010 at 7:51
  • 4
    At least make the function return a bool to avoid answers like return x; (yes, I did it). A bit of context would also be interesting, why would you (anyone) need to write such a function with such constraints ?
    – kriss
    Oct 12, 2010 at 8:07
  • 4
    Since when is + a bitwise operator? Oct 15, 2010 at 23:17
  • 8
    do people really ask lame questions like this in interviews? Its total BS (excuse the use of overly technical jargon)
    – pm100
    Oct 15, 2010 at 23:18
  • 12
    The correct answer to this interview question is: What do you intend to do with the result? comparison? So why can't I do the comparison in the first place? I have better things to do with my time, you have failed to be selected to become my boss.
    – mouviciel
    Oct 16, 2010 at 7:24

14 Answers 14

42

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;
}
8
  • 5
    You are using 11 bitwise operators here. (5x|, 5x>>, 1x&).
    – haylem
    Oct 12, 2010 at 7:02
  • 2
    "sub" isn't a bitwise op; a C++ solution would be easier if we \'re allowed -1
    – MSalters
    Oct 12, 2010 at 7:18
  • 2
    Why don't you just use neg? xor eax, eax; neg ecx; adc eax, 0;
    – wj32
    Oct 12, 2010 at 7:58
  • 1
    isNotZero explaination... n and -n can both only be non negative numbers IF n = 0. (n | (~n + 1)) is essnetially "or"ing n with -n. You then shift the most significant bit (which is the sign bit) to the right by 31 to put it in the least significant bit position. Then chop off any sign extended ones by "and"ing with 1.
    – CamHart
    Jan 16, 2014 at 17:25
  • 1
    There's a shorter assembler solution that doesn't modify the input variable (which is often better): xor eax, eax; cmp eax, n; adc eax, 0;
    – amichair
    Feb 20, 2015 at 20:35
11
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).

4
  • I guess this assumes 2nd complement representation (x + ~0 == x-1)
    – Suma
    Oct 12, 2010 at 7:50
  • On my Intel 32-bit Linux machine this function returns 0 or -1. If you subtract the answer from zero you would have a working function (on Intel 32-bit with gcc).
    – PP.
    Oct 12, 2010 at 7:58
  • @PP: That is why I wrote "Assuming ... signed shifts behave exactly like unsigned ones". This shows that on Intel 32-bit with gcc they don't behave the same, which is perfectly OK. In fact there are more problems with this solution when x is of signed type. I shall elaborate about that shortly...
    – usta
    Oct 12, 2010 at 8:12
  • I changed the parameter type to unsigned not only because results of bitwise operations on signed types are implementation-defined when arguments have negative values, but also because adding and subtracting a non-zero constant cannot reliably be used either, as then there'll be at least one value of x with which + or - will result in overflow, and hence undefined behavior.
    – usta
    Oct 12, 2010 at 8:25
10

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;
}
3
  • 2
    because that's not the requirement. the requirement is to return 1 for non-zero
    – Matt Ellen
    Oct 12, 2010 at 8:06
  • 1
    @Matt Ellen: let the OP write it would you ? When he wrote his question he stated Example: isNonZero(3) = 1, and example is not a requirement, never have been.
    – kriss
    Oct 12, 2010 at 8:17
  • 10
    Ok, but your function doesn't fulfil the example either.
    – Matt Ellen
    Oct 12, 2010 at 8:26
2
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

10
  • This will return 0 when x = 0x80000000
    – usta
    Oct 12, 2010 at 7:36
  • also + and - are not allowed, if you allow them it's much more simple.
    – kriss
    Oct 12, 2010 at 8:10
  • 1
    @kriss: + is explicitly allowed, see list.
    – MSalters
    Oct 12, 2010 at 11:01
  • @Matt: No, that is why there is a cast to unsigned. See ideone link. Oct 12, 2010 at 15:29
  • @usta: Yep, didn't think of that. Fortunately the fix is easy - use AND NOT instead of XOR. Oct 12, 2010 at 15:29
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 );
}
7
  • I'm not sure if creating a second function counts as a bitwise operator :)
    – JoshD
    Oct 12, 2010 at 6:30
  • I'm not a C person and I'm wondering why return x|(x&0); wouldn't work? Put that in your answer and I'll upvote. Oct 12, 2010 at 6:34
  • 1
    @Spencer Ruport: No, that won't work. That's a trivial identity; it will just return x. The result must be either 1 or 0.
    – JoshD
    Oct 12, 2010 at 6:38
  • 1
    @JoshD: Why should the result be 1 or 0, in C every non zero values means true. The identity works perfectly :-) Try is in an if if you don't believe so.
    – kriss
    Oct 12, 2010 at 8:05
  • 1
    @kriss: Yes, you're correct, but the question asks to return an integer with value either 0 or 1 as you can see from the function in the question. Otherwise you'd just return x and it would be a trivial problem.
    – JoshD
    Oct 12, 2010 at 8:15
0

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;
}
3
  • 1
    I think you have << where you mean to have >>
    – benzado
    Oct 12, 2010 at 6:51
  • 2
    You are using 24 bitwise operators here.
    – haylem
    Oct 12, 2010 at 7:09
  • @haylem: When I wrote the answer, that wasn't one of the requirements Oct 12, 2010 at 10:37
-1

My solution is the following,

int isNonZero(int n)
{
    return ~(n == 0) + 2;
}
1
  • 3
    == is not included in the list of legal operators. Dec 13, 2012 at 18:49
-1

My solution in C. No comparison operator. Doesn't work with 0x80000000.

#include <stdio.h>

int is_non_zero(int n) {
    n &= 0x7FFFFFFF;
    n *= 1;
    return n;
}

int main(void) {
    printf("%d\n", is_non_zero(0));
    printf("%d\n", is_non_zero(1));
    printf("%d\n", is_non_zero(-1));
    return 0;
}
1
  • is_non_zero(-1) returns 2147483647 = 0x7FFFFFFF (on a system with 32-bit 2's complement int like x86: godbolt.org/g/DJFTNu). n *= 1; is a no-op (note that it doesn't even appear in the asm output, is_non_zero just returns the low 31 bits). i.e. this doesn't produce a 0 / 1 return value at all. Nov 30, 2017 at 6:52
-2

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)
}
1
  • 1
    Comparison operators are not allowed as per the question; Only bitwise operators.
    – Core Xii
    Oct 15, 2010 at 7:25
-3
if(x)
     printf("non zero")
else
     printf("zero")
-3

The following function example should work for you.

bool isNonZero(int x)
{
    return (x | 0);
}
2
  • Just make sure bool is recognized as a type. On Linux using gcc, I had to add these to my .c file: Just make sure bool is defined as a type. Else I did this using gcc on Linux, so bool would be recognized as a type. #define true 1 #define false 0 typedef char bool; Jun 13, 2012 at 20:42
  • 3
    "| 0" is completely useless. All the work here is being done by the conversion to bool, if you're using a language with a real bool type, and not a typedef to an integer type.
    – Nicolás
    Jun 2, 2013 at 19:32
-3

This function will return x if it is non-zero, otherwise it will return 0.

int isNonZero(int x)
{
    return (x);
}
-4

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.

1
  • 4
    if statements aren't allowed in the problem. Oct 12, 2010 at 10:39
-4

return ((val & 0xFFFFFFFF) == 0 ? 0:1);

1
  • 1
    That's still an if, just in shorthand! Besides, val & 0xFFFFFFFF == val. Jun 14, 2012 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.