Re: Bitwise XOR in Lua?

[Paul Hsieh <qed@...>]

> > Thanks!  However, it would be ideal if I didn't have to (re)compile
> > anything, as the code that uses the function needs to be portable, and some
> > of the target platforms don't have compilers available.  Is there a way to
> > implement it in "pure" Lua?
> 
> How do you get Lua on the machines without a compiler?
> 
> You can implement XOR in pure Lua but it's very slow. Probably the easiest 
> way is to do it bit by bit, but maybe there's a clever trick to do it 
> faster with whole-word arithmetic.

Well, off the top of my head here are some ideas:

1. Use a small look-up table to handle more bits at a time.  You can generate the
   table from even smaller tables, so you don't import a huge table or anything like
   that.  A nice size would be 4-bits per operand.  You could then even unroll the
   loop, and it would probably still be acceptable.

2. Observe the following:

   A + B = (A and B)*2 + (A xor B)

   Which creates a simple relationship between "and" and "xor".  So you only need to
   compute one or the other.

   not A = -A - 1

   So using deMorgan's laws you can get a simple relationship for "or" to.  Oh yes
   and don't forget:

   -1 xor A = not A


--
Paul Hsieh
qed@pobox.com