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

[Ricky]

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

 

[Andrew Poelstra]

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;

 

[Seebs]

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

 

[Ersek, Laszlo]

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 "!"?

/* 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]

/* 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;

Tom

 

[Ersek, Laszlo]

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]

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