轉換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秒。這很慢。