[GAP Forum] Bitwise operators
Jean-Claude Arbaut
jeanclaudearbaut at orange.fr
Tue Dec 2 18:29:16 GMT 2014
Hello all,
There was a question a few years ago about bitwise operators in GAP - in
february 2010, see here:
http://mail.gap-system.org/pipermail/forum/2010/002701.html
At that time, it seems GAP didn't have these, I wonder if things have
changed since. If so, could somebody point me to the manual for them?
Otherwise, here is an attempt to convince the reader they are indeed
necessary.
The answer back then was that the representation was not consistent with
bitwise operators. However, these operators are defined on the integers,
independently of any representation. Like addition, subtraction,
multiplication, and division.
They just happen to be easier to compute when the numbers are written in
binary, but it should not be a concern. For example, languages such as
Python, Common Lisp or Mathematica implement bitwise operators on big
integers, without a problem.
Now, there may be some reasons to want them in GAP. "Groups, Algorithms,
Programming"? But many algorithms use bitwise operators. Anderson's Bit
Twiddling Hacks (https://graphics.stanford.edu/~seander/bithacks.html)
and Warren's book Hacker's Delight show many examples usable at the
assembly programming level. Their use to compute Gray code is also
rather well known
(http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code).
Here is another example I found recently (another well known
application, it seems): when implementing Lucas-Lehmer test for Mersenne
primes, it's possible to eliminate division and replace it with a few
bitwise ops. See here for example:
http://rosettacode.org/wiki/Talk:Lucas-Lehmer_test#Speeding_things_up
The speed is highly improved, as one might guess (bitwise ops are
usually O(n), division is much harder).
Now, I hope I have shown some good reasons to include bitwise operators
in the language, if they are not already here :-)
Best regards,
Jean-Claude Arbaut
More information about the Forum
mailing list