Fog Creek Software
Discussion Board




detect

C function is passed an integer argument. Should return 1 if the argument is 0 else return 0. No logical operators, bit wise  operators, "if then else" can be used

Smitha George
Wednesday, May 15, 2002

You didn't say anything about while/for loops, which would allow the following possibility:

int detect(int a) {
  while(a) {
    return 0;
  }
  return 1;
}

Assuming that's cheating, and an integer is max 32 bit, the following would work.

int detect(int a) {
  unsigned int b = a;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;
  b -= b/2;  b -= b/2;  b -= b/2;  b -= b/2;

  return 1-b;
}

All in all, I like this one best ...

int detect(int a) {
  unsigned int b = a;  /* kill negative input */
  b -= b/2; /* prevents overflow when a == -1 */
  return ((b+2) / (b+1)) -1;
}

Paul Viney

Paul Viney
Wednesday, May 15, 2002

I am sure I am missing something but I fail to understand what is the problem with

int detect(int x){
        return x==0;
}

"==" is neither a logical nor bitwise operator.

vivek gupta
Thursday, May 16, 2002

the problem with return (x == 0) is that it uses "if"

paul's solution of returning b+2/b+1 - 1 works great.
i understand the unsigned part, but don't understand the second step b -= b/2 ??  why do we need this?

Vin
Thursday, May 16, 2002

if the input is -1, then b becomes the maximum possible unsigned integer, which means that b+2 gives an overflow. The b -= b/2  is a safe way to make sure that this doesn't happen.

Paul Viney

Paul Viney
Friday, May 17, 2002

of course.  but why b -= b/2?  why not just b = b/2?

Vin
Friday, May 17, 2002

Suppose b was 1. b = b/2 would leave b on zero. Bad News.

Paul Viney

Paul Viney
Friday, May 17, 2002

crystal.  thanks!  it's a clever solution btw.

Vin
Friday, May 17, 2002

*  Recent Topics

*  Fog Creek Home