Write a C program to find the smallest of three integers, without using any of the comparison operators.

Question

I found this question online and have been struggling to come up with an answer to it on my own.

Bonus question I found. Write hello world in C without using a semicolon.

Answer 1

Here's a hint.

Answer 2

Answer to bonus question:

#error "Hello world"

Answer 3

The bonus question is quite easy:

#include <stdio.h>
int main (int argc, char *argc [])
{
  while (printf ("Hello world!\n") == 0)
  {
  }
}

although there are lots of semi-colons in the #include'd file - is that OK?

Skizz

Answer 4

Since 0 in C means false you could just do something like the following. All three args would have to be positive.

I'm very rusty at C. so, Pseudo C:

ct=0;
while(var1 && var2 && var3){
    var1--;
    var2--;
    var3--;
    ct++;
}
printf("%d",ct);

Answer 5

Smallest number (for non-negative numbers):

int smallest(int a, int b, int c) {
  int s = 0;
  while (a && b && c) {
    s++;
    a--; b--; c--;
  }
  return s;
}

Hello world:

#include <stdio.h>

int main() {
  if (printf("Hello world")) {}
}

Edit:

A variation of the above function working for all integers:

int smallest(int a, int b, int c) {
  int test = INT_MIN;
  while ((a-test) && (b-test) && (c-test))
    test++;
  return test;
}

Answer 6

Answer to Bonus Question

Answer 7

You can use bit twiddling to get the min or two integers, also unlike the other answers which use repeated subtraction, this solution supports negative numbers.

(min/max from http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)

#include <limits.h>
#include <stdio.h>

int main() {
    int x = 2;
    int y = 1;
    int z = 3;
    int r;

    r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
    r = z + ((r - z) & ((r - z) >> (sizeof(int) * CHAR_BIT - 1)));

    printf("%d\n", r);
}

NOTE: this depends on integers being implemented with 2's complement. I think this is fair game since we are talking about using tricks to do something which has an obvious and simpler solution anyway.

Answer 8

Without using a comparison operator and handles negative numbers (using minmax)

int main() {
    int v1 = smallest(-12, 12, 13);
    int v2 = smallest(-12, -14, -13);
    int v3 = smallest(11, 12, 13);
}

int smallest(int a, int b, int c)
{
   return min(min(a, b), c);
}

int min(int a, int b)
{
    a -= b;
    a &= a >> 31;
    a += b;
    return a;
}

Answer 9

Another example:

void main()
{
   if(printf("Hello World!")){}
}

Yet another example:

void main()
{
    printf("Hello World!") nosemicolon
}

Compile with:

gcc -Dnosemicolon=; ctest.c -o ctest

Answer 10

Here's my smallest of three solution. It doesn't use the inefficent while loop and appears to cope with negative values. I haven't tested it thoroughly but the maths looks OK to me:

#include <stdio.h>

int myabs (int a)
{
  return (((~a) + 1) & (a >> 31)) | (a & ~(a >> 31));
}

int smaller (int a, int b)
{
  return (a + b - myabs (a - b)) / 2;
}

int main (int argc, char *argv [])
{
  int
    a, b, c;

  if (argc != 4)
  {
    printf ("Error\n");
  }
  else
  {
    a = atoi (argv [1]);
    b = atoi (argv [2]);
    c = atoi (argv [3]);

    printf ("Smallest of %d, %d and %d is %d\n", a, b, c, smaller (smaller (a, b), c));
  }
}

Skizz

Answer 11

Not the fastest implementation, but more general (ie computes the minimum of an arbitrary number of integers), works with negative numbers and reasonably clear:

#include <limits.h>

int sign(int x)
{
    // portable, no branching:
    return (x > 0) - (x < 0);

    // non-portable, no comparisons:
    return +1 | (x >> (sizeof(int) * CHAR_BIT - 1));
}

int abs(int x)
{
    return sign(x) * x;
}

int min2(int a, int b)
{
    return ((a + b) - abs(a - b)) / 2;
}

int _min(unsigned n, int values[n])
{
    int m = INT_MIN;
    while(n--) m = min2(m, values[n]);
    return m;
}

#define min(...) \
    _min(sizeof((int []){ __VA_ARGS__ }) / sizeof(int), (int []){ __VA_ARGS__ })

extern int printf(const char *, ...)

int main(void)
{
    printf("%i", min(-5, 1, -2));
}

Answer 12

Reference: http://stackoverflow.com/questions/476800/comparing-two-integers-without-any-comparison

Next, we can raise a question to compare four integers. :)

Answer 13

int main() { int v1 = smallest(-12, 12, 13); int v2 = smallest(-12, -14, -13); int v3 = smallest(11, 12, 13); }

int smallest(int a, int b, int c) { return min(min(a, b), c); }

int min(int a, int b) { a -= b; a &= a >> 31; a += b; return a; }

Above program is working, but i dint get logic......why shifting 31 times???