Trích xuất tập hợp con từ boost dynamic_bitset

Question

Tôi cần trích xuất và giải mã các bit (idx, idx + 1, ... idx + n_bits) từ một dynamic_bitset tăng đã cho. Tôi đã tạo ra các giải pháp sau đây:

boost::dynamic_bitset<> mybitset(...); 
// build mask 2^{idx+n_bits} - 2^{idx} 
const boost::dynamic_bitset<> mask(mybitset.size(), (1 << idx+n_bits) - (1 << idx)); 
// shift the masked result idx times and get long 
unsigned long u = ((mybitset & mask) >> idx).to_ulong(); 

Nó hoạt động tốt, nhưng khi mã này là rất quan trọng để thực hiện các ứng dụng của tôi, tôi tò mò nếu có tồn tại một cách tốt hơn để đạt được điều này?

Answer 1

Giải pháp là đơn giản:

#include <tuple> 
    using std::get; 
    using std::tuple; 
    using std::make_tuple; 
#include <boost/dynamic_bitset.hpp> 
    using boost::dynamic_bitset; 

template <typename Block, typename Allocator> 
unsigned block_index(const boost::dynamic_bitset<Block, Allocator>& b, unsigned pos) 
{ return pos/b.bits_per_block; } 

namespace boost { 
template <> 
inline void 
to_block_range(const dynamic_bitset<>& b, tuple<unsigned, unsigned, unsigned long&> param) 
{ 

    { 
     unsigned beg = get<0>(param); 
     unsigned len = get<1>(param); 
     unsigned block1 = block_index(b, beg); 
     unsigned block2 = block_index(b, beg + len -1); 
     unsigned bit_index = beg % b.bits_per_block; 
     unsigned long bitmask = (1 << len) - 1; 
     get<2>(param) = ((b.m_bits[block1] >> bit_index) | 
           (b.m_bits[block2] << (b.bits_per_block - bit_index) )) & 
           bitmask; 
     return; 
    } 
} 
} 


unsigned long res; 
to_block_range(bits, make_tuple(pos, len, std::ref(res))); 

Để gọi:

boost::dynamic_bitset<> bits; 
unsigned long result; 
to_block_range(bits, t_extract_range{begin_bit, length_bits, result}); 

Không có, hỗ trợ bản địa trực tiếp trong dynamic_bitset.

Để nhận được một loạt các bit, bạn phải vào bên trong dynamic_bitset, nhận quyền truy cập vào bộ nhớ cơ bản và tự giải nén các bit.

Mã để thực hiện việc này là không đáng kể nhưng dữ liệu (dynamic_bitset::m_bits) nằm trong phần riêng tư của lớp học. Có ba cách để hack qua tường riêng tư:

1. Giả vờ trình biên dịch của bạn không phù hợp.
   #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Điều này thay đổi private thành public bằng cách thay đổi BOOST_DYNAMIC_BITSET_PRIVATE.
2. Lấy tiêu đề dynamic_bitset.hpp để hiển thị m_bits.
3. Giải pháp thứ ba là làm việc xung quanh mã hiện tại.

(1) và (2) là các cuộc tấn công giòn, phía trước sẽ là cơn ác mộng duy trì.

May mắn cho (3), có các chức năng mẫu là friend s trong số dynamic_bitset. Chúng ta có thể thay thế hàm riêng của chúng ta để thực hiện phép khai thác riêng của chúng ta bằng cách tiếp quản (chuyên dụng) khuôn mẫu này.

template <typename Block, typename Allocator, typename BlockOutputIterator> 
inline void 
to_block_range(const dynamic_bitset<Block, Allocator>& b, 
       BlockOutputIterator result) 
{ 
    std::copy(b.m_bits.begin(), b.m_bits.end(), result); 
} 

Mẫu chức năng bản kinh điển các toàn bộ bitset để iterator BlockOutputIterator đó là không những gì chúng ta muốn.

Chúng ta sẽ chuyên boost::to_block_range sử dụng một kiểu tùy chỉnh đơn ở vị trí của BlockOutputIterator mà sẽ giữ tất cả 3 i/o các thông số: cụ thể là

• begin_bit,
• length_of_range và
• đích.

Cung cấp cho bạn gọi to_block_range với loại cần thiết, nó sẽ gọi chức năng của riêng bạn thay vì mẫu chuẩn, nhưng có toàn quyền truy cập vào nội bộ. Về cơ bản bạn đã hủy hệ thống đặc tả truy cập C++!

N.B.Mã ví dụ không kiểm tra lỗi. Không nỗ lực để đảm bảo

• rằng phạm vi phù hợp trong unsigned dài hoặc
• rằng phạm vi không vượt quá giới hạn của bitset hoặc
• rằng bitset sử dụng chờ đợi unsigned trong nội bộ.