在大型的大整数集上快速执行操作 [英] Fast implementation of operations on large sets of quite big integers
本文介绍了在大型的大整数集上快速执行操作的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
说明：
我实施了以下课程LabSetInt64（见下面的代码）。
I implemented the following class LabSetInt64 (see below code).
这里的目标是尽可能快地操纵大型整数（最大值为10M）。
我的主要要求主要集中在：
The goal here is to manipulate large sets of big integers (up to values of 10M) as fast as possible. My main requirements are focused on :
- ！至关重要：尽可能快地获得一组的大小/基数
- ！重要提示：能够快速迭代一套
所以，从实施开始在下面，我仍然希望与你讨论两点。
So, starting from the implementation below, it still remain two points I would like to discuss with you.
popcount（）懒惰实现
int LabSetInt64::popcount(uint64_t x) {
int count;
for (count=0; x; count++)
x &= x-1;
return count;
}
我知道我选择的实施是市场上最慢的实施之一，但我不能
自己找一个更好的。所以，如果你能指出一个更好的（64位，当然）......
I know that the implementation I chose is one of the slowest in the market place, but I could not find out a better one by myself. So if you can point me to a better one (64 bits, of course)...
我听说过一种非常有效的计算基数的算法：MIT HAKMEM 169算法>>
I heard about a very efficient algorithm to compute cardinality : The "MIT HAKMEM 169" algorithm >>
// MIT HAKMEM.
// MIT HAKMEM Count is funky. Consider a 3 bit number as being 4a+2b+c. If we
// shift it right 1 bit, we have 2a+b. Subtracting this from the original gives
// 2a+b+c. If we right-shift the original 3-bit number by two bits, we get a,
// and so with another subtraction we have a+b+c, which is the number of bits
// in the original number. How is this insight employed? The first assignment
// statement in the routine computes tmp. Consider the octal representation of
// tmp. Each digit in the octal representation is simply the number of 1¡äs in
// the corresponding three bit positions in n. The last return statement sums
// these octal digits to produce the final answer. The key idea is to add
// adjacent pairs of octal digits together and then compute the remainder
// modulus 63. This is accomplished by right-shifting tmp by three bits, adding
// it to tmp itself and ANDing with a suitable mask. This yields a number in
// which groups of six adjacent bits (starting from the LSB) contain the number
// of 1¡äs among those six positions in n. This number modulo 63 yields the
// final answer. For 64-bit numbers, we would have to add triples of octal
// digits and use modulus 1023. This is HACKMEM 169, as used in X11 sources.
// Source: MIT AI Lab memo, late 1970¡äs.
// http://gurmeet.net/2008/08/05/fast-bit-counting-routines/
int CheckMIT(unsigned int n)
{
/* works for 32-bit numbers only */
/* fix last line for 64-bit numbers */
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
// the remainder of 63 for i equals the sum of 7 octal numbers which
// consititutes the 32-bit integer.
// For example, 03456 % 63 == 034 + 056
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
我上面算法的问题是我对它的理解不够
把它变成uint64_t（64位）版本（尽管有很少的指示）。
My problem with the algorithm above is that I don't understand it enough to turn it into "uint64_t" (64 bits) version (despite the few instructions to do it).
所以，如果你们中的一个可以帮助我任务（或至少帮助我理解），这将是非常棒的。
So if one of you could help me with that task (or at least help me to understand), that would be awesome.
这是 LabSetInt64.h ：
/*
* LabSetInt64.h
*
* Created on: Feb 20, 2013
* Author: golgauth
*/
#ifndef LABSETINT64_H_
#define LABSETINT64_H_
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdint.h>
#include <limits>
#include <algorithm>
#include <LabTimeUtils.h>
using namespace std;
namespace elps {
// Lets assume we need at most 1M distinct indices in our sets
#define DEFAULT_SIZE_IN_BITS 1000000
class LabSetInt64
{
public:
LabSetInt64();
LabSetInt64(int sizeinbits);
LabSetInt64(const LabSetInt64 &);
~LabSetInt64();
void Clear();
void Resize(int sizeinbits);
void Set(int i);
void UnSet(int i);
void Set(int i, bool b);
bool Find(int i);
int Cardinality();
int NextSetBit(int i);
void Print();
/**
* Should have been "=" operator, but this overload is not compatible
* with Cython, so we'll use "<<" instead.
* @param
* @return
*/
const LabSetInt64 & operator << ( const LabSetInt64 & );
LabSetInt64 operator ~ () const;
LabSetInt64 operator + ( const LabSetInt64 & );
LabSetInt64 operator * ( const LabSetInt64 & );
LabSetInt64 operator - ( const LabSetInt64 & );
LabSetInt64 operator ^ ( const LabSetInt64 & );
private:
uint64_t *data;
int data_len;
int bits_size;
int popcount(uint64_t x);
int nb_trailing_zeros(uint64_t v);
};
} /* namespace elps */
#endif /* LABSETINT64_H_ */
此处 LabSetInt64.cpp ：
/*
* LabSetInt64.cpp
*
* Created on: Feb 20, 2013
* Author: golgauth
*/
#include "LabSetInt64.h"
namespace elps {
/** PUBLICS **/
LabSetInt64::LabSetInt64() : LabSetInt64(DEFAULT_SIZE_IN_BITS) {
}
LabSetInt64::LabSetInt64(int sizeinbits) {
bits_size = sizeinbits;
data_len = (bits_size + 63) / 64;
data = new uint64_t[data_len];
}
LabSetInt64::LabSetInt64(const LabSetInt64& src) {
bits_size = src.bits_size;
data_len = src.data_len;
data = new uint64_t[data_len];
for( int i = 0; i < data_len; i++ ) // copy into this set
data[i] = src.data[i];
}
LabSetInt64::~LabSetInt64() {
}
void LabSetInt64::Clear() {
std::fill_n(data, data_len, 0);
}
void LabSetInt64::Resize(int sizeinbits) {
bits_size = sizeinbits + 1;
int size = (bits_size + 63) / 64;
uint64_t *new_data = new uint64_t[size];
memcpy( new_data, data, data_len * sizeof(uint64_t) );
data_len = size;
delete [] data;
data = new_data;
}
void LabSetInt64::Set(int i) {
data[i / 64] |= (1l << (i % 64));
}
void LabSetInt64::UnSet(int i) {
data[i / 64] &= ~(1l << (i % 64));
}
void LabSetInt64::Set(int i, bool b) {
if(b) Set(i); else UnSet(i);
}
bool LabSetInt64::Find(int i) {
return ((data[i / 64]) & (1l << (i % 64))); // binary AND;
}
int LabSetInt64::Cardinality() {
int sum = 0;
for(int i=0; i<data_len; i++)
sum += popcount(data[i]);
//sum += __builtin_popcount(data[i]);
return sum;
}
int LabSetInt64::NextSetBit(int i) {
int x = i / 64;
long w = data[x];
w >>= (i % 64);
if (w != 0) {
return i + nb_trailing_zeros(w);
}
++x;
for (; x < data_len; ++x) {
if (data[x] != 0) {
return x * 64 + nb_trailing_zeros(data[x]);
}
}
return -1;
}
void LabSetInt64::Print() {
int cur_id = this->NextSetBit(0);
cout << "\nSet size : " << this->Cardinality() << endl;
cout << "{ ";
while (cur_id != -1)
{
cout << (cur_id) << " ";
cur_id = this->NextSetBit(cur_id+1);
}
cout << "}" << endl;;
}
/** PRIVATES **/
//This is better when most bits in x are 0
//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
int LabSetInt64::popcount(uint64_t x) {
int count;
for (count=0; x; count++)
x &= x-1;
return count;
}
// output: c will count v's trailing zero bits,
// so if v is 1101000 (base 2), then c will be 3
int LabSetInt64::nb_trailing_zeros(uint64_t v) {
int c;
if (v)
{
v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s to 1s and zero rest
for (c = 0; v; c++) {
v >>= 1;
}
}
else
c = 8 * sizeof(v);
return c;
}
/** ***************************************************************************
********************************* OPERATORS *******************************
*******************************************************************************/
/** PUBLICS **/
/*******************************************************************************
* TODO >> May be better to use "DEFAULT_SIZE_IN_BITS" instead of "data_len" *
* in all the operators !!! *
* *
* => For now, we assume that all the Sets are created with the default *
* constructor (aka : bit_size = DEFAULT_SIZE_IN_BITS) *
*******************************************************************************/
/**
* "operator = " assigns the right hand side to this set.
* returns: nothing
*/
const LabSetInt64 &LabSetInt64::operator << ( const LabSetInt64 &rhs )
{
if( &rhs != this ) // avoid self assignment
{
this->Resize(rhs.bits_size - 1);
for( int i = 0; i < data_len; i++ ) // copy into this set
data[i] = rhs.data[i];
}
return *this; // enable x << y << z;
}
/**
* "operator ~ " performs set complement operation (not).
* returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator ~ () const
{
LabSetInt64 rv;
for( int i = 0; i < data_len; i++ )
rv.data[i] = ~data[i]; // bitwise complement
return rv;
}
/**
* "operator + " performs set union operation (or).
* returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator + ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( int i = 0; i < data_len; i++ )
rv.data[i] = data[i] | rhs.data[i]; // bitwise OR
return rv;
}
/**
* "operator * " performs set intersection operation (and).
* returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator * ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( int i = 0; i < data_len; i++ )
rv.data[i] = data[i] & rhs.data[i]; // bitwise AND
return rv;
}
/**
* "operator - " performs set difference operation.
* returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator - ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( int i = 0; i < data_len; i++ )
rv.data[i] = data[i] & ( ~rhs.data[i] ); // bitwise a AND ~b
return rv;
}
/**
* "operator ^ " performs set symmetric difference operation (xor).
* returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator ^ ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( int i = 0; i < data_len; i++ )
rv.data[i] = data[i] ^ rhs.data[i]; // bitwise XOR
return rv;
}
/** *****************************************************************************
*********************************************************************************/
} /* namespace elps */
对于其余的实施，我对表演很满意，但又一次，任何好的
评论都会非常受欢迎。
For the rest of the implementation, I am quite happy with the performances, but once again, any good comments would be very very well appreciated.
非常感谢您的时间。
编辑：
好吧，毕竟我并不完全相信稀疏的解决方案，因为我需要联合，交集，差异功能，这些，我猜，很多比我的按位版本更昂贵（需要迭代潜在的大量项目），所以我仍然有兴趣获得一些帮助，如何将上述MIT HAKMEM算法转换为64位。非常感谢。
编辑：
此版本包含一些小缺陷。请更好地查看下面给出的源代码。
EDIT : This version contains some little imperfections. Please, better look at the source code given bellow.
推荐答案
因此，在研究了其他一些库之后（ BitMagic 和一些C ++和Java实现），
和许多bechmarkings：
So, after having studied some other libraries (BitMagic and a few C++ and java implementations), and a lot of bechmarkings :
（由于需要快速组合运算符，我拒绝了稀疏选项）...
(I rejected the "sparse" option because of the need of fast combination operators)...
我进行了一些有趣的改进。
I went to some interesting improvements.
主要的改进是我现在保持基数（意味着快速计算不再是一个大问题）。
The main improvement is that I now maintain the cardinality on the fly (meaning that counting fast is no longer a big issue).
改进：
- 迭代（这是我的第一个问题）仍然比（BitMagic）慢一点，但还行。将我的表现与BitMagic的表现进行比较证实我的课程毕竟不是那么糟糕......但BitMagic的目的主要是通过使用压缩来节省内存，并且在处理时比使用boost（我想避免在这里避免）慢得多使用大向量。
- 显着改善了我们计算基数的方式。
inline int nb_trailing_zeros(uint64_t v) {
if (v & 1l) return 0; // Fast check if no trailing zeros
// Avoids a useless call to __builtin_ctzl()
else return __builtin_ctzl(v);
}
两项改进：使用gcc的内置函数计算尾随零并避免在调用时调用它该块以1开始显着改善了迭代时的性能。
Two improvements : using gcc's builtin function for counting trailing zeros and avoiding calling it when the block starts with a 1 improved significantly the performances while iterating.
用法内置 sse4.2 popcount函数：
usage of builtin sse4.2 popcount function :
inline int popcount(uint64_t x) {
// int count;
// for (count=0; x; count++)
// x &= x-1;
// return count;
return _mm_popcnt_u64(x); //__builtin_popcount(x) is ok too
// Thanks to @cschwan for pointing me on this
}
_ mm_popcnt_u64需要额外的编译选项-m64 -msse4.2
（不是__builtin_popcount）
"_mm_popcnt_u64" requires additional compilation options "-m64 -msse4.2" (not "__builtin_popcount")
增加了以下功能：
int LabSetInt64::CU ( const LabSetInt64 &rhs ) {
int sum = 0;
for(int i=0; i<data_len; i++)
sum += popcount(data[i] | rhs.data[i]);
return sum;
}
比进行操作更快，然后再计数。
Faster than making the operation, and then counting.
优化计数选项（ CNT_OPT 模式）：查看新版本版本
"optim counting" option (CNT_OPT mode) : See the new class version bellow
减慢组合操作的速度（只有几个，没有真正的担忧......）
Slows down a little bit the combination operations (just a few, no real worries...)
仅在未找到时插入：
void LabSetInt64::Set(int i) {
int n = i / 64;
uint64_t shift1l = 1l << (i % 64);
if ( !(data[n] & shift1l) ) { // Not found
data[n] |= shift1l;
if (CNT_OPT) ++cardinality;
}
}
首先检查该位是否已经更快设置，而不是在任何情况下设置它。
（我们尝试插入的最多的零，我们节省的时间最多）。
设置非设置位时，性能保持不变。
It is faster to first check if the bit is already set, than setting it in any cases. (the most zeros we try to insert, the most we save time). The performances remain quite unchanged in case of setting a non-set bit.
const LabSetInt64 & LabSetInt64::operator += ( const LabSetInt64 & rhs) {
for( int i = 0; i < data_len; i++ )
data[i] = data[i] | rhs.data[i]; // bitwise OR
return *this;
}
A + = B现在比A = A + B快得多（保存要返回的新向量
的实例化）
A += B is now much faster than A = A + B (saves the instantiation of a new vector to be returned)
添加了一些便利函数和运算符：请参阅下面的新类版本
Added some convenience functions and operators : See the new class version bellow
[标题]
/**
* If the set to 1, will be optimized for counting (cardinality updated on the fly).
* WARNING : Optimizing for counting will slow down a little the following features :
* - Binary operation : (~, +, *, -, ^)
*/
#define CNT_OPT 1
#define DEFAULT_SIZE_IN_BITS 1000000
//This is better when most bits in x are 0
inline unsigned int popcount(uint64_t x) {
// // It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
// int count;
// for (count=0; x; count++)
// x &= x-1;
// return count;
return _mm_popcnt_u64(x); //__builtin_popcountl(x); //
}
/**
* Counts trailing zeros starting from a given point
* @param v Input to count trailing zero bits
* @return c will count v's trailing zero bits,
so if v is 1101000 (base 2), then c will be 3
*/
inline int nb_trailing_zeros(uint64_t v) {
if (v & 1l) return 0; // Fast check if no trailing zeros
// Avoids a useless call to __builtin_ctzl()
else return __builtin_ctzl(v);
}
class LabSetInt64
{
public:
LabSetInt64();
/**
* Instantiates a bitset with a given maximum size.
* @param sizeinbits Maximum size of the population
*/
LabSetInt64(unsigned int sizeinbits);
LabSetInt64(const LabSetInt64 &);
virtual ~LabSetInt64();
void Clear();
void Resize(unsigned int sizeinbits);
/**
* WARNING : no check is perform whether i is in the correct range :
* i MUST be in [0, size_in_bits-1]
*/
void Set(int i);
void UnSet(int i);
// void Set(int i, bool b);
int Cardinality();
bool Find(int i);
void Print();
int GetFirst();
int ChooseOne();
int GetAt(int n);
const LabSetInt64 & operator = ( const LabSetInt64 & );
/**
* All the following operators assume that left and right operands
* have the same size "size_in_bits" (enough for our needs,
* since memory usage is not really a problem for us).
*/
LabSetInt64 operator ~ () const; /** Inversion **/
LabSetInt64 operator + ( const LabSetInt64 & ); /** Union **/
LabSetInt64 operator * ( const LabSetInt64 & ); /** Intersection **/
LabSetInt64 operator - ( const LabSetInt64 & ); /** Difference **/
LabSetInt64 operator ^ ( const LabSetInt64 & ); /** Symmetrical D. **/
/**
* Comparison.
*/
bool operator == ( const LabSetInt64 & ) const;
bool operator != ( const LabSetInt64 & ) const;
/**
* Convenient, moreover :
* (A += B) is actually a lot faster than (A = A + B)...
* [ No intermediary storage ]
*/
const LabSetInt64 & operator += ( const LabSetInt64 & );
const LabSetInt64 & operator *= ( const LabSetInt64 & );
const LabSetInt64 & operator -= ( const LabSetInt64 & );
const LabSetInt64 & operator ^= ( const LabSetInt64 & );
const LabSetInt64 & INV();
/**
* Gets the population count of the union.
* Faster than realizing the union, then calling Cardinality().
* [ No intermediary storage ]
*/
int CU ( const LabSetInt64 & );
int CI ( const LabSetInt64 & );
int CD ( const LabSetInt64 & );
int CSD ( const LabSetInt64 & );
/**
* Basic iterator facility.
*/
class iter {
public:
iter(LabSetInt64 & bv) { pos_ = -1; bv_ = &bv; }
void reset() { pos_ = -1; }
int end() { return -2; }
int next() { pos_ = bv_->next_set_bit(pos_); return pos_; }
private:
int pos_;
LabSetInt64 * bv_;
};
private:
uint64_t * data_;
unsigned int data_len_;
unsigned int size_in_bits_;
unsigned int cardinality_;
void init_bitset(unsigned int sizeinbits);
int calc_cardinality();
int next_set_bit(int i);
};
[实施]
LabSetInt64::LabSetInt64() {
init_bitset(DEFAULT_SIZE_IN_BITS);
}
LabSetInt64::LabSetInt64(unsigned int sizeinbits) {
init_bitset(sizeinbits);
}
void LabSetInt64::init_bitset(unsigned int sizeinbits) {
// +1 (the last higher weighted bit is 0 : allows to stop when iterating)
// See example in "Print()" function
size_in_bits_ = sizeinbits + 1;
data_len_ = (size_in_bits_ + 63) / 64;
data_ = new uint64_t[data_len_];
if (CNT_OPT) cardinality_ = 0;
Clear(); // Start filled with 0s. // Necessary...
}
LabSetInt64::LabSetInt64(const LabSetInt64& src) {
size_in_bits_ = src.size_in_bits_;
data_len_ = src.data_len_;
data_ = new uint64_t[data_len_];
memcpy( data_, src.data_, src.data_len_ * sizeof(uint64_t) );
cardinality_ = src.cardinality_;
}
LabSetInt64::~LabSetInt64() {
if (data_ != NULL) delete[] data_;
}
void LabSetInt64::Clear() {
std::fill_n(data_, data_len_, 0);
if (CNT_OPT) cardinality_ = 0;
}
void LabSetInt64::Resize(unsigned int sizeinbits) {
bool truncated;
unsigned int new_sizeinbits = sizeinbits + 1;
if (size_in_bits_ != new_sizeinbits)
{
truncated = (size_in_bits_ > new_sizeinbits);
size_in_bits_ = new_sizeinbits;
unsigned int new_size = (size_in_bits_ + 63) / 64;
if (new_size != data_len_) // Resize only if storage size changed
{
uint64_t *new_data = new uint64_t[new_size];
if (!truncated) // Clear : required only if extended
std::fill_n(new_data, new_size, 0);
memcpy( new_data, data_, std::min(data_len_, new_size) * sizeof(uint64_t) );
data_len_ = new_size;
delete [] data_;
data_ = new_data;
}
//--
if (truncated) {
// Clear the bits beyond the maximum size
unsigned int begin = sizeinbits;
unsigned int end = data_len_ * 64;
for ( unsigned int i = begin; i<end; ++i ) UnSet(i);
// Update cardinality
if (CNT_OPT) cardinality_ = calc_cardinality();
}
}
}
void LabSetInt64::Set(int i) {
int n = i / 64;
uint64_t shift1l = 1l << (i % 64);
if ( !(data_[n] & shift1l) ) { // Not found
data_[n] |= shift1l;
if (CNT_OPT) ++cardinality_;
}
}
void LabSetInt64::UnSet(int i) {
int n = i / 64;
uint64_t shift1l = 1l << (i % 64);
if ( data_[n] & shift1l ) { // Found
data_[n] &= ~shift1l;
if (CNT_OPT) --cardinality_;
}
}
//void LabSetInt64::Set(int i, bool b) {
// if(b) Set(i); else UnSet(i);
//}
bool LabSetInt64::Find(int i) {
return ((data_[i / 64]) & (1l << (i % 64)));
}
int LabSetInt64::Cardinality() {
if (CNT_OPT) return cardinality_;
else return calc_cardinality();
}
int LabSetInt64::calc_cardinality() {
unsigned int sum = 0;
for(unsigned int i=0; i<data_len_; i++)
sum += popcount(data_[i]);
//sum += bitcount64_4way(data[i], data[i+1], data[i+2], data[i+3]);
return sum;
}
int LabSetInt64::next_set_bit(int i) {
++i;
unsigned int x = i / 64;
uint64_t w = data_[x];
w >>= (i % 64);
if (w != 0) {
return i + nb_trailing_zeros(w);
}
++x;
for (; x < data_len_; ++x) {
if (data_[x] != 0) {
return x * 64 + nb_trailing_zeros(data_[x]);
}
}
return -2;
}
void LabSetInt64::Print() {
cout << "\nSet size : " << this->Cardinality() << endl;
cout << "{ ";
int cnt = 0;
iter it(*this);
for (int val = it.next(); val != it.end(); val = it.next())
{
cout << (val) << " ";
if ((++cnt) % 30 == 0) cout << endl;
}
cout << "}" << endl;
}
int LabSetInt64::GetFirst() {
return this->next_set_bit(-1);
}
int LabSetInt64::ChooseOne() {
// Get lucky...
int id = rand() % this->size_in_bits_;
// Otherwise...
if (!Find(id))
id = GetAt(rand() % this->Cardinality());
return id;
}
int LabSetInt64::GetAt(int n) {
int cnt = 0, val;
iter it(*this);
while ((val = it.next()) != it.end() && cnt++ != n) { }
return val;
}
// *************************************************
/*----------------------------------------------------------------------------*
** "operator = " assigns the right hand side to this set.
**
** returns: nothing
*/
const LabSetInt64 &LabSetInt64::operator = ( const LabSetInt64 &rhs )
{
if( &rhs != this ) // avoid self assignment
{
this->Resize(rhs.size_in_bits_ - 1);
memcpy( data_, rhs.data_, rhs.data_len_ * sizeof(uint64_t) );
if (CNT_OPT) cardinality_ = rhs.cardinality_;
}
return *this; // enable x = y = z;
}
/*----------------------------------------------------------------------------*
** "operator ~ " performs set complement operation (not).
**
** returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator ~ () const
{
LabSetInt64 rv;
unsigned int i;
for( i = 0; i < data_len_; i++ ) {
rv.data_[i] = ~data_[i]; // bitwise complement
if (CNT_OPT) rv.cardinality_ += popcount(rv.data_[i]);
}
rv.size_in_bits_ = size_in_bits_;
// Clear the bits beyond the maximum size
unsigned int begin = rv.size_in_bits_ - 1;
unsigned int end = data_len_ * 64;
for ( i = begin; i<end; ++i ) rv.UnSet(i);
return rv;
}
/*----------------------------------------------------------------------------*
** "operator + " performs set union operation (or).
**
** returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator + ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( unsigned int i = 0; i < data_len_; i++ ) {
rv.data_[i] = data_[i] | rhs.data_[i]; // bitwise OR
if (CNT_OPT) rv.cardinality_ += popcount(rv.data_[i]);
}
return rv;
}
/*----------------------------------------------------------------------------*
** "operator * " performs set intersection operation (and).
**
** returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator * ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( unsigned int i = 0; i < data_len_; i++ ) {
rv.data_[i] = data_[i] & rhs.data_[i]; // bitwise AND
if (CNT_OPT) rv.cardinality_ += popcount(rv.data_[i]);
}
return rv;
}
/*----------------------------------------------------------------------------*
** "operator - " performs set difference operation.
**
** returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator - ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( unsigned int i = 0; i < data_len_; i++ ) {
rv.data_[i] = data_[i] & ( ~rhs.data_[i] ); // bitwise a AND ~b
if (CNT_OPT) rv.cardinality_ += popcount(rv.data_[i]);
}
return rv;
}
/*----------------------------------------------------------------------------*
** "operator ^ " performs set symmetric difference operation (xor).
**
** returns: pointer to set
*/
LabSetInt64 LabSetInt64::operator ^ ( const LabSetInt64 &rhs )
{
LabSetInt64 rv;
for( unsigned int i = 0; i < data_len_; i++ ) {
rv.data_[i] = data_[i] ^ rhs.data_[i]; // bitwise XOR
if (CNT_OPT) rv.cardinality_ += popcount(rv.data_[i]);
}
return rv;
}
bool LabSetInt64::operator == ( const LabSetInt64 &rhs ) const {
if ((CNT_OPT) && (cardinality_ != rhs.cardinality_)) return false;
for( unsigned int i = 0; i < data_len_; i++ )
{
if (data_[i] != rhs.data_[i]) {
return false;
}
}
return true;
}
bool LabSetInt64::operator != ( const LabSetInt64 &rhs ) const {
return !(*this == rhs);
}
const LabSetInt64 & LabSetInt64::operator += ( const LabSetInt64 & rhs) {
if (CNT_OPT) cardinality_ = 0;
for( unsigned int i = 0; i < data_len_; i++ ) {
data_[i] = data_[i] | rhs.data_[i];
if (CNT_OPT) cardinality_ += popcount(data_[i]);
}
return *this;
}
const LabSetInt64 & LabSetInt64::operator *= ( const LabSetInt64 & rhs) {
if (CNT_OPT) cardinality_ = 0;
for( unsigned int i = 0; i < data_len_; i++ ) {
data_[i] = data_[i] & rhs.data_[i];
if (CNT_OPT) cardinality_ += popcount(data_[i]);
}
return *this;
}
const LabSetInt64 & LabSetInt64::operator -= ( const LabSetInt64 & rhs) {
if (CNT_OPT) cardinality_ = 0;
for( unsigned int i = 0; i < data_len_; i++ ) {
data_[i] = data_[i] & ( ~rhs.data_[i] );
if (CNT_OPT) cardinality_ += popcount(data_[i]);
}
return *this;
}
const LabSetInt64 & LabSetInt64::operator ^= ( const LabSetInt64 & rhs) {
if (CNT_OPT) cardinality_ = 0;
for( unsigned int i = 0; i < data_len_; i++ ) {
data_[i] = data_[i] ^ rhs.data_[i];
if (CNT_OPT) cardinality_ += popcount(data_[i]);
}
return *this;
}
// *************************************************
const LabSetInt64 & LabSetInt64::INV() {
unsigned int i;
if (CNT_OPT) cardinality_ = 0;
for( i = 0; i < data_len_; i++ ) {
data_[i] = ~data_[i];
if (CNT_OPT) cardinality_ += popcount(data_[i]);
}
// Clear the bits beyond the maximum size
unsigned int begin = size_in_bits_ - 1;
unsigned int end = data_len_ * 64;
for ( i = begin; i<end; ++i ) UnSet(i);
return *this;
}
// *************************************************
int LabSetInt64::CU ( const LabSetInt64 & rhs ) {
int sum = 0;
for( unsigned int i=0; i < data_len_; i++ )
sum += popcount(data_[i] | rhs.data_[i]);
return sum;
}
int LabSetInt64::CI ( const LabSetInt64 & rhs ) {
int sum = 0;
for( unsigned int i=0; i < data_len_; i++ )
sum += popcount(data_[i] & rhs.data_[i]);
return sum;
}
int LabSetInt64::CD ( const LabSetInt64 & rhs ) {
int sum = 0;
for( unsigned int i=0; i < data_len_; i++ )
sum += popcount(data_[i] & (~rhs.data_[i]));
return sum;
}
int LabSetInt64::CSD ( const LabSetInt64 & rhs ) {
int sum = 0;
for( unsigned int i=0; i < data_len_; i++ )
sum += popcount(data_[i] ^ rhs.data_[i]);
return sum;
}
Note about portability :
One some architectures (like Windows 7 + MinGW), where long is only 32 bits, replace in the above code, all occurrences of :
Note about portability :
One some architectures (like Windows 7 + MinGW), where long is only 32 bits, replace in the above code, all occurrences of :
1lwith1ll__builtin_popcountlwith__builtin_popcountll__builtin_ctzlwith__builtin_ctzll
1lwith1ll__builtin_popcountlwith__builtin_popcountll__builtin_ctzlwith__builtin_ctzll
This will ensure you’re always using 64 bits numbers (long long).
This will ensure you're always using 64 bits numbers (long long).
Well, I hope this was informative and it can be a good starting point for some others.
Well, I hope this was informative and it can be a good starting point for some others.
这篇关于在大型的大整数集上快速执行操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
