Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Application Exercises Date: Fri, 12 Apr 2019 19:08:25 -0700 Organization: A noiseless patient Spider Lines: 117 Message-ID: <86ef66irmu.fsf@mailhub.linuxsc.com> References: <861s2emhi2.fsf@mailhub.linuxsc.com> <71d9629f-03be-40e1-bb23-3a9314e745df@googlegroups.com> <86tvf7ju49.fsf@mailhub.linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="df573815ed2de48149cf48b0bf16b748"; logging-data="4161"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18e1QG0PFFvWjqoJwvwkp14X4YZ9xr2P60=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:PXCo4oB1ynFz+A6YFAqa43LkSiE= sha1:KYzuWI/44K/MHPx/NHVJYjnp0vc= Xref: csiph.com comp.lang.c:143065 Richard Damon 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.