Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Hi,

I use this function to add one to a boolean array (in essence a binary array), which is fine, but is there any way of speeding this up? Just for further information, it returns true if it has looped back to a value of 0, otherwise false.

================================================================================

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){

if(aBoolArray[0]==0){

aBoolArray[0]=1;

return false;

}else

aBoolArray[0]=0;

int bitIndex=1;

while(bitIndex<aArraySize){

if(aBoolArray[bitIndex]==0){

aBoolArray[bitIndex]=1;

return false;

}else

aBoolArray[bitIndex]=0;

bitIndex++;

if(bitIndex==aArraySize)

return true;

}

return true;

}

================================================================================

Thanks,

Uni

I use this function to add one to a boolean array (in essence a binary array), which is fine, but is there any way of speeding this up? Just for further information, it returns true if it has looped back to a value of 0, otherwise false.

==========================

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){

if(aBoolArray[0]==0){

aBoolArray[0]=1;

return false;

}else

aBoolArray[0]=0;

int bitIndex=1;

while(bitIndex<aArraySize)

if(aBoolArray[bitIndex]==0

aBoolArray[bitIndex]=1;

return false;

}else

aBoolArray[bitIndex]=0;

bitIndex++;

if(bitIndex==aArraySize)

return true;

}

return true;

}

==========================

Thanks,

Uni

{

bool TempMask=1;

for(int i=0;i<aArraySize;i++)

{

TempMask = TempMask & aBoolArray[i];

}

return TempMask;

}

Regards

Bijo.

comparison always steels a lot more cpu cycles.

i havnt made any comparisons in my code.

Regards

Bijo.

Just to let you know I'm trying to get it into my program... having a couple of problems elsewhere now though. Hopefully won't be long. :)

Thanks,

Uni

**************************

FAO future posters: Any further solutions won't be considered as I've already got two possible solutions.

**************************

{

TempMask = TempMask & aBoolArray[i];

}

Well both the soutions are good but the above code will iterate through till max array size, whereas OSO's solution will not do that which I guess is slightly more efficient.

If you want to see how much time it took :

Put your code under

long lStartTimer = GetTickCount();

.....

.....

...function to be tested...

long lEndTimer = GetTickCount()-lStartTimer

cout<<"Time taken : "<<lEndTimer/1000.00<<endl

bijopuli: It seems the code you've given doesn't modify the array with the new result?

FYI, here's the code I'm using to test:

==========================

int numberOfBits=29;

//Set array to 0.

bool *binaryArray=new bool[numberOfBits];

for(int i=0;i<numberOfBits;i++)

binaryArray[i]=0;

//Loop.

DWORD s=GetTickCount();

while(true){

if(plusOneToBinaryArray(bi

break;

}

DWORD e=GetTickCount();

cout<<"Dur: "<<(e-s)<<endl;

delete[] binaryArray;

==========================

Thanks,

Uni

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize) {

int carry = 1;

while (aArraySize) {

if ( *aBoolArray & carry ) {

*aBoolArray = 0;

carry = 1;

aBoolArray++;

aArraySize--;

continue;

}

*aBoolArray = 1;

carry = 0;

return false;

}

return true;

}

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize) {

int carry = 1;

while (aArraySize) {

if ( *aBoolArray & carry ) {

*aBoolArray = 0;

carry = 1;

aBoolArray++;

aArraySize--;

continue;

}

*aBoolArray = 1;

return false;

}

return true;

}

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize)

{

bool* p = &aBoolArray[0];

bool* pend = &aBoolArray[aArraySize];

for (; p != pend; ++p)

if (*p)

*p == 0;

else

return (*p = 1) == 0; // always false

return true;

}

Regards, Alex

000

100

110

111

Rather than:

000

100

010

110

001

101

011

111

Thanks,

Uni

class BoolArray

{

unsigned int bits; // buffer for bits

iint size; // array size

int bitsint; // bits pro integer

public:

BoolArray(int numBits)

{

int bitsint = (sizeof(unsigned int) * 8);

size = (numBits + bitsint - 1)/bitsint;

bits = new unsigned int[size];

memset(bits, 0, size * sizeof(unsigned int));

}

~BoolArray() { delete [] bits; }

bool plusOne()

{

int i;

for (i = 0; i < size && *(bits + i) == 0xffffffff; ++i)

*(bits + i) = 0;

if (i >= size)

return true;

(*(bits + i))++; // normal increment will do the job

return false;

};

};

Regards, Alex

bool * bit = &aBoolArray[0];

while(aArraySize>0){

if( *bit^=1 ){

return false;

}

bit++;aArraySize--;

}

return true;

Paul

if( aBoolArray[0]^=1 ){ return false; }

if( aBoolArray[1]^=1 ){ return false; }

if( aBoolArray[2]^=1 ){ return false; }

if( aBoolArray[3]^=1 ){ return false; }

// that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases

int bitIndex=4;

while(bitIndex<aArraySize)

if( aBoolArray[bitIndex]^=1 ){

return false;

}

bitIndex++;

}

return true;

//or depending on your compiler, applying PaulCaswell's variant may also help

Yes, using pointers instead of indexing will speed up the loop cause it uses pointer addition instead of multiplication. That's why iterators for containers were much faster than using operator[].

Regards, Alex

Some compilers are smart enough to figure that out on their own, and some machines can loop comparing to 0 faster than loop comparing to other constants

Paul

Ozo in regards to: "that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases" I'm curious to how you arrived at that figure, as surely that is depedant on the test using 29 bits? Also, I can't see why unrolling the loop is faster? After all, your original suggestion was not any different other than being inside a loop, but it still terminated on the first true. Surely a loop cannot be that expensive?

PaulCaswell: I do not need to use a bool array, since I'm treating it as a binary string. I'd have though a comparison on a binary value (a bool) would have been much faster than a comparison for an integer (even if they still only contain a binary value)?

Thanks all! :)

Uni.

Original: 3312ms

ozo's first code: 3110ms

nixfreak: 3187ms

itsmeandnobodyelse: 3188ms

PaulCaswells variant: 2969ms

ozo's unrolled loop:2734ms

That's much better! :) I've been playing about with some CPU stuff that's clearly had a negative impact. So, the questions now:

ozo: I can't see why unrolling the loop is faster? After all, your original suggestion was not any different other than being inside a loop, but it still terminated on the first true. Surely a loop cannot be that expensive?

PaulCaswell: I do not need to use a bool array, since I'm treating it as a binary string. I'd have though a comparison on a binary value (a bool) would have been much faster than a comparison for an integer (even if they still only contain a binary value)?

Thanks again,

Uni

Ok, I've done a bit more improvement and I've found that this:

==========================

int _B0=0;

int _B1=1;

bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){

if(aBoolArray[0]==&_B0){

aBoolArray[0]=&_B1;

return false;

}else

aBoolArray[0]=&_B0;

int bitIndex=1;

while(bitIndex<aArraySize)

if(aBoolArray[bitIndex]==&

aBoolArray[bitIndex]=&_B1;

return false;

}else

aBoolArray[bitIndex]=&_B0;

bitIndex++;

if(bitIndex==aArraySize)

return true;

}

return true;

}

==========================

Takes 3078ms using the original code, so a saving of 234ms. Not huge compared to what's been put forward, but is there a way I can combine this method with maybe the unrolled loop idea (or any of them to be honest!) to get a bigger saving?

Thanks again,

Uni

What are the results you get in aBoolArray, and how does that compare with what the original function does to aBoolArray?

It isn't that expensive.

According to your numbers, it only adds 378ms out of 3110

the loop has to set bitIndex and test it, which are not done if the loop is unrolled.

I got my 6.25% number by assuming that aBoolArray[bitIndex]==0 and aBoolArray[bitIndex]==1 are equally likely, which it should be on average if you run plusOneToBinaryArray many times on the same aBoolArray

Re: I'm not sure that improvement is correct.

Well, I've ran it again and even printed the int array (I've converted all the ideas given so far to use ints as PaulCaswell suggested and it is faster again) in the test loop that calls the plusOneToBinaryArray function and it's doing exactly the same thing as the original function except 234ms faster. What makes you think it shouldn't be faster?

Thanks,

Uni

Should read:

It just seems that 378ms seems pretty expensive for just setting up a loop and test a variable, more than a third of a second.

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){

and

bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){

so we can see the array being printed?

This is using the pointers:

==========================

int _B0=0;

int _B1=1;

int main(){

int numberOfBits=29;

//Set array to 0.

int **binaryArray=new int*[numberOfBits];

for(int i=0;i<numberOfBits;i++)

(binaryArray[i])=&_B0;

//Loop.

DWORD s=GetTickCount();

while(true){

if(plusOneToBinaryArray(bi

break;

printBinaryArray(binaryArr

}

DWORD e=GetTickCount();

//Output and clean-up.

cout<<"Dur: "<<(e-s)<<endl;

delete[] binaryArray;

//All okay.

return 0;

}

bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){

//3078ms

if(aBoolArray[0]==&_B0){

aBoolArray[0]=&_B1;

return false;

}else

aBoolArray[0]=&_B0;

int bitIndex=1;

while(bitIndex<aArraySize)

if(aBoolArray[bitIndex]==&

aBoolArray[bitIndex]=&_B1;

return false;

}else

aBoolArray[bitIndex]=&_B0;

bitIndex++;

if(bitIndex==aArraySize)

return true;

}

return true;

}

void printBinaryArray(int **aBoolArray, int aArraySize){

for(int i=0;i<aArraySize;i++)

cout<<*(aBoolArray[i]);

}

==========================

This is using the original:

==========================

int main(){

int numberOfBits=29;

//Set array to 0.

int *binaryArray=new int[numberOfBits];

for(int i=0;i<numberOfBits;i++)

binaryArray[i]=0;

//Loop.

DWORD s=GetTickCount();

while(true){

if(plusOneToBinaryArray(bi

break;

printBinaryArray(binaryArr

}

DWORD e=GetTickCount();

//Output and clean-up.

cout<<"Dur: "<<(e-s)<<endl;

delete[] binaryArray;

}

bool plusOneToBinaryArray(int aBoolArray[], int aArraySize){

//3312ms

if(aBoolArray[0]==0){

aBoolArray[0]=1;

return false;

}else

aBoolArray[0]=0;

int bitIndex=1;

while(bitIndex<aArraySize)

if(aBoolArray[bitIndex]==0

aBoolArray[bitIndex]=1;

return false;

}else

aBoolArray[bitIndex]=0;

bitIndex++;

if(bitIndex==aArraySize)

return true;

}

return true;

}

void printBinaryArray(int aBoolArray[], int aArraySize){

for(int i=0;i<aArraySize;i++)

cout<<(aBoolArray[i]);

}

==========================

I think that's correct. It's cut and pasted from a few different files, but it should be fine...

bool plusOneToBinaryArray(char *aBoolArray, int aArraySize){

if( aBoolArray[0]^=1 ){ return false; }

if( aBoolArray[1]^=1 ){ return false; }

if( aBoolArray[2]^=1 ){ return false; }

if( aBoolArray[3]^=1 ){ return false; }

char *bit = &aBoolArray[3];

aArraySize-=3;

while( --aArraySize>0 ){

if( *++bit^=1 ){

return false;

}

}

return true;

}

==========================

if( aBoolArray[0]^=1 ){ return false; }

if( aBoolArray[1]^=1 ){ return false; }

if( aBoolArray[2]^=1 ){ return false; }

if( aBoolArray[3]^=1 ){ return false; }

// that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases

int bitIndex=4;

while(bitIndex<aArraySize)

if( aBoolArray[bitIndex]^=1 ){

return false;

}

bitIndex++;

}

return true;

==========================

I've tried putting PaulCaswells suggestion in, but it doesn't seem to give any improvement at all.

That looks to be wrong. Why are you comparing bools with pointers?

The initial if else block handling index 0 doesn't seem to be necessary as you easily can solve the initial case with the loop that follows. Do you have better times when handling the initial case separately? If yes it is the unroll effect ozo already has commented. However, if a significant part of your calls pass an empty bool array, you should consider whether a bool array makes sense at all. If you take an unsigned int you have 32 bits which can be checked fastly and easily. The plusOne function simply would increment the integer. With a 64 bit integer you are doubling the number of bools and it is not very difficult to create a 128 or 256 or ... bit integer as I showed it in one of my previous posts.

Regards, Alex

that's what I thought at first too, but it looks like the definition of aBoolArray changed between the two functions.

if changing the data type from bool to int* made it faster, I though perhaps a char array might be even faster, but maybe the machine it is running on is faster for moves that are aligned to larger words.

I'm checking to see if the pointer at aBoolArray[0] points to _B0, since aBoolArray in the pointer idea I had was an array of pointers to an integer (either _B0 or _B1).

With the initial if else block, it is faster marginally (on average after 5 runs about 15ms). If I unroll it up to 8 elements (there's still 29 in the array), then it's faster by about 250ms.

"However, if a significant part of your calls pass an empty bool array, you should consider whether a bool array makes sense at all."

No, an empty bool array is never passed. There are always numberOfBits elements (so far has always been 29) in the array, and all I do is go through every possible combination.

"If you take an unsigned int you have 32 bits which can be checked fastly and easily. The plusOne function simply would increment the integer. With a 64 bit integer you are doubling the number of bools and it is not very difficult to create a 128 or 256 or ... bit integer as I showed it in one of my previous posts."

Well, for each combination of bits (currently 2^29), I do an few operations on them, i.e. bit switching and finding patterns. So I'd have to convert an integer into a binary string (whether that is an array of bools, or a string) it seems still more expensive than just operating on a int array?

void printBinaryArray(int aBoolArray, int aArraySize){

for(int i=0;i<aArraySize;i++){

cout<<aBoolArray&1;

aBoolArray>>=1;

}

}

int binaryArray=0;

while(true){

if(plusOneToBinaryArray(&b

break;

printBinaryArray(binaryArr

}

bool plusOneToBinaryArray(int *aBoolArray, int aArraymask){

++*aBoolArray;

return *aBoolArray&=aArraymask

}

Yes it did. My apologies, I should have made it a bit more clearer just how different the two programs were.

"if changing the data type from bool to int* made it faster"

In all cases it sped up quite significantly.

"but maybe the machine it is running on is faster for moves that are aligned to larger words."

Well, the CPU is an AMD Athlon 64 X2 Dual 2.21Ghz, running 64-bit XP. However compiling into a 64-bit program slows it down (I guess it's to do with the CPU having to pad the data types?). So I'm compiling into a 32-bit application.

Thing is though if I do that, I'm limiting myself to what is essentially only a 32-bit array. Even if I use an unsigned __int64, I'm still only limited to a 64-bit array.

Can you try this modification of ozo's code that uses AND instead of XOR. In x86 AND executes faster than XOR.

if( aBoolArray[0]^=0 ){ return false; }

if( aBoolArray[1]^=0 ){ return false; }

if( aBoolArray[2]^=0 ){ return false; }

if( aBoolArray[3]^=0 ){ return false; }

/* Calculate remaining 2^(aArraySize - 4) possiblities */

aArraySize = aArraySize - 4;

bool * bit = &aBoolArray[4];

while(aArraySize != 0) {

if( *bit &= 1 ) {

bit++;aArraySize--;

continue;

}

*bit = 1 /* don't forgot this step */

return false;

}

return true;

Notes:

- You might also want to use a macro instead of a funtion call which incurs an additional function call overhead.

- You might want to use compiler optimizations. A compiler may be able to optimize by loop unrolling.

If that would be faster then no problem. However, my only concern is as I said earlier:

I do an few operations on them, i.e. bit switching and finding patterns. So I'd have to convert an integer into a binary string (whether that is an array of bools, or a string) it seems still more expensive than just operating on a int array?

The operations are going to be more expensive than finding all values, and I'm wondering if the cost of making the loop faster would actually slow the overall program down since searching for bit patterns and bit switching would be slower if the bits are packed into an integer?

00001000000000000000000000

00001100000000000000000000

...

00001111111111111111111111

rather than:

00000000000000000000000000

10000000000000000000000000

01000000000000000000000000

11000000000000000000000000

etc... On the bright side it does only take 16ms. Hehehe. :)

if( aBoolArray[0]^=0 ){ return false; }

if( aBoolArray[1]^=0 ){ return false; }

if( aBoolArray[2]^=0 ){ return false; }

if( aBoolArray[3]^=0 ){ return false; }

Actually in the above the bit is never set hence the "addition is never actually performed -- it only return true or false :)!

printBinaryArray could be slightly slower, but I don't think you'd notice compared to the cout<< operation.

what other operations are you doing and how often are you doing them?

There may be acceptably fast ways of doing them with 32 bits per int,

or or if you do a lot of plusOneToBinaryArray operations in a row, and then a lot of some other operation that works better with a one bit per int structure,

then it may be worth translating back and forth.

if( !aBoolArray[0] ){ aBoolArray[0]=1; return false; } aBoolArray[0]=0;

if( !aBoolArray[1] ){ aBoolArray[1]=1; return false; } aBoolArray[1]=0;

if( !aBoolArray[2] ){ aBoolArray[2]=1; return false; } aBoolArray[2]=0;

if( !aBoolArray[3] ){ aBoolArray[3]=1; return false; } aBoolArray[3]=0;

That's not an issue. It would only occasionally be called (perhaps every 10 minutes) just to give a rough idea of progress.

Well, what is done for every possible value is:

* Check to see if certain binary patterns exist (this again can be a bool array, etc...).

* Do some bit manipulation.

To give you some idea of the percentage of the operations to incrementing the bool array. For every second spent increasing the array approximately 4-5 minutes was spent carrying out the operations for each possible value.

"or or if you do a lot of plusOneToBinaryArray operations in a row"

No, only one operation is done, then the above operations are done for that value. Then we call plusOneToBinaryArray and repeat the same operations buton that value... Then it's a case of rinse and repeating until all possible values of the binary array have been carried out.

I don't know what kinds of bit manipulations you want to do, there exist various tricks to do certain types of bit manipulations with ints.

It may also be possible to restructure the problem slightly so that the bit manipulations you do turn out to be the ones that can be done faster rather than the ones that are slower.

Then it sounds like we are concentrating our effort in the wrong place.

Again sorry, I should have made it more clear! :( I'm not checking precisely for one binary array to exactly match another binary array, but to search inside the binary array for certain patterns.

"I don't know what kinds of bit manipulations you want to do, there exist various tricks to do certain types of bit manipulations with ints."

Things such as switching every X bit, or applying a formula to a bit pattern to switch certain bits.

Well, I don't think I'm allowed to give out the specific algorithms that we use for the operations, but what I think I should do is maybe close this question and post a new one for a clean slate.

Is everybody okay with that?

"Then it sounds like we are concentrating our effort in the wrong place."

Well, I don't think I'm allowed to give out the specific algorithms that we use for the operations, but what I think I should do is maybe close this question and post a new one for a clean slate. Then find out how efficient the operations are when searching inside a binary array (whether it is an int array, or using an integer to store the bits).

Is everybody okay with that?

if( aBoolArray[1] = !aBoolArray[1] ){ return false; }

if( aBoolArray[2] = !aBoolArray[2] ){ return false; }

if( aBoolArray[3] = !aBoolArray[3] ){ return false; }

No, of course not.

All standard operations can be made with the unsigned int

unsigned int binaryArray = 0; // sets all bits to 0

unsigned int binaryArray = 0xffffffff; // sets all bits to 1

binaryArray++; // plus one

binaryArray |= 1<<n; // set bit n

binaryArray &= ~(1<<n); // clear bit n

binaryArray = ~binaryArray; // build complement

binaryArray >>= n; // right shift of all bits by n

// padding up with zero bits

binaryArray <<= n; // left shift of all bits by n

// padding up with zero bits

unsigned int pattern = 0x10fa98bd; // any pattern

if ((binaryArray & pattern) != 0) // all bits of the pattern match

...

if (binaryArray == pattern) // exact pattern match

...

Note if a pattern is made by single bits it easily can be build by using enums:

enum

{

FIRST = 0x00000001,

SECOND = 0x00000002,

....

TWENTY_NINETH = 0x10000000

};

unsigned int pattern = THIRD | FOURTH | TWELVETH; // set bits 2, 3, 11

or (equivalent)

unsigned int pattern = (1<<2) | (1<< 3) | (1<<11);

or (equivalent)

unsigned int pattern = 4 + 8 + (1<<11);

Regards, Alex

Alex: I'll get back to you on that once I fully understand it all.

Thanks both,

Uni

Didn't take me as long as I thought to get to grips with what you've suggested, however I'm not checking directly for an exact pattern match, but maybe counting the instances of a pattern in a binary array. I.e. I have 001010010 and want to count the instances of 001.

Also, how fast are these:

binaryArray |= 1<<n; // set bit n

binaryArray &= ~(1<<n); // clear bit n

compared to an int array:

binaryArray[2]=0;

binaryArray[6]=1;

binaryArray[7]=1;

etc...

As the bits will be switched after a seperate program has evaluated some mathematical formula.

unsigned int ba = 0x00000052; // == 001010010

int count = 0;

for (int i = 0; i < 7; ++i)

if ( ((ba>>i) & 0x7) == 1)

count++;

Remarks:

1. I assumed that we know the number of bits relevant for ba (10 bits) and the pattern (3 bits). That's is why I used 7 as upper loop boundary (10 - 3) and 0x7 to get a mask for the lower 3 bits. You may argue that when using unsigned ints the bit sizes must be computed programmatically (what costs extra time) but I think that isn't fair. When holding an array you need to save the size as well if it is not the same for all arrays. So, in case of using an unsigned int you would make it a member of a little helper class that would have the size as a second member:

class BitArray

{

unsigned int ba;

int siz;

public:

BitArray(unsigned int ui, int size) : ba(ui), siz(size) {}

unsigned int setAt(int n) { ba |= 1<<n; }

...

};

Of course all operations should be made inline.

2. if ( ((ba>>i) & 0x7) == 1)

The ba>>i shifts the bits right for i positions. So first it is not shifted.

The "& 0x7" extracts only the low 3 bits (all higher bits were set to 0) which is then compared with the integer value of the pattern (001 == 1).

If we would use the above class to count any pattern we would use the following inline member:

class BitArray

{

...

int countPattern(const BitArray& pattern)

{

int count = 0;

int sizPattern = pattern.siz;

unsigned int mask = pattern.allBits();

for (int i = 0; i < siz - pattern.siz ; ++i)

if ( ((ba>>i) & mask ) == pattern.ba)

count++;

}

};

The pattern.allBits() would return an unsigned integer where all bits are set up to the size of the pattern. It can be implemented like

unsigned int allBits()

{

static unsigned int all[32] = { 0x1, 0x3, 0x7, 0xf, 0x1f....., 0xffffffff };

return all[siz];

}

>>>> Also, how fast are these:

AND (&) and OR (|) operations on 32 bit integer are made with one assembler statement. It depends on the compiler whether the temporaries were moved to registers and back but anyhow it is only a very small part of the time any of your above function calls will need.

Regards, Alex

unsigned int allBits()

{

return (1<<siz)-1; // e. g. (1<<3) - 1 == 2^3 - 1 == 7

}

That even works for siz = 32 where (1<<32) == 0 and -1 = 0xffffffff.

Note in the previous implementation of allBits I would have to return

..

return all[siz-1];

cause the siz is 1-based while the all array is 0-based.

Regards, Alex

@Ozo and PaulCaswell: Since the actual question about making the loop has been answered please comment on http://www.experts-exchange.com/Programming/Languages/CPP/Q_22463065.html

Thanks.

Uni

1) unsigned int bits; Judging by the operations on this variable, this should be a pointer?

2) int bitsint = (sizeof(unsigned int) * 8);

size = (numBits + bitsint - 1)/bitsint;

bits = new unsigned int[size];

memset(bits, 0, size * sizeof(unsigned int));

I'm sorry, the only line I understand is the last one... :( What do the variables you specify do?

Yes it was a typo.

>>>> int bitsint = (sizeof(unsigned int) * 8);

you can change to

bitsint = 32;

if you are sure that your compiler has a 32 bit int type always. sizeof(unsigned int) gives the size in bytes which has 8 bits guaranteed.

>>>> size = (numBits + bitsint - 1)/bitsint

That computes the number of 32 bit integers I need to store the required amount of bits.

+ bitsint - 1 adds 31 to the given number of bits. Because of that the following integer division by 32 always rounds up to the *next* integer and never rounds up.

e. g. want 1 bit: (1 + 32 - 1) / 32 = 1 need array size 1 to store 1 bit

want 32 bits: (32 + 32 - 1) / 32 = 1 need array size 1 to store 32 bits

So, it doesn't matter what odd number was passed, the above calculation always computes the correct array size.

>>>> bits = new unsigned int[size];

That is the allocation of dynamically sized integer array where the bits were stored. You need to delete the pointer in the destructor of the class. You could provide a resize function where a new pointer was allocated, the old bits were copied and the old pointer was deleted.

Regards, Alex

not exactly, CHAR_BIT is guaranteed to be at least 8

I didn't talk of sizeof(char) but that the return of sizeof has a unit of 8 bits (AFAIK)

CHAR_BIT, defined in <limits.h> is the number of bits in a char and must be greater than or equal to 8

Applying that gives:

int bitsint = (sizeof(unsigned int) * CHAR_BIT);

Unfortunately there is no member function of numeric_limits template that returns the number of bits per char. So we need to use the CHAR_BIT constant as ozo has suggested.

Regards, Alex

Thanks. :)

Uni

I personally think it will never happen. Kernighan and Ritchie, the inventors of C, had made the basic types variable in size, what IMO was a bad idea. I experienced where int goes from 16 bits to 32 bits and it really was a mess. I can't think that they will repeat that mess by going from 32 to 64 but for some high-end machines and their special compilers it may happen nevertheless.

Moving a char to 16 bits really is no necessity cause you could use a wchar_t instead which has the advantage that the current available standard software could handle it (however as far as I knows wchar_t is only mimimum 16 bits and *there are* UNIX systems with a 32bit wchar_t).

>>>> Is it a CPU issue?

Yes and no. Of course a 32 bit int type makes no sense on a 16bit processor. And a 64bit pointer rarely will be used with a 32bit processor. There are also 8bit processors widely spreaded but a char has a minimum of 8 bits they need their own half-byte type but surely go to the minimum bit count of every type.

I had preferred INT8, INT16, INT32, INT64 types as I was used from FORTRAN. But noone asked me ;-)

Regards, Alex

The bitset template class in STL already has some clever implementations which might be useful. I didn't mention it til now cause some of your requirements, e. g. pattern search, cannot be made with bitset because of the very small (poor) functionality. Nevertheless you might consider to take it as a baseclass or steal some of its implementations which really are tricky.

Regards, Alex

I'm looking to close this question but can I have recommendations with regards points please? Currently I'm with a 50/50 split for ozo and Alex (itsmeandnobodyelse). If there are no comments or objections by Friday I'll split as mentioned.

Thanks, :)

Uni

comments since then have been mostly on another question.

A mask and compare to several bits at once could be faster than several different compares in an array to find a specific sequence of bits, although the latter could do a boyer-moore of knuth-moris-prat type search, and the former could get tricky if the pattern straddles multiple array entries,

another way to store bits in ints could be to pack the bits sideways, so that packing 800 bits in 100 chars could store the first 100 bits in bit 1 of eaqch char, the next 100 bits in bit 2 of each char, etc,

then you may be able to use the same logic you are using now to detect paterns scanning one array elelemt at a time, but you may be able to scan in 8 places at once by using bit operations to do 8 scans in parallel

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

while(bitIndex<aArraySize)

if( aBoolArray[bitIndex]^=1 ){

return false;

}

bitIndex++;

}

return true;