转换bitarray设置

Question

如何转换bitarray快速设置与c + +？ 每个实际bitarrays有750,000位。

实施例1：

bitarray: 01011111 
set: {0,1,2,3,4,5,7} 
or set: {1,3,4,5,6,7} 

实施例2：

bitarray: 0101 1111 0001 0001 
set: {0,4,8,9,10,11,12,14} 
or set: {1,3,4,5,6,7,11,15} 

该组是usigned 32位整数（uint32_t的）的阵列。这两种设置都可以接受。

该位阵在内存中是连续的。 bitarray的第一位对simd有正确的对齐。现在我正在使用一个自定义的内存分配器与std :: vector来容纳bitarray。 bitarray中每1位的内存中有1位。

谢谢。

更新：

this so question does the reverse

loop through bits in c

How to define and work with an array of bits in C?

gmpy使用gmp library的SCAN1功能。 SCAN1似乎找到第一套，如维基百科here

Answer 1

如果我明白你的问题：

for (int i = 0; i < 750000; ++i) { 
    if (bitarray_has(bitarray, i)) { 
     set_of_numbers.push_back(i); 
    } 
} 

我不相信走bitarray会特别慢，但可以push_back()如果你知道如何进行得更快许多元素将被创建。然后您可以使用reserve()预先分配内存。

Answer 2

代码：

#include <iostream> 
#include <vector> 
#include <time.h> 

using namespace std; 

template <typename T> 
uint32_t bitarray2set(T& v, uint32_t * ptr_set){ 
    uint32_t i; 
    uint32_t base = 0; 
    uint32_t * ptr_set_new = ptr_set; 
    uint32_t size = v.capacity(); 
    for(i = 0; i < size; i++){ 
     find_set_bit(v[i], ptr_set_new, base); 
     base += 8*sizeof(uint32_t); 
    } 
    return (ptr_set_new - ptr_set); 
} 

inline void find_set_bit(uint32_t n, uint32_t*& ptr_set, uint32_t base){ 
    // Find the set bits in a uint32_t 
    int k = base; 
    while(n){ 
     if (n & 1){ 
      *(ptr_set) = k; 
      ptr_set++; 
     } 
     n = n >> 1; 
     k++; 
    } 
} 

template <typename T> 
void rand_vector(T& v){ 
    srand(time(NULL)); 
    int i; 
    int size = v.capacity(); 
    for (i=0;i<size;i++){ 
     v[i] = rand(); 
    } 
} 

template <typename T> 
void print_vector(T& v, int size_in = 0){ 
    int i; 

    int size; 
    if (size_in == 0){ 
     size = v.capacity(); 
    } else { 
     size = size_in; 
    } 
    for (i=0;i<size;i++){ 
     cout << v[i] << ' '; 
    } 
    cout << endl; 
} 

int main(void){ 
    const int test_size = 6000; 
    vector<uint32_t> vec(test_size); 
    vector<uint32_t> set(test_size*sizeof(uint32_t)*8); 
    rand_vector(vec); 
    //for (int i; i < 64; i++) vec[i] = -1; 
    //cout << "input" << endl; 
    print_vector(vec); 
    //cout << "calculate result" << endl; 

    int i; 
    int rep = 10000; 
    uint32_t res_size; 

    struct timespec tp_start, tp_end; 
    clock_gettime(CLOCK_MONOTONIC, &tp_start); 
    for (i=0;i<rep;i++){ 
     res_size = bitarray2set(vec, set.data()); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &tp_end); 
    double timing; 
    const double nano = 0.000000001; 

    timing = ((double)(tp_end.tv_sec - tp_start.tv_sec) 
      + (tp_end.tv_nsec - tp_start.tv_nsec) * nano) /(rep); 

    cout << "timing per cycle: " << timing << endl; 
    cout << "print result" << endl; 
    //print_vector(set, res_size); 
} 

结果（使用ICC -O3 code.cpp -lrt编译）

... 
timing per cycle: 0.000739613 
print result 

0.0008秒转换768000位进行设置。但每个周期至少有10,000个768,000位数组。每个周期8秒。这很慢。