[GAP Forum] Bitwise operators

[Jean-Claude Arbaut]

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