[GAP Forum] Bitwise operations

Johannes Hahn johannes.hahn at uni-jena.de
Tue Sep 11 18:50:54 BST 2012


Dear forum,

I have a graph whose vertices are subsets of some fixed finite set S, 
maybe {1,...,n} or {0,...,n-1} or something like that. Now I want to 
write a function that, given n, outputs the adjacency matrix of this 
graph. In particular this would be a 2^n by 2^n matrix. Now matrices are 
indexed by integers. In any normal programming language I would just use 
integers from 0 to 2^n-1 and bitwise operations to translate from sets 
to integers. Is there a reasonable way to do that in GAP?
I know there are bit-lists that can be used to simulate sets, but there 
seems to be no method to convert integers to bit-lists and vice-versa. 
Of course I could implement that by myself, but that seems to be a total 
waste as this is really a no-cost-operation (if I understand the GAP 
manual correctly the internal representation of bit-lists are just 
integers, so there is really nothing to convert here) while a manual 
implementation by iterated integer division by 2 has a nontrivial cost.
Since I not only want to use integers to enumerate subsets of S that one 
time but instead switching back and forth between sets and integers all 
the time (e.g. to use the total ordering of the power set of S that is 
induced by this bijection), I'd really prefer no-cost-operations.

Is there an elegant way to do this, maybe with some undocumented functions?


Johannes Hahn.



More information about the Forum mailing list