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

Groups > comp.programming > #9218 > unrolled thread

Simpler way to dp binary logical operation using arithmetic?

Back to article view | Back to comp.programming

Contents

  Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-10 22:56 +0700
    Re: Simpler way to dp binary logical operation using arithmetic? Julio Di Egidio <julio@diegidio.name> - 2018-09-10 09:30 -0700
      Re: Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-11 02:13 +0700
        Re: Simpler way to dp binary logical operation using arithmetic? Julio Di Egidio <julio@diegidio.name> - 2018-09-10 14:21 -0700
    Re: Simpler way to dp binary logical operation using arithmetic? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2018-09-10 18:32 +0200
      Re: Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-11 02:26 +0700
        Re: Simpler way to dp binary logical operation using arithmetic? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2018-09-10 22:00 +0200
          Re: Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-11 03:22 +0700
    Re: Simpler way to dp binary logical operation using arithmetic? David Brown <david.brown@hesbynett.no> - 2018-09-10 18:50 +0200
      Re: Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-11 03:02 +0700
        Re: Simpler way to dp binary logical operation using arithmetic? nobody@example.org (Scott) - 2018-09-11 15:24 +0000
    Re: Simpler way to dp binary logical operation using arithmetic? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-09-10 18:59 +0100
      Re: Simpler way to dp binary logical operation using arithmetic? JJ <jj4public@vfemail.net> - 2018-09-11 03:08 +0700

#9218 — Simpler way to dp binary logical operation using arithmetic?

I'm using a programming language which is pretty limited. FYI, it's part of
an Android automation application. It has a custom syntax which is similar
to Java.

I want to perform binary logical operations such as NOT, OR, and AND. While
the language does support logical operators, they're only applicable for
boolean value types. They're not applicable for integers. e.g. in a full
featured programming language, below code is possible.

    value1 = 0xA5;
    value2 = 0x5A;
    result = value1 | value2;
    //result is 0xFF

However, in the Android application that I use, it cause an error saying
that `value1` or `value2` can not be converted to boolean. Meaning that the
`|` operator only works on boolean types.

The only thing I could think of to achieve this is to extract each bit one
by one from each two values by using the modulo operator, manually perform
the bitwise logical operation using `if` statement on each bit one by one,
then pack the separated bit values back into one value. e.g.

    //extract all bits of the first value...
    value1bit0 = value1 % 2;
    value1reminder = value1 \ 2; //"\" operator is an integer division
    value1bit1 = value1reminder % 2;
    value1reminder = value1reminder \ 2;
    //etc. up to 31th or 63th bit

    //extract all bits of the second value...
    value2bit0 = value2 % 2;
    value2reminder = value2 \ 2;
    //etc.

    //perform a bitwise OR operation...
    if (value1bit0 || value2bit0) {
      resultbit0 = 1;
    } else resultbit0 = 0;
    if (value1bit1 || value2bit1) {
      resultbit1 = 1;
    } else resultbit1 = 0;
    //etc. up to 31th or 63th bit...
    //this can be simplified using an array,
    //but simple code is used to make it simpler to understand

    //pack the bit values back to one value...
    result = resultbit0 || (resultbit1 * 2) || (resultbit2 * 4) ||
             (resultbit3 * 2) || (resultbit4 * 4) || (resultbit5 * 4) ||
             //etc. up to 31th or 63th bit...

Aa you can see, the above code is pretty long.

So, my question is: is there a simpler way to do this? Preferably, without
extracting/repacking the bits, and performing the bitwise logical operation
one bit at a time.

[toc] | [next] | [standalone]

#9219

On Monday, 10 September 2018 17:56:39 UTC+2, JJ  wrote:

>     //pack the bit values back to one value...
>     result = resultbit0 || (resultbit1 * 2) || (resultbit2 * 4) ||
>              (resultbit3 * 2) || (resultbit4 * 4) || (resultbit5 * 4) ||
>              //etc. up to 31th or 63th bit...

So you have bitwise OR or don't you??  Indeed, I'd expect || to be the Boolean
OR, so that code makes little sense anyway...

> So, my question is: is there a simpler way to do this? Preferably, without
> extracting/repacking the bits, and performing the bitwise logical operation
> one bit at a time.

Short answer, no (except for NOT and SHIFTs), but you don't need to extract/
repack the bits:

<https://en.wikipedia.org/wiki/Bitwise_operation#Mathematical_equivalents>

Julio

[toc] | [prev] | [next] | [standalone]

#9229

On Mon, 10 Sep 2018 09:30:11 -0700 (PDT), Julio Di Egidio wrote:
>>     //pack the bit values back to one value...
>>     result = resultbit0 || (resultbit1 * 2) || (resultbit2 * 4) ||
>>              (resultbit3 * 2) || (resultbit4 * 4) || (resultbit5 * 4) ||
>>              //etc. up to 31th or 63th bit...
> 
> So you have bitwise OR or don't you??  Indeed, I'd expect || to be the Boolean
> OR, so that code makes little sense anyway...

Oh, sorry. That suppose to be the `+` operator. Not `||` or `|`.

> Short answer, no (except for NOT and SHIFTs), but you don't need to extract/
> repack the bits:
> 
> <https://en.wikipedia.org/wiki/Bitwise_operation#Mathematical_equivalents>

I'm not really good at math. But the equations seems to apply the operation
one bit at a time. Considering that they use "mod 2".

[toc] | [prev] | [next] | [standalone]

#9239

On Monday, 10 September 2018 21:13:40 UTC+2, JJ  wrote:
> On Mon, 10 Sep 2018 09:30:11 -0700 (PDT), Julio Di Egidio wrote:
<snip>
> > Short answer, no (except for NOT and SHIFTs), but you don't need to extract/
> > repack the bits:
> > 
> > <https://en.wikipedia.org/wiki/Bitwise_operation#Mathematical_equivalents>
> 
> I'm not really good at math. But the equations seems to apply the operation
> one bit at a time. Considering that they use "mod 2".

It's not so much the mod 2, it's the number of terms in the summation.  But
I was referring to the fact that you don't need additional loops to unpack
and repack the single digits (or the single bytes, etc.), one loop suffices
to do the whole operation.

But definitely yes, as suggested by others, you may optimise it by rather
looping over bytes, or more generally over groups of bits, where operations
on the single group have been tabled.  But the mathematical formulas remain
essentially the same, just looping for the number of -say- bytes, and not
anymore using mod 2 but mod 2^8, etc...

Julio

[toc] | [prev] | [next] | [standalone]

#9220

On 2018-09-10 17:56, JJ wrote:

> So, my question is: is there a simpler way to do this? Preferably, without
> extracting/repacking the bits, and performing the bitwise logical operation
> one bit at a time.

You mean on 2nd complement integer? You could use

    not x = -x - 1

provided, you can suppress overflows.

The easiest way is to use a byte or character array and tabulate bitwise 
operations on bytes/characters.

A table of a binary operation is 256x256 = 64K long, which is not much. 
For commutative operations (and, or, xor) you can furthermore reduce the 
table down to 32K by reordering operands.

P.S. Does your language support interfacing to C?

P.P.S. Does your language support assembly code insertions?

P.P.P.S. What about a language that has modulo 2**n numbers AKA binary 
unsigned numbers. Bitwise operations are defined on them.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#9231

On Mon, 10 Sep 2018 18:32:58 +0200, Dmitry A. Kazakov wrote:
> 
> You mean on 2nd complement integer? You could use
> 
>     not x = -x - 1
> 
> provided, you can suppress overflows.

Oh, right. I forgot that I already know it. Sorry. And thank you.

> The easiest way is to use a byte or character array and tabulate bitwise 
> operations on bytes/characters.
> 
> A table of a binary operation is 256x256 = 64K long, which is not much. 
> For commutative operations (and, or, xor) you can furthermore reduce the 
> table down to 32K by reordering operands.

I also forgot to mention I already know about this. However, using a lookup
table is still a bit tedious. It's within my consideration, though.

> P.S. Does your language support interfacing to C?
> 
> P.P.S. Does your language support assembly code insertions?

No for both. It's an interpreter based application. It can't load any
external libraries by file name.

It can use Java classes. e.g. create a new object from a Java class, call
its method, or call a static method of a Java class.

> P.P.P.S. What about a language that has modulo 2**n numbers AKA binary 
> unsigned numbers. Bitwise operations are defined on them.

I'm not sure what you meant, sorry. The only supported modulo operation is
the `%` operator.

The application doesn't support any bitwise operation at all. It's pretty
limited, really. It doesn't support bit shifting operators. It doesn't even
support custom function. i.e. it's not possible to create my own function.

[toc] | [prev] | [next] | [standalone]

#9234

On 2018-09-10 21:26, JJ wrote:
> On Mon, 10 Sep 2018 18:32:58 +0200, Dmitry A. Kazakov wrote:

>> P.P.P.S. What about a language that has modulo 2**n numbers AKA binary
>> unsigned numbers. Bitwise operations are defined on them.
> 
> I'm not sure what you meant, sorry. The only supported modulo operation is
> the `%` operator.

Modular arithmetic is like this:

    1 + 0 = 1 (mod 3)
    1 + 1 = 2 (mod 3)
    1 + 2 = 0 (mod 3)
    1 + 3 = 1 (mod 3)
    1 + 4 = 2 (mod 3)
    1 + 5 = 0 (mod 3)

etc.

See

    https://en.wikipedia.org/wiki/Modular_arithmetic

Bitwise operations are mathematically defined only on power of 2 modulo. 
This kind of arithmetic has nothing to do with integer arithmetic except 
for sharing numerals, names of operations, some properties of 
corresponding operations.

Decent languages have different numeric types for modular integers and 
"normal" integers.

> The application doesn't support any bitwise operation at all. It's pretty
> limited, really. It doesn't support bit shifting operators.

Arithmetic shift by n in modular arithmetic of modulo of power of 2 is 
equivalent to multiplication by 2**n (in both arithmetics), provided you 
can suppress integer overflows.

> It doesn't even
> support custom function. i.e. it's not possible to create my own function.

Why do you bother with that then? (:-)) Life is too short... (:-()

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#9238

On Mon, 10 Sep 2018 22:00:08 +0200, Dmitry A. Kazakov wrote:
> 
> Why do you bother with that then? (:-)) Life is too short... (:-()

Believe it or not, IMO, so far, it's the only Android automation application
which has most freedom for its scripting.

[toc] | [prev] | [next] | [standalone]

#9222

On 10/09/18 17:56, JJ wrote:
> I'm using a programming language which is pretty limited. FYI, it's part of
> an Android automation application. It has a custom syntax which is similar
> to Java.
> 
> I want to perform binary logical operations such as NOT, OR, and AND. While
> the language does support logical operators, they're only applicable for
> boolean value types. They're not applicable for integers. e.g. in a full
> featured programming language, below code is possible.
> 

You seem to be a little muddled here.  Let's rewind a little.

There are two sorts of AND/OR/NOT operations - logical (boolean) 
operations, and bitwise operations.  In C and Java, the logical 
operations are &&, || and !, while the bitwise ones are &, | and ~.  I 
will stick to those here, although there is no guarantee that your 
language has these.

Logical operations operate on boolean values.  In many languages, they 
are allowed for integers too - an integer value of 0 counts as "false" 
and non-zero counts as "true".  So you get:

	0x12 && 0x55		// true

Bitwise operations operate on integers (preferably unsigned integers), 
and are done a bit at a time.  So you get:

	0x12 & 0x55		// 0x10

If your language supports bitwise operations (suggested by your code 
below) but not logical operations, then the logical versions are easy to 
simulate.  To get "x & y" you use:

	(x != 0) & (y != 0)	// Same as "x && y"
	(x != 0) | (y != 0)	// Same as "x || y"
	(x == 0)		// Same as "!x"

If your language supports logical operations, but not bitwise 
operations, then it is harder to make the bitwise operations manually. 
Try something like this (structured for clarity and flexibility) :

uint8_t bitwise_and8(uint8_t x, uint8_t y) {
	uint8_t z = 0;
	for (int n = 0; n < 8; n++) {
		z = z * 2;

		bool bitX;
		bool bitY;
		if (x >= 0x80) {
			bitX = true;
			x -= 0x80;
		} else {
			bitX = false;
		}
		if (y >= 0x80) {
			bitY = true;
			y -= 0x80;
		} else {
			bitY = false;
		}
		if (bitX && bitY) {
			z += 1;
		}
		
		x = x / 2;
		y = y / 2;
	}
	return z;
}

That only uses simple operations found in most programming languages. 
If you need larger sizes, you can use a longer loop.  And the extensions 
to "or" and "xor" are obvious.





>      value1 = 0xA5;
>      value2 = 0x5A;
>      result = value1 | value2;
>      //result is 0xFF
> 
> However, in the Android application that I use, it cause an error saying
> that `value1` or `value2` can not be converted to boolean. Meaning that the
> `|` operator only works on boolean types.
> 
> The only thing I could think of to achieve this is to extract each bit one
> by one from each two values by using the modulo operator, manually perform
> the bitwise logical operation using `if` statement on each bit one by one,
> then pack the separated bit values back into one value. e.g.
> 
>      //extract all bits of the first value...
>      value1bit0 = value1 % 2;
>      value1reminder = value1 \ 2; //"\" operator is an integer division
>      value1bit1 = value1reminder % 2;
>      value1reminder = value1reminder \ 2;
>      //etc. up to 31th or 63th bit
> 
>      //extract all bits of the second value...
>      value2bit0 = value2 % 2;
>      value2reminder = value2 \ 2;
>      //etc.
> 
>      //perform a bitwise OR operation...
>      if (value1bit0 || value2bit0) {
>        resultbit0 = 1;
>      } else resultbit0 = 0;
>      if (value1bit1 || value2bit1) {
>        resultbit1 = 1;
>      } else resultbit1 = 0;
>      //etc. up to 31th or 63th bit...
>      //this can be simplified using an array,
>      //but simple code is used to make it simpler to understand
> 
>      //pack the bit values back to one value...
>      result = resultbit0 || (resultbit1 * 2) || (resultbit2 * 4) ||
>               (resultbit3 * 2) || (resultbit4 * 4) || (resultbit5 * 4) ||
>               //etc. up to 31th or 63th bit...
> 
> Aa you can see, the above code is pretty long.
> 
> So, my question is: is there a simpler way to do this? Preferably, without
> extracting/repacking the bits, and performing the bitwise logical operation
> one bit at a time.
> 

[toc] | [prev] | [next] | [standalone]

#9235

On Mon, 10 Sep 2018 18:50:20 +0200, David Brown wrote:
> 
> You seem to be a little muddled here.  Let's rewind a little.
> 
> There are two sorts of AND/OR/NOT operations - logical (boolean) 
> operations, and bitwise operations.  In C and Java, the logical 
> operations are &&, || and !, while the bitwise ones are &, | and ~.  I 
> will stick to those here, although there is no guarantee that your 
> language has these.

Ah, sorry for the mix up.

The application supports all logical/boolean operators.
i.e. it has &&, ||, !, and ^

It doesn't support any bitwise operators at all.
i.e. it has no &, |, and ~

> Logical operations operate on boolean values.  In many languages, they 
> are allowed for integers too - an integer value of 0 counts as "false" 
> and non-zero counts as "true".  So you get:
> 
> 	0x12 && 0x55		// true

This would be invalid in the application. Logical/boolean operators are
strictly for boolean type.

> Bitwise operations operate on integers (preferably unsigned integers), 
> and are done a bit at a time.  So you get:
> 
> 	0x12 & 0x55		// 0x10

This is also invalid. The bitwise & operator is not supported.

> If your language supports bitwise operations (suggested by your code 
> below) but not logical operations, then the logical versions are easy to 
> simulate.  To get "x & y" you use:
> 
> 	(x != 0) & (y != 0)	// Same as "x && y"
> 	(x != 0) | (y != 0)	// Same as "x || y"
> 	(x == 0)		// Same as "!x"

This won't work in the application.  Because the & and | operators are not
supported.

> If your language supports logical operations, but not bitwise 
> operations, then it is harder to make the bitwise operations manually. 
> Try something like this (structured for clarity and flexibility) :

Well, that's similar to the one I have done. i.e. it's done one bit at a
time.

I was hoping if there's math equation(s) to apply bitwise operation for the
whole e.g. 8-bits, 16-bits, etc.

Kind of like the algorithm which uses multiplication to perform a division.
What's it called? Reciprocal division? Not that I meant to use it for this
bitwise operations.

[toc] | [prev] | [next] | [standalone]

#9245

On Tue, 11 Sep 2018 03:02:59 +0700, JJ <jj4public@vfemail.net> wrote:

>I was hoping if there's math equation(s) to apply bitwise operation for the
>whole e.g. 8-bits, 16-bits, etc.
>
>Kind of like the algorithm which uses multiplication to perform a division.
>What's it called? Reciprocal division? Not that I meant to use it for this
>bitwise operations.

You mean a procedure whereby simple operations are performed
repeatedly in order to achieve a more complex operation? That's how
you do multiplication and division when they're not built in. That's
also how you do bit bashing when it's not built in. Won't be pretty,
but it'll work.

If there was an easy answer, nobody would have bothered to invent bit
bashing operators.

[toc] | [prev] | [next] | [standalone]

#9225

JJ <jj4public@vfemail.net> writes:

> I'm using a programming language which is pretty limited. FYI, it's part of
> an Android automation application. It has a custom syntax which is similar
> to Java.
>
> I want to perform binary logical operations such as NOT, OR, and AND. While
> the language does support logical operators, they're only applicable for
> boolean value types.
<snip>
> The only thing I could think of to achieve this is to extract each bit one
> by one from each two values by using the modulo operator, manually perform
> the bitwise logical operation using `if` statement on each bit one by one,
> then pack the separated bit values back into one value. e.g.
>
>     //extract all bits of the first value...
>     value1bit0 = value1 % 2;
>     value1reminder = value1 \ 2; //"\" operator is an integer division
>     value1bit1 = value1reminder % 2;
>     value1reminder = value1reminder \ 2;
>     //etc. up to 31th or 63th bit
>
>     //extract all bits of the second value...
>     value2bit0 = value2 % 2;
>     value2reminder = value2 \ 2;
>     //etc.
>
>     //perform a bitwise OR operation...
>     if (value1bit0 || value2bit0) {
>       resultbit0 = 1;
>     } else resultbit0 = 0;
>     if (value1bit1 || value2bit1) {
>       resultbit1 = 1;
>     } else resultbit1 = 0;
>     //etc. up to 31th or 63th bit...
>     //this can be simplified using an array,
>     //but simple code is used to make it simpler to understand
>
>     //pack the bit values back to one value...
>     result = resultbit0 || (resultbit1 * 2) || (resultbit2 * 4) ||
>              (resultbit3 * 2) || (resultbit4 * 4) || (resultbit5 * 4) ||
>              //etc. up to 31th or 63th bit...
>
> Aa you can see, the above code is pretty long.
>
> So, my question is: is there a simpler way to do this? Preferably, without
> extracting/repacking the bits, and performing the bitwise logical operation
> one bit at a time.

You could use a look-up table and do it a few bit at a time, the number
dependent on how large a table you are prepared to have.  (I think this has
already been suggested.)

But however you do it, it's probably worth "programming" it rather than
writing it out as above.  For example, in C:

  unsigned bitwise_or(unsigned a, unsigned b)
  {
       unsigned or[2][2] = {{0, 1}, {1, 1}};
       return a == 0 ? b : b == 0 ? a : bitwise_or(a/2, b/2) * 2 + or[a%2][b%2];
  }

In C one would usually just add (a%2 || b%2) at the end, but you won't
be able to do that in the language you are using so I've used a little
table.  Though there are other ways, the table shows how you can extend
this method to working with more bits at a time.  For example:

  unsigned bitwise_or(unsigned a, unsigned b)
  {
       unsigned or[4][4] = {
            {0, 1, 2, 3},
            {1, 1, 3, 3},
            {2, 3, 2, 3},
            {3, 3, 3, 3}
       }; 
       return a == 0 ? b : b == 0 ? a : bitwise_or(a/4, b/4) * 4 + or[a%4][b%4];
  }

If you point readers to a reference for the language you are using we
could see if something else suggests itself, but also I could check how
to actually write the above in that language.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#9237

On Mon, 10 Sep 2018 18:59:27 +0100, Ben Bacarisse wrote:
> 
> You could use a look-up table and do it a few bit at a time, the number
> dependent on how large a table you are prepared to have.  (I think this has
> already been suggested.)

Yes, a lookup table is already in my consideration as I mentioned in my
reply to Dmitry A. Kazakov.

> If you point readers to a reference for the language you are using we
> could see if something else suggests itself, but also I could check how
> to actually write the above in that language.

The Android application is called "Automagic".

Below is the help section for its programming language.

http://automagic4android.com/en/help/components-actions#action_script

I should have mentioned this in the OP, sorry.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web