compare a large number of variables

[Netocrat]

Albeit ugly, this should work:

if(a-b|b-c|c-d|d-e /* ... */)
puts("mismatched");
else
puts("pick one... they're all the same");

All zero? Overflow?

Also it doesn't use the ^ operator - but you my not have been responding
directly to what I said (which was intended to mean that I can't see a way
to rearrange the expression so that it works as intended, keeping the ^
expressions and using other bitwise operators as required - and I wouldn't
have objected to an overall negation operator if that had been necessary).

 

[Netocrat]

In the case of one variable with a==1, value==1 then a^value
is false. The first branch of the 'if' is not taken; all
elements of {a} are equal to value, or equivalently, none of
the elements of {a} is not equal to value.

The 'if' expression works just as the comment says it does.
The remark of "No that doesn't work" is therefore, shall
we say, less than totally accurate.

If the comment entirely defined the expected behaviour, then you would be
right. Actually though, the code is to be read as though followed by:

else
/* all variables are equal to value */

because the context of the thread is a search for a one-liner to determine
whether all variables are equal to a value or not. The example I
provided shows that as a one-liner it fails in at least one case.

 

[Tim Rentsch]

It's identical to my original comment except for the addition of a couple
of commas. Please be more specific.

In the case of one variable with a==1, value==1 then a^value
is false. The first branch of the 'if' is not taken; all
elements of {a} are equal to value, or equivalently, none of
the elements of {a} is not equal to value.

The 'if' expression works just as the comment says it does.
The remark of "No that doesn't work" is therefore, shall
we say, less than totally accurate.

 

[Tim Rentsch]

If the comment entirely defined the expected behaviour, then you would be
right. Actually though, the code is to be read as though followed by:

else
/* all variables are equal to value */

No, it isn't. That might be your reading, but it's certainly
not necessary to understand the point being made, nor, I feel
confident, what the poster intended. In any case that's
irrelevant; your comments should be on what *was* written,
and if you want to make presumptions about something that
*wasn't* written then the burden is on you to state what
those presumptions are. Don't expect other people to read
your mind.

because the context of the thread is a search for a one-liner to determine
whether all variables are equal to a value or not. The example I
provided shows that as a one-liner it fails in at least one case.

Re-read the thread. I think you'll find that the context of
the thread is a search for code to determine whether *any*
variables are *not* equal to a value. Which is exactly what
the posted code did.

 

[Netocrat]

On Thu, 18 Aug 2005 17:11:25 +0000, Michael Wojcik wrote:
Yes, your suggestions work perfectly, but I was mor looking
for a nice bit operator to operate on all my variables and
then to compare it with the value. something like
(a|b|c|d...z) != value (this wont work however... ).

How about (off the top of my head and untested):

if ( !( ((a|b|c|d...z) == value) && ((a&b&c&d...z) == value) )
)
/* one or more of a,b,c,d...z is not equal to value */

Or the similarly silly:

if (a^value|b^value|c^value|...|z^value)
/* one or more of a,b,c,...,z is not equal to value */

No that doesn't work. [...]
The 'if' expression works ... The remark of "No that doesn't work" is
therefore, shall we say, less than totally accurate.

Xors have always been a weak spot in my logic. You're right, the code
works as advertised as Pete attempted to point out elsewhere in his usual
understated style.

[...]

 

[Mark]

All zero? Overflow?

Overflow is not possible, stare at it for a while and see if you can figure
out why

Also it doesn't use the ^ operator

You didn't say it had to use the exclusive or operator ... you said bit
operator, no?
AFAIK the inclusive or operator is a bit operator... do you disagree?

- but you my not have been responding

directly to what I said

I was.

(which was intended to mean that I can't see a way
to rearrange the expression so that it works as intended, keeping the ^

No, you said using bitwise operators, which I most definately did.

expressions and using other bitwise operators as required - and I wouldn't
have objected to an overall negation operator if that had been necessary).

Whatever that means.
Do you know what the code does? Obviously not if you're worried about
overflow

 

[Netocrat]

Embarrassingly, my logic circuits have been malfunctioning in this
thread... as evidenced above (the xor code works contrary to my claim) and
here - the code performs correctly for all variables zero.

Overflow is not possible, stare at it for a while and see if you can figure
out why

Perhaps I don't understand the overflow requirements. And perhaps I
should have called it underflow instead of overflow. But by my
understanding, if a and b are unsigned and a == 0 and b > 0, then the
expression (a-b) results in an underflow, which is undefined behaviour.

I don't see that this would be changed by it being part of a greater
expression. But my strike rate in this thread hasn't been crash hot so
I'm not betting the bank on it...

Alternatively this could occur if both are signed int and a == INT_MIN
and b > 0, but as noted by Michael Wojcik the bitwise operators may result
in trap representations for signed types - so we should require unsigned
variables for portability.

You didn't say it had to use the exclusive or operator ... you said bit
operator, no?

Right, but I wrote "rearranged" and intended that to mean retaining the
expressions with the ^ operator, but I can see how you might have
interpreted me differently. Anyhow as it turns out there is no need for
rearrangement as it works as is.

[...]

Do you know what the code does?

It looks to me like it compares each variable to its neighbour by
subtracting one from the other; if any of the comparisons are unequal then
at least one bit will be set in the result and the bitwise or will
agglomerate any of these bits into the final result, which will be
non-zero only if any variable differs from its neighbour - and by chaining
neighbours this equates to if any variable differs from any of the rest.

[...]

 

[Mark]

Overflow is not possible, stare at it for a while and see if you can
figure out why

Rather than 'not possible' let me rephrase and say 'not an issue'
unless the values are equal, there must be at least one bit set...
which will in turn cause the statement to work properly.

You didn't say it had to use the exclusive or operator ... you said bit
operator, no?
AFAIK the inclusive or operator is a bit operator... do you disagree?

- but you my not have been responding
I was.

Well, actually I was also responding to the OP question, which as of yet you
had not answered properly

No, you said using bitwise operators, which I most definately did.

And again, OP did not require exlusive or operator.

Whatever that means.

I realized what you meant after reading your post a 2nd time... should have
waited a minute before responding, but I do that frequently

Do you know what the code does? Obviously not if you're worried about
overflow

.... as it couldn't affect the outcome of the statement... it should work
properly regardless.

Much better, I'm happy now.
Mark

 

[Netocrat]

[attributions cleaned up and simplified]

Mark wrote:
Netocrat wrote: [...]

if ( !( ((a|b|c|d...z) == value) && ((a&b&c&d...z) == value) ) )
/* one or more of a,b,c,d...z is not equal to value */ [...]
Albeit ugly, this should work:

if(a-b|b-c|c-d|d-e /* ... */)
puts("mismatched");
else
puts("pick one... they're all the same");

All zero? Overflow?

Overflow is not possible, stare at it for a while and see if you can
figure out why

Rather than 'not possible' let me rephrase and say 'not an issue'
unless the values are equal, there must be at least one bit set...
which will in turn cause the statement to work properly.

As far as I understand, overflow/underflow invokes behaviour not covered
by the standard, which may include setting all bits to zero.

[...]

Well, actually I was also responding to the OP question, which as of yet
you had not answered properly

What do you find deficient in my suggestion above, or the alternative
I gave which got snipped:

if ( ((a|b|c|d...z)&a&b&c&d...z) != value )
/* one or more of a,b,c,d...z is not equal to value */
?

I realized what you meant after reading your post a 2nd time... should have
waited a minute before responding, but I do that frequently

I can relate.

[...]

 

[Mark]

[attributions cleaned up and simplified]

Netocrat wrote:
Mark wrote:
Netocrat wrote: [...]

if ( !( ((a|b|c|d...z) == value) && ((a&b&c&d...z) == value) ) )
/* one or more of a,b,c,d...z is not equal to value */ [...]
Albeit ugly, this should work:

if(a-b|b-c|c-d|d-e /* ... */)
puts("mismatched");
else
puts("pick one... they're all the same");

All zero? Overflow?
Overflow is not possible, stare at it for a while and see if you can
figure out why

Rather than 'not possible' let me rephrase and say 'not an issue'
unless the values are equal, there must be at least one bit set...
which will in turn cause the statement to work properly.

As far as I understand, overflow/underflow invokes behaviour not covered
by the standard, which may include setting all bits to zero.

I thought it was covered... no?

H.2.2 Integer types
[#1] The signed C integer types int, long int, long long
int, and the corresponding unsigned types are compatible
with LIA-1. If an implementation adds support for the LIA-1
exceptional values integer_overflow and undefined, then
those types are LIA-1 conformant types. C's unsigned
integer types are ``modulo'' in the LIA-1 sense in that
overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also
being modulo need not detect integer overflow, in which
case, only integer divide-by-zero need be detected.

Maybe I'm misreading something...

[...]

Well, actually I was also responding to the OP question, which as of yet
you had not answered properly

What do you find deficient in my suggestion above, or the alternative
I gave which got snipped:
if ( ((a|b|c|d...z)&a&b&c&d...z) != value )
/* one or more of a,b,c,d...z is not equal to value */

I didn't see this one... it must have been elsethread.
As for deficiency, consider:
a = b = d = f = INT_MAX;
c = -1;


Regarding the one above, I didn't examine it...
The text which followed your suggestion was what prompted me to post.

No that doesn't work. In the case of one variable with a==1, value==1
then a^value is false. I can't see a way to rearrange it using bitwise
or/and to work.

I did see a way to arrange it using a bitwise or, so I posted my solution

Mark

 

[freak]

All what? Learn to quote. The google interface may by broken but it is
possible, and if you had read this (or almost any other group) you would
have seen that it is the done thing.

Search this group for broken google interface and you will see *lots* of
complaints, explanations of the problem, and instructions on how to get
Google to do the right thing.

Learn to think. My post, in any interface was an answer to the subject
line. Read the subject and my post. Still can't figger it out? Ccan't
find the plural word in the subject? Complain away. You are good at it.

 

[Netocrat]

Mark wrote:
Netocrat wrote:
Mark wrote:
Netocrat wrote: [...]

if ( !( ((a|b|c|d...z) == value) && ((a&b&c&d...z) == value) ) )
/* one or more of a,b,c,d...z is not equal to value */ [...]
Albeit ugly, this should work:

if(a-b|b-c|c-d|d-e /* ... */)
puts("mismatched");
else
puts("pick one... they're all the same");

All zero? Overflow?
Overflow is not possible, stare at it for a while and see if you can
figure out why
Rather than 'not possible' let me rephrase and say 'not an issue'
unless the values are equal, there must be at least one bit set...
which will in turn cause the statement to work properly.

OK, as others have pointed out overflow only invokes undefined behaviour
for signed arithmetic, and unsigned arithmetic wraps. So for that reason
and because the bit operators are not portable on signed operands all of
the techniques proposed in this thread are restricted to unsigned
operands. Once that restriction is imposed there is no overflow problem
with your code.

[...]

I didn't see this one... it must have been elsethread. As for
deficiency, consider:
a = b = d = f = INT_MAX;
c = -1;

Signed operands can't portably be used, although assuming no trap
representations I can't see a problem with that particular situation. But
looking at it again, the expression is wrong (and needlessly complicated).
It should rather be:

if ( value != (a&b&c&d...z&value) )
/* one or more of a,b,c,d...z is not equal to value */

[...]

 

[Tim Rentsch]

[snip]
As far as I understand, overflow/underflow invokes behaviour not covered
by the standard, which may include setting all bits to zero.

I thought it was covered... no?

H.2.2 Integer types
[#1] The signed C integer types int, long int, long long
int, and the corresponding unsigned types are compatible
with LIA-1. If an implementation adds support for the LIA-1
exceptional values integer_overflow and undefined, then
those types are LIA-1 conformant types. C's unsigned
integer types are ``modulo'' in the LIA-1 sense in that
overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also
being modulo need not detect integer overflow, in which
case, only integer divide-by-zero need be detected.

Maybe I'm misreading something...

First: Appendix H is informative rather than normative.

Second: The paragraph above only says that signed integer
types *may* behave in a certain way ("An implementation that
defines...", etc). The standard itself says that what
happens when overflow occurs is undefined behavior (6.5 p5).
Indeed, what happens on integer overflow is cited as an
example (3.4.3 p3) in the definition of undefined behavior.

 

[CBFalconer]

.... snip ...

Embarrassingly, my logic circuits have been malfunctioning in this
thread... as evidenced above (the xor code works contrary to my
claim) and here - the code performs correctly for all variables zero.



Perhaps I don't understand the overflow requirements. And perhaps
I should have called it underflow instead of overflow. But by my
understanding, if a and b are unsigned and a == 0 and b > 0, then
the expression (a-b) results in an underflow, which is undefined
behaviour.

Unsigned ints do not overflow. The result is exactly defined by
using modulo arithmetic.

Assuming you want to detect 'all same' vs 'something different',
you can do it with:

if ((a-b) || (b-c) || (c-d) || .... ) different();
else (same)

If the values are in an array A[N] then you can use:

for (unequal = 0, i = 1; i < N; i++) {
if (A |= A[i-1]) {
unequal = 1;
break;
}
}
if (unequal) different();
else same();

and this will function for ints as well as unsigned.

 

[CBFalconer]

Learn to think. My post, in any interface was an answer to the
subject line. Read the subject and my post. Still can't figger
it out? Ccan't find the plural word in the subject? Complain
away. You are good at it.

The point is that in many newsreaders the subject is not easily
available to the reader, and neither are previous messages in the
thread. In fact, they may not be available at all. The cure for
this is to make each article stand by itself. Google users who are
ignorant of normal conventions, and how to implement them on
google, have become a plague on usenet.

Don't be so ready to pick a fight. If you do you will shortly find
yourself killfiled by most of the knowledgeable participants here.

 

[Mark]

[snip]
As far as I understand, overflow/underflow invokes behaviour not
covered
by the standard, which may include setting all bits to zero.

I thought it was covered... no?

H.2.2 Integer types
[#1] The signed C integer types int, long int, long long
int, and the corresponding unsigned types are compatible
with LIA-1. If an implementation adds support for the LIA-1
exceptional values integer_overflow and undefined, then
those types are LIA-1 conformant types. C's unsigned
integer types are ``modulo'' in the LIA-1 sense in that
overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also
being modulo need not detect integer overflow, in which
case, only integer divide-by-zero need be detected.

Maybe I'm misreading something...

First: Appendix H is informative rather than normative.

Second: The paragraph above only says that signed integer
types *may* behave in a certain way

No, it also states that unsigned integer types DO behave a certain way.

("An implementation that
defines...", etc). The standard itself says that what
happens when overflow occurs is undefined behavior (6.5 p5).

It also states that the result will silently wrap...
be it informative or normative... it's still a part of the standard, no?

Indeed, what happens on integer overflow is cited as an
example (3.4.3 p3) in the definition of undefined behavior.

3.18.3 - no? But you do realize that the line to which you
refer is informative rather than normative, don't you?
If not, read the forward again (part 6 to be specific

 

[Mark]

Mark wrote:
Mark wrote:
Netocrat wrote:
Mark wrote:
Netocrat wrote:
[...]

if ( !( ((a|b|c|d...z) == value) && ((a&b&c&d...z) == value) ) )
/* one or more of a,b,c,d...z is not equal to value */
[...]
Albeit ugly, this should work:

if(a-b|b-c|c-d|d-e /* ... */)
puts("mismatched");
else
puts("pick one... they're all the same");

All zero? Overflow?
Overflow is not possible, stare at it for a while and see if you can
figure out why
Rather than 'not possible' let me rephrase and say 'not an issue'
unless the values are equal, there must be at least one bit set...
which will in turn cause the statement to work properly.

OK, as others have pointed out overflow only invokes undefined behaviour
for signed arithmetic, and unsigned arithmetic wraps. So for that reason
and because the bit operators are not portable on signed operands all of
the techniques proposed in this thread are restricted to unsigned
operands. Once that restriction is imposed there is no overflow problem
with your code.

[...]

I didn't see this one... it must have been elsethread. As for
deficiency, consider:
a = b = d = f = INT_MAX;
c = -1;

Signed operands can't portably be used, although assuming no trap
representations I can't see a problem with that particular situation.

The problem is your code doesn't work... try it.
c = (unsigned) -1; can most definately be used... and your code
reports all values as being equal when passed arguments specified.

But
looking at it again, the expression is wrong (and needlessly complicated).
It should rather be:

if ( value != (a&b&c&d...z&value) )
/* one or more of a,b,c,d...z is not equal to value */

Has the same problem as the other...
try setting the values as I specified earlier...
The only example you provided which doesn't choke on it was
the first :Which also happens to be the one you claimed was wrong up-thread!

Regards,
Mark

 

[Netocrat]

[...]
The problem is your code doesn't work... try it. [...]

But looking at it again, the expression is wrong (and needlessly
complicated). It should rather be:

if ( value != (a&b&c&d...z&value) )
/* one or more of a,b,c,d...z is not equal to value */

Has the same problem as the other...

Yes they're both flawed after all. I was attempting to simplify my
original expression that you quote below but apparently the off-the-cuff
simplifications were lacking.

[...]

The only example you provided which doesn't choke on it was
the first :
Which also happens to be the one you claimed was wrong up-thread!

Actually the one I claimed was wrong was the xor solution and I've already
retracted that claim.

 

[Tim Rentsch]

[snip]
As far as I understand, overflow/underflow invokes behaviour not
covered
by the standard, which may include setting all bits to zero.

I thought it was covered... no?

H.2.2 Integer types
[#1] The signed C integer types int, long int, long long
int, and the corresponding unsigned types are compatible
with LIA-1. If an implementation adds support for the LIA-1
exceptional values integer_overflow and undefined, then
those types are LIA-1 conformant types. C's unsigned
integer types are ``modulo'' in the LIA-1 sense in that
overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also
being modulo need not detect integer overflow, in which
case, only integer divide-by-zero need be detected.

Maybe I'm misreading something...

First: Appendix H is informative rather than normative.

Second: The paragraph above only says that signed integer
types *may* behave in a certain way

No, it also states that unsigned integer types DO behave a certain way.

The subject in question is overflow (or underflow), which
usually is understood to refer to signed integer types rather
than unsigned integer types. This understanding is consistent
with the wording of the standard, "A computation involving
unsigned operands can never overflow," 6.2.5 p9. If what is
being talked about is overflow -- which I think is a reasonable
assumption considering the context -- then the relevant portion
of the cited H.2.2 is only that about signed integer types.

It also states that the result will silently wrap...

6.5 p5 does not say that. H.2.2 says for unsigned integer
types that overflows "silently wrap" (presumably in the sense
of LIA-1, since the C standard itself uses different wording).
Neither 6.5 p5 nor H.2.2 says for signed integer types that
overflow results must "silently wrap"; for 6.5 p5, to the
contrary:

If an <i>exceptional condition</i> occurs during the
evaluation of an expression (that is, the result is
not mathematically defined or not in the range of
representable values for its type), the behavior is
undefined.

"Not in the range of representable values" is synonymous
with overflow (or underflow) for signed integer types.

be it informative or normative... it's still a part of
the standard, no?

Normative text takes precedence over informative text.

3.18.3 - no?

In my document [ISO/IEC 9899:1999 (E)], 3.18 is a definition of
the ceiling function. Section 3.4 defines different kinds of
behaviors, with 3.4.3 defining "undefined behavior". I don't
know what document you have.

But you do realize that the line to which you
refer is informative rather than normative, don't you?
If not, read the forward again (part 6 to be specific

The text in 6.5 p5 is normative. The combination of an explicit
statement of undefined behavior in 6.5 p5, and being used as
_the_ definitional example (even if Examples are informative
rather than normative text) in 3.4.3 p3, makes a pretty strong
argument that overflow is undefined behavior; and that the text
in H.2.2 is talking (to be explicit, for signed integer types)
only about some implementations, not all implementations.

"An implementation that defines signed integer types as also
being modulo ..." is simply one way that the undefined behavior
of overflow may manifest. Another implementation could just as
well choose to always return zero, or all 1 bits, or a trap
representation that caused the computer to catch fire if stored
in location 0xDEADBEEF... etc.

 

[Mark]

[snip]
As far as I understand, overflow/underflow invokes behaviour not
covered
by the standard, which may include setting all bits to zero.

I thought it was covered... no?

H.2.2 Integer types
[#1] The signed C integer types int, long int, long long
int, and the corresponding unsigned types are compatible
with LIA-1. If an implementation adds support for the LIA-1
exceptional values integer_overflow and undefined, then
those types are LIA-1 conformant types. C's unsigned
integer types are ``modulo'' in the LIA-1 sense in that
overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also
being modulo need not detect integer overflow, in which
case, only integer divide-by-zero need be detected.

Maybe I'm misreading something...

First: Appendix H is informative rather than normative.

Second: The paragraph above only says that signed integer
types *may* behave in a certain way

No, it also states that unsigned integer types DO behave a certain way.

The subject in question is overflow (or underflow), which
usually is understood to refer to signed integer types rather
than unsigned integer types.

Then why are we having this discussion?

This understanding is consistent
with the wording of the standard, "A computation involving
unsigned operands can never overflow," 6.2.5 p9.

Then I was correct in my initial statement that in my example
'Overflow is not possible.' - I was concerned after seeing H.2.2 that
my statement was incorrect, so I ammended it to 'not an issue'.
I now retract my ammended statement and stand by my original claim.
Thanks for the citation.

If what is
being talked about is overflow -- which I think is a reasonable
assumption considering the context -- then the relevant portion
of the cited H.2.2 is only that about signed integer types.

But we have been dealing with bit operands the entire time,
so considering the context you should assume we are
dealing with unsigned integer types, no? I have been... which again
is why I earlier stated that 'overflow is not possible'.

It also states that the result will silently wrap...

6.5 p5 does not say that. H.2.2 says for unsigned integer
types that overflows "silently wrap" (presumably in the sense
of LIA-1, since the C standard itself uses different wording).
Neither 6.5 p5 nor H.2.2 says for signed integer types that
overflow results must "silently wrap"; for 6.5 p5, to the
contrary:

If an <i>exceptional condition</i> occurs during the
evaluation of an expression (that is, the result is
not mathematically defined or not in the range of
representable values for its type), the behavior is
undefined.

"Not in the range of representable values" is synonymous
with overflow (or underflow) for signed integer types.

be it informative or normative... it's still a part of
the standard, no?

Normative text takes precedence over informative text.

3.18.3 - no?

In my document [ISO/IEC 9899:1999 (E)], 3.18 is a definition of
the ceiling function.

Impossible, there is no such function in the C language.
I assume you are referring to the 'ceil' functions?
7.12.9.1 in my text... I am using the last version of the committee draft

Section 3.4 defines different kinds of
behaviors, with 3.4.3 defining "undefined behavior". I don't
know what document you have.

Nor do I know what you are reading if it truly defines a 'ceiling' function.

Regards,
Mark