find out the problem

[sabarish]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

 

[Eric Sosman]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

This cannot be done, not even by using non-portable
trickery. The reason is simple: there is no such thing
as the "biggest" of just two numbers. The superlative
form of an adjective implies three or more alternatives.

Had you written "bigger" the answer might have been
different -- but that would have made the question sound
like homework, and we can't have that, can we?

 

[Richard Bos]

This cannot be done, not even by using non-portable
trickery. The reason is simple: there is no such thing
as the "biggest" of just two numbers. The superlative
form of an adjective implies three or more alternatives.

No, they don't. Check the OED. What you describe is merely customary in
some circles, but not the only correct usage.

Richard

 

[Kenneth Brody]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

So, how many open NNTP proxies do you have access to?

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[agarwal.prateek]

result=(x-y) //subtract y from x
//if x>y result is +ve else -ve

result=result >>31 //get the sign bit to last bit
result=result&0x01 //mask the last bit

return x*result + y*(~result & 0x1)

if result =1 x will be returned as ~result&0x1 would be 0

 

[Walter Roberson]

result=(x-y) //subtract y from x
//if x>y result is +ve else -ve

Why would the result be negative if the two values are equal?

 

[Ben Pfaff]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

This question has been beaten to death over the years. Try
searching the archives.

 

[Eric Sosman]

No, they don't. Check the OED.

No thanks; I've got other uses for $295.

What you describe is merely customary in
some circles, but not the only correct usage.

"Some circles" meaning "Those who value English," I
guess ...

Does the OED list "irregardless?" Does it list "verb"
as a transitive verb? Does it endorse the sportscasters'
monstrous misuse of the present indicative for the subjunctive
("If I'm Alex Rodriguez I'm looking fast ball here")? We're
down to the old prescriptive vs. descriptive debate, and I for
one choose not use a description of other people's bad usage
as a prescription for my own. Harrumph!

 

[akarl]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

It's simple as well as off topic (since it's not C specific):

max(x, y) = (x + y + |x - y|) / 2


August

 

[Keith Thompson]

result=(x-y) //subtract y from x
//if x>y result is +ve else -ve

result=result >>31 //get the sign bit to last bit
result=result&0x01 //mask the last bit

return x*result + y*(~result & 0x1)

if result =1 x will be returned as ~result&0x1 would be 0

That has so many portability problems I'm not going to bother to
decide whether it's correct.

 

[Eric Sosman]

It's simple as well as off topic (since it's not C specific):

max(x, y) = (x + y + |x - y|) / 2

Try it with x = LDBL_MAX and y = -LDBL_MAX, and tell us
again just how "simple" it is.

Do other such misbehaving pairs exist? Oh yes, oh yes,
they most definitely do. I ran a simple test on a million
pairs of randomly-generated[*] `double' values, on which
akarl's formula delivered the right answer 596230 times --
and gave a wrong answer the other 403770 times. If you can
tolerate error rates of 40% or so, by all means use akarl's
"simple" formula.

[*] Not from a uniform distribution. I wanted a wide
spread of magnitudes, so I used tan(rand() * PI / RAND_MAX).

 

[Keith Thompson]

Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.

Use relational operators. That's what they're for.

If there's some reason you need to do this without using the features
of the language designed for that purpose, you should explain why if
you expect any help.

If the reason is that it's a homework assignment (which is the only
explanation I can think of), do it yourself.

 

[akarl]

sabarish wrote:




It's simple as well as off topic (since it's not C specific):

max(x, y) = (x + y + |x - y|) / 2

Try it with x = LDBL_MAX and y = -LDBL_MAX, and tell us
again just how "simple" it is.

Do other such misbehaving pairs exist? Oh yes, oh yes,
they most definitely do. I ran a simple test on a million
pairs of randomly-generated[*] `double' values, on which
akarl's formula delivered the right answer 596230 times --
and gave a wrong answer the other 403770 times. If you can
tolerate error rates of 40% or so, by all means use akarl's
"simple" formula.

[*] Not from a uniform distribution. I wanted a wide
spread of magnitudes, so I used tan(rand() * PI / RAND_MAX).

Note that I've only presented a mathematical formula, not a C
implementation ;-) However the whole matter is more of theoretical
interest; Why would anyone want to implement it without relational
operators?


August

 

[Alexei A. Frounze]

That has so many portability problems I'm not going to bother to
decide whether it's correct.

The correct would be (on a 2's complemented target where the right shift
operator performed on a signed value keeps the MSBit/sign bit, aka Shift
Right Arithmetic):

#include <stdio.h>

/* BITS_IN_LONG says how many bits are in long, can be computed (at run time
but then it'll be a variable not macro) or if exists such a define somewhere
in the std libc headers, can be taken right from there: */
#define BITS_IN_LONG 32

long Max(long x, long y)
{
long res;
res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */
res = (x & ~res) | (y & res); /* depending on prev value of res, we just
select/multiplex x or y by means of bitwise masking */
return res;
}

int main()
{
printf ("%ld\n", Max(-1,-1));
printf ("%ld\n", Max(-1, 0));
printf ("%ld\n", Max(-1, 1));
printf ("%ld\n", Max( 0,-1));
printf ("%ld\n", Max( 0, 0));
printf ("%ld\n", Max( 0, 1));
printf ("%ld\n", Max( 1,-1));
printf ("%ld\n", Max( 1, 0));
printf ("%ld\n", Max( 1, 1));
return 0;
}
Gives as expected:
-1
0
1
0
0
1
1
1
1

I'd suggest the newbies learn boolean stuff and digital logic better (or at
all if never studied before). I know that the above thing has a limited use,
but the limit is many millions of CPUs where it would work just fine.
And honestly, fixed point math (where people often use similar tricks) is
much more portable than floating point. It will yield the same result (if
coded properly, of course) on all targets and compilers, whereas floating
point will almost always give different LSBit (due to optimization,
operation reordering or because of simply being not IE754 compliant or using
shorter floating types) and since the errors tend to accumulate, the
difference can be bigger.

There're a few great docs on the subjects:
Sun's Numerical Computation Guide / What Every Computer Scientist Should
Know About Floating-Point Arithmetic by Goldberg
and
Algorithms For Programmers ideas and source code by Arndt

HTH
Alex

 

[Jack Klein]

On 1 Aug 2005 09:01:02 -0700, (e-mail address removed) wrote in
comp.lang.c:

Your decision to use the broken Google interface DOES NOT entitle you
to inflict the bad manners of responses with NO CONTEXT. LEARN HOW TO
QUOTE PROPERLY.

Hmmm...

double return_larger(double x, double y)
{
double result;
/* so far so good */

result=(x-y) //subtract y from x
//if x>y result is +ve else -ve

Complaint about missing ;

result=result >>31 //get the sign bit to last bit
result=result&0x01 //mask the last bit

return x*result + y*(~result & 0x1)

if result =1 x will be returned as ~result&0x1 would be 0

....just a few messages from an unhappy compiler.


Now as the OP's original question was:

....where did he say integer types?

 

[Krishanu Debnath]

(e-mail address removed) writes:

[snip]

The correct would be (on a 2's complemented target where the right shift
operator performed on a signed value keeps the MSBit/sign bit, aka Shift
Right Arithmetic):

#include <stdio.h>

/* BITS_IN_LONG says how many bits are in long, can be computed (at run time
but then it'll be a variable not macro) or if exists such a define somewhere
in the std libc headers, can be taken right from there: */
#define BITS_IN_LONG 32

long Max(long x, long y)
{
long res;
res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */

It invokes UB. C99 6.5.7p3

"If the value of the right operand is negative or is greater than or
equal to the width of the promoted left operand, the behavior is
undefined."

res = (x & ~res) | (y & res); /* depending on prev value of res, we just
select/multiplex x or y by means of bitwise masking */
return res;
}

Krishanu

 

[Alexei A. Frounze]

....

It invokes UB. C99 6.5.7p3

"If the value of the right operand is negative or is greater than or
equal to the width of the promoted left operand, the behavior is
undefined."

I know it's undefined *by standard*. But it's pretty much well defined by so
many compilers out there... Can one name a compiler that issues an error at
that shift operator or yields garbage or freaks out? Can anyone name one
that doesn't extend/propagate the sign bit to the right? I'm asking out of
curiousity, since 6 or 7 compilers that I know would handle that just right
(on about 5 entirely different CPUs, ix86 and several non-ix86).

Alex

 

[Gordon Burditt]

long res;

I know it's undefined *by standard*. But it's pretty much well defined by so
many compilers out there... Can one name a compiler that issues an error at
that shift operator or yields garbage or freaks out? Can anyone name one

There are a number of assembly languages where the shift count can
be a variable but only a small number of bits are used. Higher-order
bits in the count are ignored. (Typically a shift of the number
of bits in the word is equivalent to a shift of 0 (no change) rather
than filling the entire word with the sign bit or with zeroes.)

Compilers typically take the shift count, stuff it in a register,
and use the register for the shift count in a shift instruction.
If the shift count is out of range for the instruction, let the
nasal demons fly where they may.

For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A
shift of N bits of an int or long (32 bits in this case) to the
right seems to be treated the same as a shift of (N%32) bits to the
right *WHEN THE SHIFT COUNT IS VARIABLE*. This is "wrong" according
to what people would expect a shift to do. You get different results
sometimes if the shift amount is a constant rather than a variable.

that doesn't extend/propagate the sign bit to the right? I'm asking out of
curiousity, since 6 or 7 compilers that I know would handle that just right
(on about 5 entirely different CPUs, ix86 and several non-ix86).

The code:

#include <stdio.h>
int x(int a)
{
printf("%d: %lx\n", a, 0x12345678 >> a);
return 0;
}
int main(void)
{
x(36);
x(32);
x(0);
return 0;
}

The output (annotated to the right):
36: 1234567 Same as a shift of 4
32: 12345678 Same as no shift at all
0: 12345678

Gordon L. Burditt

 

[Tobias Blomkvist]

Gordon Burditt sade:

For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A
[snippy-snip]

int main(void)
{
x(36);
x(32);

On all IA-32 processors starting with Intel 286, the shift count
is masked to 5 bits, resulting in a maximum count of 31.

(IA-32 Intel Architecture Software Developer's Manual Volume 2, page 737)

Hence:

> The output (annotated to the right):
> 36: 1234567 Same as a shift of 4
> 32: 12345678 Same as no shift at all
> 0: 12345678

Tobias

 

[Alexei A. Frounze]

....

There are a number of assembly languages where the shift count can
be a variable but only a small number of bits are used. Higher-order
bits in the count are ignored. (Typically a shift of the number
of bits in the word is equivalent to a shift of 0 (no change) rather
than filling the entire word with the sign bit or with zeroes.)
Yep.

Compilers typically take the shift count, stuff it in a register,
and use the register for the shift count in a shift instruction.
If the shift count is out of range for the instruction, let the
nasal demons fly where they may.

I've seen that and was very surprised.

For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A
shift of N bits of an int or long (32 bits in this case) to the
right seems to be treated the same as a shift of (N%32) bits to the
right *WHEN THE SHIFT COUNT IS VARIABLE*. This is "wrong" according
to what people would expect a shift to do. You get different results
sometimes if the shift amount is a constant rather than a variable.

The code:

#include <stdio.h>
int x(int a)
{
printf("%d: %lx\n", a, 0x12345678 >> a);
return 0;
}
int main(void)
{
x(36);
x(32);
x(0);
return 0;
}

The output (annotated to the right):
36: 1234567 Same as a shift of 4
32: 12345678 Same as no shift at all
0: 12345678

That all is correct, no doubt, however, my personal opinion is that that's
wrong to take the shift count and blindly feed it to the asm instruction
with such a limitation. It's as illogical as the need to cast one of two
integer multipliers to long integer in order to get the correct long integer
product. That strikes the math guys in the back. Anyway, I was talking about
a slightly different problem of the shift -- whether or not it's SAR-like or
something else, especially something very odd, probably not any kind of
shift at all.

Alex