how to implement logical equivalence (==) or negation (!) using only binary operators

Ricky

unread,

Apr 14, 2010, 6:48:18 PM4/14/10

to

how to implement logical equivalence (==) or negation (!) for binary
numbers using only binary operators such as ~ & ^ | + << >>?

Andrew Poelstra

unread,

Apr 14, 2010, 7:25:10 PM4/14/10

to

On 2010-04-14, Ricky <rick...@gmail.com> wrote:
> how to implement logical equivalence (==) or negation (!) for binary
> numbers using only binary operators such as ~ & ^ | + << >>?

/*
* int compare(int, int):
* compares two numbers and returns 1 if they are equal
*/

#include <limits.h>

int compare(int a, int b) {
unsigned int values[UINT_MAX];
unsigned int idx;
unsigned int ua = a,
ub = b;
int zcount = 0;

if(ua < 1 || ub < 1)
ua += 73, ub += 73;

for(idx = 0; idx < UINT_MAX; ++idx)
values[idx] = idx;
for(idx = 0; idx < UINT_MAX; ++idx)
values[idx] ^= ua;
for(idx = 0; idx < UINT_MAX; ++idx)
values[idx] ^= ub;

for(idx = 0; idx < UINT_MAX; ++idx)
if(values[idx] < 1)
if(values[idx] > -1)
++zcount;

return zcount + 1;
}

This code is untested because I do not have enough memory.

To do the opposite test, replace the last line with:
return zcount - 1;

--
Andrew Poelstra
http://www.wpsoftware.net/andrew

Seebs

unread,

Apr 14, 2010, 7:55:53 PM4/14/10

to

On 2010-04-14, Ricky <rick...@gmail.com> wrote:

> how to implement logical equivalence (==) or negation (!) for binary
> numbers using only binary operators such as ~ & ^ | + << >>?

I think you'd have to combine some of those operators.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Kenneth Brody

unread,

Apr 14, 2010, 10:47:47 PM4/14/10

to

On 4/14/2010 6:48 PM, Ricky wrote:
> how to implement logical equivalence (==) or negation (!) for binary
> numbers using only binary operators such as ~& ^ | +<< >>?

I would just use "==" and "!".

However, consider:

0 xor 0 == 0
0 xor 1 == 1
1 xor 0 == 1
1 xor 1 == 0

Note the properties:

Xor returns 0 iff the bits are the same.

If you xor with 1, you "toggle" the bit.

How could you use these properties to emulate "==" and "!"?

--
Kenneth Brody

Ersek, Laszlo

unread,

Apr 15, 2010, 5:27:24 AM4/15/10

to

/* Return 1u if any bit is set in "x", return 0u otherwise. */
unsigned
mig32(uint32_t x)
{
x |= x >> 16; /* "condensed" to bits 15 .. 0 */
x |= x >> 8; /* "condensed" to bits 7 .. 0 */
x |= x >> 4; /* "condensed" to bits 3 .. 0 */
x |= x >> 2; /* "condensed" to bits 1 .. 0 */
x |= x >> 1; /* "condensed" to bit 0 */
return x & 1u;
}

{
uint32_t a, b;

/* ... */

mig32(a) ^ 1u; /* boolean-neg */
mig32(a) ^ mig32(b) ^ 1u; /* boolean-eq; IOW, negated boolean-neq */
}

Cheers,
lacos

Tom St Denis

unread,

Apr 15, 2010, 10:01:09 AM4/15/10

to

I'm sure you meant mig32(a^b)^1;

Tom

Ersek, Laszlo

unread,

Apr 15, 2010, 2:43:24 PM4/15/10

to

On Thu, 15 Apr 2010, Tom St Denis wrote:

> On Apr 15, 5:27ďż˝am, "Ersek, Laszlo" <la...@caesar.elte.hu> wrote:

>> /* Return 1u if any bit is set in "x", return 0u otherwise. */
>> unsigned
>> mig32(uint32_t x)
>> {

>> ďż˝ ďż˝x |= x >> 16; /* "condensed" to bits 15 .. 0 */
>> ďż˝ ďż˝x |= x >> ďż˝8; /* "condensed" to bits ďż˝7 .. 0 */
>> ďż˝ ďż˝x |= x >> ďż˝4; /* "condensed" to bits ďż˝3 .. 0 */
>> ďż˝ ďż˝x |= x >> ďż˝2; /* "condensed" to bits ďż˝1 .. 0 */
>> ďż˝ ďż˝x |= x >> ďż˝1; /* "condensed" to bit 0 */
>> ďż˝ ďż˝return x & 1u;
>>
>> }
>>
>> {
>> ďż˝ ďż˝uint32_t a, b;
>>
>> ďż˝ ďż˝/* ... */
>>
>> ďż˝ ďż˝mig32(a) ^ 1u; ďż˝ ďż˝ ďż˝ ďż˝ ďż˝ ďż˝/* boolean-neg */
>> ďż˝ ďż˝mig32(a) ^ mig32(b) ^ 1u; /* boolean-eq; IOW, negated boolean-neq */

> I'm sure you meant mig32(a^b)^1;

I didn't think of that, but if

{
uint32_t a, b;

a = 1u;
b = 2u;
}

Then "a" and "b" are logically equivalent (both compare unequal to 0 --
both are "true"), but

mig32(1u ^ 2u) ^ 1u

yields 0.

AIUI, we're checking for

(0 == a) == (0 == b)

not

a == b

Cheers,
lacos

Phil Carmody

unread,

Apr 15, 2010, 4:19:07 PM4/15/10

to

Andrew Poelstra <apoe...@localhost.localdomain> writes:
> On 2010-04-14, Ricky <rick...@gmail.com> wrote:
>> how to implement logical equivalence (==) or negation (!) for binary
>> numbers using only binary operators such as ~ & ^ | + << >>?

Presumably that should be 'bitwise', not 'binary'.

> /*
> * int compare(int, int):
> * compares two numbers and returns 1 if they are equal
> */
>
> #include <limits.h>
>
> int compare(int a, int b) {
> unsigned int values[UINT_MAX];
> unsigned int idx;
> unsigned int ua = a,

not a bitwise operator.

> ub = b;
> int zcount = 0;
>
> if(ua < 1 || ub < 1)

again, not bitwise

> ua += 73, ub += 73;

also not bitwise.

Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1

io_x

unread,

Apr 16, 2010, 12:32:55 PM4/16/10

to

"Kenneth Brody" <kenb...@spamcop.net> ha scritto nel messaggio
news:Hfudnap-k5_P41vW...@bestweb.net...

if you know how write operator "!"
tha a==b <=>[in C sense] !(a^b)