bit_sets

bitset_intersection(BSet1,BSet2,Inter) :-
    Inter is BSet1 /\ BSet2.

bitset_to_ordlist(PackedInteger,ResList) :-
    unpack_fd_set_aux(PackedInteger,0,ResList).

bitset_union(BSet1,BSet2,Inter) :-
    Inter is BSet1 \/ BSet2.

empty_bit_set(0).

mem_bitset_aux(Nr,Index,BitSet) :- BitSet mod 32 =:= 0,!, BitSet \= 0, B1 is BitSet >> 5, I1 is Index+5,
    mem_bitset_aux(Nr,I1,B1).

mem_bitset_aux(Nr,Index,BitSet) :- BitSet mod 8 =:= 0,!, BitSet \= 0, B1 is BitSet >> 3, I1 is Index+3,
    mem_bitset_aux(Nr,I1,B1).

mem_bitset_aux(Nr,Index,BitSet) :- BitSet mod 2 =:= 1, Nr=Index.

mem_bitset_aux(Nr,Index,BitSet) :- BitSet \= 0, B1 is BitSet >> 1, I1 is Index+1,
    mem_bitset_aux(Nr,I1,B1).

member_bitset(Nr,BitSet) :- integer(Nr),!,
    member_grchk_bitset(Nr,BitSet).

member_bitset(Nr,BitSet) :-
    mem_bitset_aux(Nr,0,BitSet).

member_grchk_bitset(Nr,BitSet) :-
    0 =\= BitSet /\ (1<<Nr).

ordlist_to_bitset(ListOfInts,Integer) :-
    pack_list_aux(ListOfInts,0,Integer).

pack_list_aux([],A,A).

pack_list_aux([Nr|T],Acc,Res) :-
    NewAcc is Acc \/ (1<<Nr),
    pack_list_aux(T,NewAcc,Res).

t1(0,A,A) :- !.

t1(N,A,R) :- ordsets:ord_intersection(A,A,A1), ordsets:ord_intersection(A1,A1,A2),
    N1 is N-1, t1(N1,A2,R).

t1bs(0,A,A) :- !.

t1bs(N,A,R) :- bitset_intersection(A,A,A1), bitset_intersection(A1,A1,A2),
    N1 is N-1, t1bs(N1,A2,R).

t2(0,A,R) :- member(R,A),!.

t2(N,A,R) :- (member(I,A), I=N -> true ; true),
    N1 is N-1, t2(N1,A,R).

t2bs(0,A,R) :- member_bitset(R,A),!.

t2bs(N,A,R) :- (member_bitset(I,A), I=N -> true ; true),
    N1 is N-1, t2bs(N1,A,R).

test(N) :- L = [1,20,21,23, 44,50,51],
    tools:start_ms_timer(T1),
    t1(N,L,R),
    tools:stop_ms_timer_with_msg(T1,test1_inter(N,R)),
    ordlist_to_bitset(L,B),
    tools:start_ms_timer(T1b),
    t1bs(N,B,RBS), bitset_to_ordlist(RBS,R1BS),
    tools:stop_ms_timer_with_msg(T1b,test1_bitset(N,RBS,R1BS)),
    tools:start_ms_timer(T2),
    t2(N,L,R2),
    tools:stop_ms_timer_with_msg(T2,test2_member(N,R2)),
    tools:start_ms_timer(T2b),
    t2bs(N,B,R22),
    tools:stop_ms_timer_with_msg(T2b,test2_bitset(N,R22)).

unpack_fd_set_aux(0,_,Res) :- !, Res=[].

unpack_fd_set_aux(Nr,X,Res) :- Nr mod 32 =:= 0,!,
    X1 is X+5, Nr1 is (Nr>>5),
    unpack_fd_set_aux(Nr1,X1,Res).

unpack_fd_set_aux(Nr,X,Res) :- Nr mod 8 =:= 0,!,
    X1 is X+3, Nr1 is (Nr>>3),
    unpack_fd_set_aux(Nr1,X1,Res).

unpack_fd_set_aux(Nr,X,Res) :-
    (Nr mod 2 =:= 1 -> Res = [X|T] ; Res=T),
    X1 is X+1, Nr1 is (Nr>>1),
    unpack_fd_set_aux(Nr1,X1,T).