Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #143065

Re: Application Exercises

Show all headers | View raw

Richard Damon <Richard@Damon-Family.org> writes:

> On 4/9/19 7:28 AM, Tim Rentsch wrote:
>
>> mark.bluemel@gmail.com writes:
>>
>>> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> |Write a function to detect whether two integral numbers are
>>>>> |equal without using any comparison operators.
>>>>
>>>> I have written a solution that I believe works correctly
>>>> on any conforming implementation.
>>>
>>> But it's too large to fit in this margin?
>>
>> Actually I wrote several solutions.  But I wasn't really
>> happy with any of them, they were all a bit clunky in one
>> way or another.  The point of my comment is just to say
>> a fully portable solution is possible.
>
> One thought I had, if we assume that x doesn't have near the absolute
> full range of uintmax_t (which we can get by using trick of comparing
> x/256 to y/256, and also x%256 to y%256 then, for an unsigned x
>
> (x+2)/(x+1)-1
>
> will have the value of 1 if x is 0 and 0 if x has any other value.
>
> This allows you to perform the effect of a comparison to zero, giving
> you the base results wanted.

This division method is clever, much moreso than my original
approach.  Using this insight we can write a routine to see if an
unsigned value is zero in just a few lines (the code uses the
type names 'Smax' and 'Umax' for the largest signed and unsigned
integer types):

    int
    unsigned_is_zero( Umax a ){
        Umax   half_plus_one    =  a/2 +1;
        Umax   upper_bits_zero  =  (half_plus_one + 1)/half_plus_one  - 1;
        Umax   low_bit_zero     =  a&1 ^ 1;

        return  upper_bits_zero  &  low_bit_zero;
    }

Note by the way that the '&1' in the initializer for 'low_bit_zero'
isn't actually needed.  Because 'upper_bits_zero' is always either
zero or one we can get the '&1' for free if we want to.

> it is now just a matter of using the range limitation trick once to
> limit the range of the numbers so we can safely convert them to unsigned
> (since it is allowed for the unsigned numbers to be a bit smaller than
> the signed numbers, effctively just forcing the sign bit to 0), take the
> difference as unsigned (so no overflow is possible), reduce range again
> (as the subtraction might generate a maximal unsigned value) and use the
> division trick to convert to an effective bool.

Rather than take the difference, if we want to compare two
unsigned values for equality, that can be done with '^':

    int
    unsigneds_are_equal( Umax a, Umax b ){
        return  unsigned_is_zero( a ^ b );
    }

> We will do this reduction 4 times, and we can get the product of the
> result (to simulate and AND operation) to detect if the original two
> numbers were numerically the same.

Here I'm lost.  I don't know what reduction you mean, or why it
needs to be done four times.  Also is there some reason you want
to avoid using an '&' operator?  It doesn't do a comparison and
so should be fair game (as should '^' and '|').  To avoid the
problem of unsigned types potentially having a width one smaller
than their corresponding signed type, we can break the signed values
into parts like what you suggest:

    int
    signeds_are_equal( Smax a, Smax b ){
        return
            unsigneds_are_equal( a/256, b/256 )  &
            unsigneds_are_equal( a%256, b%256 );
    }

Alternatively, we can use divide-by-two to compare all the upper
bits, and treat the remainder mod two specially:

    int
    signeds_are_equal( Smax a, Smax b ){
        return  unsigneds_are_equal( a/2, b/2 )  &  0421 >> a%2*3 + b%2 + 4;
    }

Here we are taking advantage of the unsigneds_are_equal()
function always returning zero or one to avoid a superfluous '&1'
in the residue test.

The end result is a remarkably compact solution.  I doff my
hat to you sir.

To save a bit of face, let me give a second followup challenge
problem.  Again we want to avoid using C's built-in comparison
operations (including !, which I forgot to mention in the first
go-round).  The functionality being sought is an implementation
for (keeping it simple, let's assume C99)

    int
    is_less_or_equal( intmax_t a, intmax_t b ){
        ...
    }

where the function returns 1 if argument 'a' is less than or
equal to argument 'b', and 0 otherwise.  Ideal solution should
work on any conforming C99 implementation.

Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-06 23:55 -0700
  Re: Application Exercises mark.bluemel@gmail.com - 2019-04-08 00:33 -0700
    Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-09 04:28 -0700
      Re: Application Exercises John Forkosh <forkosh@panix.com> - 2019-04-11 13:07 +0000
        Re: Application Exercises Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-04-11 06:11 -0700
          Re: Application Exercises John Forkosh <forkosh@panix.com> - 2019-04-11 13:19 +0000
            Re: Application Exercises James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-11 06:49 -0700
              Re: Application Exercises Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-12 01:20 +0100
      Re: Application Exercises Richard Damon <Richard@Damon-Family.org> - 2019-04-11 23:36 -0400
        Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-12 19:08 -0700

csiph-web