«

James Fang <> writes:

> On Dec 7, 1:33 pm, aark...@gmail.com wrote:
>> How to find the greatest of 2 numbers without using relational
>> operators ?
>>
> Actually there's a simpler solution: you can use an array, and use the
> array index istead of the relational operators.
>
> int max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[(a-b)&0x80000000];
> }

Broken, but it does suggest a better way and does show why these
questions are so daft. Ruling out relational operators rules out a
reasonable branch-less solution (in C99 using compound literals):

((int [2]){a, b})[b > a]

--
Ben.

James Fang wrote:
....
> Actually there's a simpler solution: you can use an array, and use the
> array index istead of the relational operators.
>
> int max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[(a-b)&0x80000000];
> }

There are several problems with that approach. First of all, the mask
that you're using assumes a particular size for 'int' - that makes it
rather unportable. (UINT_MAX/2+1U) would be more portable. However, it
still wouldn't be perfect; it assumes that the sign bit of 'int' is
stored in the same location as the high-order bit of unsigned int, which
is a much more portable assumption, but technically the C standard
allows the corresponding bit of the unsigned type to be a padding bit.
Much more serious is the biggest problem: if a is less than b, your code
subscripts a 2-element array with 0x80000000!

That last item can be fixed, in several different ways. The simplest is:

return array[(a-b)&(UINT_MAX/X+1U) != 0];

> also, you can make use of the C system stack to get rid of extra
> memory space:
>
> int max(int a,int b)
> {
> // in C standard, the function parameters are pushed from right to
> left.
> // so integer b is stored in high address.

The C standard imposes no such requirement. That's an
implementation-specific detail.

On 12ÔÂ8ÈÕ, ÏÂÎç7ʱ22·Ö, Flash Gordon <s...@flash-gordon.me.uk> wrote:
> James Fang wrote, On 08/12/07 04:23:
>
>
>
> > On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.com> wrote:
> >> On Dec 7, 1:33 pm, aark...@gmail.com wrote:
>
> >>> Hi all,
> >>> The following question is asked frequently in interviews
> >>> How to find the greatest of 2 numbers without using relational
> >>> operators ?
> >>> the solution i have seen is
> >>> ( a+b + abs(a-b) ) /2 ;
> >>> is there any better solution than this ....?????
> >> In your solution there's an overflow issue.
>
> >> Actually there's a simpler solution: you can use an array, and use the
> >> array index istead of the relational operators.
>
> >> int max(int a,int b)
> >> {
> >> int array[2];
> >> array[0]=a;
> >> array[1]=b;
> >> return array[(a-b)&0x80000000];
>
> >> }
>
> Did you actually test this piece of rubbish? When I try it I always get
> the value of a. I'm really not sure how it is giving me that since the
> code is so broken. Just to show you how bad I've added a bit of
> diagnostic and here it is...
>
> markg@brenda:~$ cat t.c
> #include<stdio.h>
>
> int max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> printf("%d\n",(a-b)&0x80000000);
> return array[(a-b)&0x80000000];
>
> }
>
> int main(void)
> {
> printf("%d\n",max(1,2));
> return 0;}
>
> markg@brenda:~$ gcc -ansi -Wall -Wextra -O t.c
> markg@brenda:~$ ./a.out
> -2147483648
> 1
> markg@brenda:~$
>
> Obviously the index is just a little outside the array.
>
> >> also, you can make use of the C system stack
>
> C does not have a system stack. Your implementation might, but equally
> well it might not work as you expect.
>
> >> to get rid of extra
> >> memory space:
>
> >> int max(int a,int b)
> >> {
> >> // in C standard, the function parameters are pushed from right to
> >> left.
>
> Or they are passed in registers (if you take the address then obviously
> it has to allocate a memory location), or the stack might not grow in
> the direction you expect, or the parameters might be pushed left to right....
>
> >> // so integer b is stored in high address.
>
> >> return array *(&a+((a-b)&0x80000000>>31));
>
> int might not be 32 bits. It invokes undefined behaviour if you take a
> pointer to a, add 1 to it, and dereference it.
>
>
>
> >> }
>
> > Sorry, I've made a mistake, the second implementation should be:
>
> > int max(int a,int b)
> > {
> > // in C standard, the function parameters are pushed from right to
> > left.
> > // so integer b is stored in high address.
> > return *(&a+((a-b)&0x80000000>>31));
> > }
>
> No, the second implementation should be erased not corrected, and anyone
> who thinks it is valid needs to learn C. The first could be corrected as
> an intellectual exercise, but should never be used in real life.
> --
> Flash Gordon

Actually, I just missed one shift operation in the max function
because the code was written in a hurry in the bbs reply, attached
below is the corrected function int max(int,int).

My code is directly written in the bbs reply, the purpose of my code
is to illustrate new idea and algorithm, rather than help sb directly
do copy&paste job. The entire execution code is pasted below, it was
compiled with gcc and had basic functionality test on win32 system.


#include <stdio.h>

int max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[((a-b)&0x80000000)>>31];
}

int main()
{
printf("%d\n",max(-1,100));
printf("%d\n",max(10000,100));
printf("%d\n",max(99,99));
getchar();
}

On 12ÔÂ8ÈÕ, ÏÂÎç9ʱ25·Ö, James Kuyper <jameskuy...@verizon.net> wrote:
> James Fang wrote:
>
> ...
>
> > Actually there's a simpler solution: you can use an array, and use the
> > array index istead of the relational operators.
>
> > int max(int a,int b)
> > {
> > int array[2];
> > array[0]=a;
> > array[1]=b;
> > return array[(a-b)&0x80000000];
> > }
>
> There are several problems with that approach. First of all, the mask
> that you're using assumes a particular size for 'int' - that makes it
> rather unportable. (UINT_MAX/2+1U) would be more portable. However, it
> still wouldn't be perfect; it assumes that the sign bit of 'int' is
> stored in the same location as the high-order bit of unsigned int, which
> is a much more portable assumption, but technically the C standard
> allows the corresponding bit of the unsigned type to be a padding bit.
> Much more serious is the biggest problem: if a is less than b, your code
> subscripts a 2-element array with 0x80000000!
>
> That last item can be fixed, in several different ways. The simplest is:
>
> return array[(a-b)&(UINT_MAX/X+1U) != 0];
>
> > also, you can make use of the C system stack to get rid of extra
> > memory space:
>
> > int max(int a,int b)
> > {
> > // in C standard, the function parameters are pushed from right to
> > left.
> > // so integer b is stored in high address.
>
> The C standard imposes no such requirement. That's an
> implementation-specific detail.

Thanks for your correction. It's surely a more portable implementation
to use system defines.

BTW, since "!=" is also in the Relational Operator Set which is also
disatisfied with the question requirement, a better way may be like
below:
int get_max(int a,int b)
{
int array[2];
array[0]=a;
array[1]=b;
return array[( (a-b)& (UINT_MAX/2+1U) ) >>
((sizeof(int)*-1)];
}
int main()
{
printf("%d\n",get_max(-190,-100));
printf("%d\n",get_max(10000,100));
printf("%d\n",get_max(99,199));
}

For the sign bit assumption, can we use a serios of macro to control
it?

Anyway, in engineering practice, the best solution for this max impl
is to use the Relational Operators.

On Dec 8, 9:35 am, James Fang <fangshang...@gmail.com> wrote:
> Thanks for your correction...
>
> int get_max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[( (a-b)& (UINT_MAX/2+1U) ) >>
> ((sizeof(int)*-1)];}
>
> int main()
> {
> printf("%d\n",get_max(-190,-100));
> printf("%d\n",get_max(10000,100));
> printf("%d\n",get_max(99,199));
>
> }

Still wrong. With your code,
printf("%d
\n",get_max(2147483647,-1));
will print -1 as the answer.

Your entire attempt is stupid, and the OP's requirement
is stupid. Your whole attempt is pointless,
and encourages stupid programming.

James Fang wrote:
>
.... snip ...
>
> My code is directly written in the bbs reply, the purpose of my code
> is to illustrate new idea and algorithm, rather than help sb directly
> do copy&paste job. The entire execution code is pasted below, it was
> compiled with gcc and had basic functionality test on win32 system.
>
> #include <stdio.h>
>
> int max(int a,int b) {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[((a-b)&0x80000000)>>31];
> }
>
> int main() {
> printf("%d\n",max(-1,100));
> printf("%d\n",max(10000,100));
> printf("%d\n",max(99,99));
> getchar();
> }

And how does it work on sign magnitude systems, or 16 bit integer
systems, or any non-32 bit integer systems, etc.? What is the
useless 'getchar' for? Are there prizes for deleting blanks?

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

On 12ÔÂ8ÈÕ, ÏÂÎç10ʱ46·Ö, ptkmar...@gmail.com wrote:
> On Dec 8, 9:35 am, James Fang <fangshang...@gmail.com> wrote:
>
>
>
> > Thanks for your correction...
>
> > int get_max(int a,int b)
> > {
> > int array[2];
> > array[0]=a;
> > array[1]=b;
> > return array[( (a-b)& (UINT_MAX/2+1U) ) >>
> > ((sizeof(int)*-1)];}
>
> > int main()
> > {
> > printf("%d\n",get_max(-190,-100));
> > printf("%d\n",get_max(10000,100));
> > printf("%d\n",get_max(99,199));
>
> > }
>
> Still wrong. With your code,
> printf("%d
> \n",get_max(2147483647,-1));
> will print -1 as the answer.
>
> Your entire attempt is stupid, and the OP's requirement
> is stupid. Your whole attempt is pointless,
> and encourages stupid programming.

You are right, I omitted the overflow condition in the code, and it
can be workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >> ((sizeof(long
long)*-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?

On 12ÔÂ8ÈÕ, ÏÂÎç10ʱ46·Ö, ptkmar...@gmail.com wrote:
> On Dec 8, 9:35 am, James Fang <fangshang...@gmail.com> wrote:
>
>
>
> > Thanks for your correction...
>
> > int get_max(int a,int b)
> > {
> > int array[2];
> > array[0]=a;
> > array[1]=b;
> > return array[( (a-b)& (UINT_MAX/2+1U) ) >>
> > ((sizeof(int)*-1)];}
>
> > int main()
> > {
> > printf("%d\n",get_max(-190,-100));
> > printf("%d\n",get_max(10000,100));
> > printf("%d\n",get_max(99,199));
>
> > }
>
> Still wrong. With your code,
> printf("%d
> \n",get_max(2147483647,-1));
> will print -1 as the answer.
>
> Your entire attempt is stupid, and the OP's requirement
> is stupid. Your whole attempt is pointless,
> and encourages stupid programming.

You are right, I omitted the overflow condition in the code, and it
can be workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >> ((sizeof(long
long)*-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?

On 12ÔÂ8ÈÕ, ÏÂÎç10ʱ46·Ö, ptkmar...@gmail.com wrote:
> On Dec 8, 9:35 am, James Fang <fangshang...@gmail.com> wrote:
>
>
>
> > Thanks for your correction...
>
> > int get_max(int a,int b)
> > {
> > int array[2];
> > array[0]=a;
> > array[1]=b;
> > return array[( (a-b)& (UINT_MAX/2+1U) ) >>
> > ((sizeof(int)*-1)];}
>
> > int main()
> > {
> > printf("%d\n",get_max(-190,-100));
> > printf("%d\n",get_max(10000,100));
> > printf("%d\n",get_max(99,199));
>
> > }
>
> Still wrong. With your code,
> printf("%d
> \n",get_max(2147483647,-1));
> will print -1 as the answer.
>
> Your entire attempt is stupid, and the OP's requirement
> is stupid. Your whole attempt is pointless,
> and encourages stupid programming.

Just omitted the overflow condition in the code, and it can be
workarounded as follow:
int get_max(int a,int b)
{
long long divisor = (long long)a-(long long)b;
int array[2];
array[0]=a;
array[1]=b;
return array[( divisor & (ULLONG_MAX/2+1U) ) >> ((sizeof(long
long)*-1)];
}

As far as I am concerned, this question is rather an excersice than
what will be used in the real engineering environment. It forces the
coder to implement an "if(a<b){....}" expression with high level
programming language C rather than the compiler generated assembly.
In the assembly we can get the value of the status-register, which
will help us know the overflow in the last caculation. but with pure C
it is hard to get this valuable information(if I am wrong please
correct me).So it's impossible to implement a perfect "if(a<b){...}"
without knowing the processor details. And it's impossible for a
program caring the processor details be portable!

If we see the question as an excersice for "if(a<b){....}" and an
interesting puzzle, it is worthwhile to have a try and have some fun.

The "if(a>b){return a;}..." like impl is surely not stupid for the
real-world engineering, but it is surely not a clever answer for a
puzzle, right?

Anyway, I am with this answer just because that I am with this sounds-
interesting-question, not means that I support this kind of coding
standard in the project. I take your point that in engineering
practice, simply is the best.

BTW, is there any perfect solution to implement the "if(a<b){....}"
without any Relational Operator?

James Fang wrote, On 08/12/07 13:33:
> On 12ÔÂ8ÈÕ, ÏÂÎç7ʱ22·Ö, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>> James Fang wrote, On 08/12/07 04:23:
>>
>>> On Dec 8, 12:20 pm, James Fang <fangshang...@gmail.com> wrote:
>>>> On Dec 7, 1:33 pm, aark...@gmail.com wrote:
>>>>> Hi all,
>>>>> The following question is asked frequently in interviews
>>>>> How to find the greatest of 2 numbers without using relational
>>>>> operators ?
>>>>> the solution i have seen is
>>>>> ( a+b + abs(a-b) ) /2 ;
>>>>> is there any better solution than this ....?????
>>>> In your solution there's an overflow issue.
>>>> Actually there's a simpler solution: you can use an array, and use the
>>>> array index istead of the relational operators.
>>>> int max(int a,int b)
>>>> {
>>>> int array[2];
>>>> array[0]=a;
>>>> array[1]=b;
>>>> return array[(a-b)&0x80000000];
>>>> }
>> Did you actually test this piece of rubbish? When I try it I always get
>> the value of a. I'm really not sure how it is giving me that since the
>> code is so broken. Just to show you how bad I've added a bit of
>> diagnostic and here it is...
>>
>> markg@brenda:~$ cat t.c
>> #include<stdio.h>
>>
>> int max(int a,int b)
>> {
>> int array[2];
>> array[0]=a;
>> array[1]=b;
>> printf("%d\n",(a-b)&0x80000000);
>> return array[(a-b)&0x80000000];
>>
>> }
>>
>> int main(void)
>> {
>> printf("%d\n",max(1,2));
>> return 0;}
>>
>> markg@brenda:~$ gcc -ansi -Wall -Wextra -O t.c
>> markg@brenda:~$ ./a.out
>> -2147483648
>> 1
>> markg@brenda:~$
>>
>> Obviously the index is just a little outside the array.
>>
>>>> also, you can make use of the C system stack
>> C does not have a system stack. Your implementation might, but equally
>> well it might not work as you expect.
>>
>>>> to get rid of extra
>>>> memory space:
>>>> int max(int a,int b)
>>>> {
>>>> // in C standard, the function parameters are pushed from right to
>>>> left.
>> Or they are passed in registers (if you take the address then obviously
>> it has to allocate a memory location), or the stack might not grow in
>> the direction you expect, or the parameters might be pushed left to right...
>>
>>>> // so integer b is stored in high address.
>>>> return array *(&a+((a-b)&0x80000000>>31));
>> int might not be 32 bits. It invokes undefined behaviour if you take a
>> pointer to a, add 1 to it, and dereference it.
>>
>>
>>
>>>> }
>>> Sorry, I've made a mistake, the second implementation should be:
>>> int max(int a,int b)
>>> {
>>> // in C standard, the function parameters are pushed from right to
>>> left.
>>> // so integer b is stored in high address.
>>> return *(&a+((a-b)&0x80000000>>31));
>>> }
>> No, the second implementation should be erased not corrected, and anyone
>> who thinks it is valid needs to learn C. The first could be corrected as
>> an intellectual exercise, but should never be used in real life.
>> --
>> Flash Gordon
>
> Actually, I just missed one shift operation in the max function
> because the code was written in a hurry in the bbs reply, attached
> below is the corrected function int max(int,int).

No, you have several other errors. With assume int is 32 bits as I
already stated, your code will invoke undefined behaviour due to
overflow with some values. It may well have other problems, your second
example certainly does.

> My code is directly written in the bbs reply, the purpose of my code

I have no idea what you mean by bbs.

> is to illustrate new idea and algorithm, rather than help sb directly
> do copy&paste job. The entire execution code is pasted below, it was
> compiled with gcc and had basic functionality test on win32 system.

Specific implementations are not relevant.

> #include <stdio.h>
>
> int max(int a,int b)
> {
> int array[2];
> array[0]=a;
> array[1]=b;
> return array[((a-b)&0x80000000)>>31];
> }
>
> int main()
> {
> printf("%d\n",max(-1,100));
> printf("%d\n",max(10000,100));
> printf("%d\n",max(99,99));

#include <limits.h>
printf("%d\n",max(INT_MIN,INT_MAX);

I get the value of INT_MIN printed which is just a little incorrect.

> getchar();
> }

Basically the only sensible answer is that it is a stupid question.
--
Flash Gordon