Skip to content

Instantly share code, notes, and snippets.

@hanfeisun
Created August 15, 2012 23:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hanfeisun/3364807 to your computer and use it in GitHub Desktop.
Save hanfeisun/3364807 to your computer and use it in GitHub Desktop.
bits_extend
#include <stdio.h>
#include <stdlib.h>
#define SHIFT 4
#define MSK 0x0F
#define UNT 1
#define N 300000000
#define print(X) for (i=1;i<1+N;i++) {printf("%d\t%d\n",i,(X)[i]);}
unsigned char aln[1+N];
unsigned char pileup[1+N];
void set(unsigned long i)
{
if ((aln[i] & MSK) != MSK ) {
aln[i] += UNT;
}
}
void nset(unsigned long i)
{
if ((aln[i] & ~MSK) != ~MSK) {
aln[i] += UNT << SHIFT;
}
}
inline int get(unsigned long i) { return aln[i] & MSK; }
inline int nget(unsigned long i) { return aln[i] >> SHIFT; }
unsigned long before(unsigned long i, int shift, unsigned long start)
{
if (start < i - shift)
return i - shift;
else
return start;
}
unsigned long after(unsigned long i, int shift, unsigned long end)
{
if (i+shift < end)
return i + shift;
else
return end;
}
int ext(unsigned long pos, int shift, int seed)
{
unsigned long left;
unsigned long right;
int sum;
unsigned long i;
left = before(pos, shift, 1);
right = after(pos, shift, N+1);
if (seed == 0) {
sum = 0;
for (i=left; i<pos; i++)
sum += get(i);
for (i=pos; i<right; i++)
sum += nget(i);
return sum;
} else {
return get(pos) - get(left) + nget(right) - nget(pos);
}
}
int main(void)
{
unsigned long i;
int shiftsize = 200;
for (i=1; i < N+1; i++)
aln[i] = 0;
set(10); set(10); set(11); set(12); nset(29); nset(20);
for (i=1; i < N+1; i++)
pileup[i] = 0;
pileup[1] = ext(1, shiftsize, 0);
for (i=2; i<N+1; i++) {
pileup[i] = pileup[i-1] + ext(i, shiftsize, 1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment