+
+uint static_bitsequence_brw32::select0(uint x) {
+ // returns i such that x=rank_0(i) && rank_0(i-1)<x or n if that i not exist
+ // first binary search over first level rank structure
+ // then sequential search using popcount over a int
+ // then sequential search using popcount over a char
+ // then sequential search bit a bit
+ if(x>n-ones) return (uint)(-1);
+
+ //binary search over first level rank structure
+ if(x==0) return 0;
+ uint l=0, r=n/s;
+ uint mid=(l+r)/2;
+ uint rankmid = mid*factor*W-Rs[mid];
+ while (l<=r) {
+ if (rankmid<x)
+ l = mid+1;
+ else
+ r = mid-1;
+ mid = (l+r)/2;
+ rankmid = mid*factor*W-Rs[mid];
+ }
+ //sequential search using popcount over a int
+ uint left;
+ left=mid*factor;
+ x-=rankmid;
+ uint j=data[left];
+ uint zeros = W-popcount(j);
+ while (zeros < x) {
+ x-=zeros;left++;
+ if (left > integers) return n;
+ j = data[left];
+ zeros = W-popcount(j);
+ }
+ //sequential search using popcount over a char
+ left=left*b;
+ rankmid = 8-popcount8(j);
+ if (rankmid < x) {
+ j=j>>8;
+ x-=rankmid;
+ left+=8;
+ rankmid = 8-popcount8(j);
+ if (rankmid < x) {
+ j=j>>8;
+ x-=rankmid;
+ left+=8;
+ rankmid = 8-popcount8(j);
+ if (rankmid < x) {
+ j=j>>8;
+ x-=rankmid;
+ left+=8;
+ }
+ }
+ }
+
+ // then sequential search bit a bit
+ while (x>0) {
+ if (j%2 == 0 ) x--;
+ j=j>>1;
+ left++;
+ }
+ left--;
+ if (left > n) return n;
+ else return left;
+}