Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: Simpler way to dp binary logical operation using arithmetic?
Date: Mon, 10 Sep 2018 18:59:27 +0100
Organization: A noiseless patient Spider
Lines: 84
Message-ID: <87k1ntcjy8.fsf@bsb.me.uk>
References: <bx7o6lmzra8t.mz0g7tl4wryj.dlg@40tude.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="5abc294d3a8d593037ebd4adc5ba4a09"; logging-data="3953"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+y91KoG7AmZ/berK9XV+XEJOEqq8lKdM4="
Cancel-Lock: sha1:lZFrsLVjJeiZxe/jxw9Gg/Qs7es= sha1:6jr7QG1iX9TaaoXfneDIrfEoTPI=
X-BSB-Auth: 1.4ba0e4a374d808d5f512.20180910185927BST.87k1ntcjy8.fsf@bsb.me.uk
Xref: csiph.com comp.programming: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.