# find out the problem

Discussion in 'C Programming' started by sabarish, Aug 1, 2005.

1. ### sabarishGuest

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

sabarish, Aug 1, 2005

2. ### Eric SosmanGuest

sabarish wrote:
> 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.

different -- but that would have made the question sound
like homework, and we can't have that, can we?

--

Eric Sosman, Aug 1, 2005

3. ### Richard BosGuest

Eric Sosman <> wrote:

> sabarish wrote:
> > 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.

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

Richard

Richard Bos, Aug 1, 2005
4. ### Kenneth BrodyGuest

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

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

Kenneth Brody, Aug 1, 2005
5. ### Guest

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

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

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

, Aug 1, 2005
6. ### Walter RobersonGuest

In article <>,
<> wrote:
>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?
--
This signature intentionally left... Oh, darn!

Walter Roberson, Aug 1, 2005
7. ### Ben PfaffGuest

"sabarish" <> writes:

> 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.
--
--Richard Heathfield

Ben Pfaff, Aug 1, 2005
8. ### Eric SosmanGuest

[OT] Re: find out the problem

Richard Bos wrote:
> Eric Sosman <> wrote:
>
>
>>sabarish wrote:
>>
>>>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.

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

--

Eric Sosman, Aug 1, 2005
9. ### akarlGuest

sabarish wrote:
> 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

akarl, Aug 1, 2005
10. ### Keith ThompsonGuest

writes:
> 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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Aug 1, 2005
11. ### Eric SosmanGuest

akarl wrote:
> sabarish wrote:
>
>>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

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

--

Eric Sosman, Aug 1, 2005
12. ### Keith ThompsonGuest

"sabarish" <> writes:
> 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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Aug 1, 2005
13. ### akarlGuest

Eric Sosman wrote:
>
> akarl wrote:
>
>>sabarish wrote:
>>
>>
>>>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

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

akarl, Aug 1, 2005
14. ### Alexei A. FrounzeGuest

"Keith Thompson" <> wrote in message
news:...
> writes:
> > 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.

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

Alexei A. Frounze, Aug 1, 2005
15. ### Jack KleinGuest

On 1 Aug 2005 09:01:02 -0700, 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

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

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

....where did he say integer types?

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

Jack Klein, Aug 2, 2005
16. ### Krishanu DebnathGuest

Alexei A. Frounze wrote:
> "Keith Thompson" <> wrote in message
> news:...
> > 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

--
"What we need is less people running around and telling everyone else
what to do and more people actually writing code."
--Linus Torvalds

Krishanu Debnath, Aug 2, 2005
17. ### Alexei A. FrounzeGuest

"Krishanu Debnath" <> wrote in message
news:...
....
> > 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."

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

Alexei A. Frounze, Aug 2, 2005
18. ### Gordon BurdittGuest

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

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

Gordon Burditt, Aug 2, 2005
19. ### Tobias BlomkvistGuest

> 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
--
IMPORTANT: The contents of this email and attachments are confidential
and may be subject to legal privilege and/or protected by copyright.
Copying or communicating any part of it to others is prohibited and may
be unlawful.

Tobias Blomkvist, Aug 2, 2005
20. ### Alexei A. FrounzeGuest

"Gordon Burditt" <> wrote in message
news:...
....
> 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

Alexei A. Frounze, Aug 2, 2005