[GAP Forum] Bitwise operations

Johannes Hahn johannes.hahn at uni-jena.de
Tue Sep 11 20:13:33 BST 2012


Hi Stephen.

n is pretty small. I would be perfectly happy if there was a solution 
for let's say n<=10 so that everything would fit easily into a 32bit 
integer. The adjacency matrix is not sparse in general, so it would be 
very time- and memory-consuming to fill the matrix for much bigger n. My 
hope is of course, that the conjecture I would like to test, is either 
true for all n or at least that it fails for some n<=10 :-)

Thanks for taking time for this
Johannes.

Am 11.09.2012 21:06, schrieb Stephen Linton:
> 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