[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Bitwise XOR in Lua?**
**From**: Paul Hsieh <qed@...>
**Date**: Mon, 09 Sep 2002 12:03:19 -0700

> > 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