flags in a bitmap

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

For OEIS:A005282 I wrote this "clean" code:

aupto1(L)= {
  my(S=vector(L), A=[1]);
  for(i=2, L
  , for(j=1, #A
    , if(S[i-A[j]], next(2))
    );
    for(j=1, #A
    , S[i-A[j]]=1
    );
    A=concat(A, i)
  );
  A
}

So S is a "seen" array.

I could also use an integer and then bitand and bitor:

aupto2(L)= {
  my(S=0, A=[1]);
  for(i=2, L
  , for(j=1, #A
    , if(bitand(S, 1<<(i-A[j]-1)), next(2))
    );
    for(j=1, #A
    , S=bitor(S, 1<<(i-A[j]-1))  \\or: S+= 1<<(i-A[j]-1)
    );
    A=concat(A, i)
  );
  A
}

but that is (much) slower.


There are of course multiple ways to improve this code.
For example S=Vecsmall(0,L) uses less memory and is marginally faster.

I think a big win would be to have a (dynamic? sparse?) byte-buffer with 
addressable bits.
Is there already a fast implementation of such somewhere?
The sparse-option could for example mean that runs of 0- and/or 
255-bytes get run-length encoded.

-- Ruud