[GAP Forum] Bitwise operations

Stephen Linton sal at cs.st-andrews.ac.uk
Tue Sep 11 20:06:45 BST 2012


Dear Johannes,

It would help us to answer your question to know roughly how large n is. Could you give us an idea?

	Thanks

		Steve

On 11 Sep 2012, at 18:50, Johannes Hahn <johannes.hahn at uni-jena.de> wrote:

> 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.
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum




More information about the Forum mailing list