Solved

# Boolean array efficiency.

Posted on 2007-03-20
1,517 Views
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
0
Question by:Unimatrix_001
• 33
• 19
• 13
• +4

LVL 84

Accepted Solution

ozo earned 250 total points
int bitIndex=0;
while(bitIndex<aArraySize){
if( aBoolArray[bitIndex]^=1 ){
return false;
}
bitIndex++;
}
return true;
0

LVL 3

Author Comment

What?... That small thing instead of my entire function? :O
0

LVL 6

Expert Comment

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize)
{
for(int i=0;i<aArraySize;i++)
{
}
}

Regards
Bijo.
0

LVL 6

Expert Comment

Hi Uni

comparison always steels a lot more cpu cycles.
i havnt made any comparisons in my code.

Regards
Bijo.
0

LVL 3

Author Comment

Hi,

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.
*******************************
0

LVL 11

Expert Comment

for(int i=0;i<aArraySize;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 :

long lStartTimer = GetTickCount();
.....
.....
...function to be tested...

long lEndTimer = GetTickCount()-lStartTimer;

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

LVL 3

Author Comment

Hi Deepu, thanks although I'm aware of doing a time test, which is what I'm currently doing. Thanks anyway.
0

LVL 3

Author Comment

ozo: Your code takes 17750ms, while the original code takes 13766ms?
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(binaryArray, numberOfBits))
break;
}
DWORD e=GetTickCount();
cout<<"Dur: "<<(e-s)<<endl;
delete[] binaryArray;
================================================================================

Thanks,
Uni
0

LVL 7

Expert Comment

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;
}
0

LVL 7

Expert Comment

Applied small correction:

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;
}
0

LVL 3

Author Comment

0

LVL 39

Assisted Solution

itsmeandnobodyelse earned 250 total points
Or that:

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
0

LVL 3

Author Comment

Alex. Thanks, although that gives an output of:

000
100
110
111

Rather than:
000
100
010
110
001
101
011
111

Thanks,
Uni
0

LVL 39

Expert Comment

Note for a bool array you need bits rather than bytes. You could make a more efficient bool array by using a little class like that:

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
0

LVL 39

Expert Comment

>>>> ...although that gives an output of:

Change to
if (*p)
*p = 0;   // HERE =  NOT ==
0

LVL 11

Expert Comment

(e - s)/1000 will give you the correct value in sec.More readable!
0

LVL 16

Expert Comment

A variant to ozo's post:

bool * bit = &aBoolArray[0];
while(aArraySize>0){
if( *bit^=1 ){
return false;
}
bit++;aArraySize--;
}
return true;

Paul
0

LVL 84

Expert Comment

// You could unroll the loop
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
0

LVL 39

Expert Comment

>>>> 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
0

LVL 84

Expert Comment

>> indexing will speed up the loop cause it uses pointer addition instead of multiplication.
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
0

LVL 16

Expert Comment

To get a significant improvement, try to understand exactly why you need to do this using arrays of booleans. Arrays of integers would be MUCH faster.

Paul
0

LVL 3

Author Comment

Wow! That's a lot of replies...  However no suggestions so far have beaten the original. The closest so far was the latest one by ozo, which unrolls the loop. That had a time of 14343ms, while the original was 13766ms.

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.
0

LVL 3

Author Comment

Actually, ignore that last reply. I'm going to do some testing on another computer, this one seems to be having a few hiccups.
0

LVL 3

Author Comment

Ok, I've finished testing and something was very wrong with the other computer... Here's the results:

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
0

LVL 3

Author Comment

Hi all.

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]==&_B0){
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
0

LVL 84

Expert Comment

I'm not sure that improvement is correct.
What are the results you get in aBoolArray, and how does that compare with what the original function does to aBoolArray?
0

LVL 84

Expert Comment

> Surely a loop cannot be that expensive?
It isn't that expensive.
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

0

LVL 3

Author Comment

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

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
0

LVL 3

Author Comment

It just seems that 378ms seems pretty expensive for just setting up a loop, more than a third of a second.
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.
0

LVL 84

Expert Comment

May we see the test loop for
bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){
and
bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){
so we can see the array being printed?
0

LVL 3

Author Comment

Of course:

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(binaryArray, numberOfBits))
break;
printBinaryArray(binaryArray, numberOfBits); cout<<endl;
}
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]==&_B0){
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(binaryArray, numberOfBits))
break;
printBinaryArray(binaryArray, numberOfBits); cout<<endl;
}
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...
0

LVL 84

Expert Comment

It looks like indexing into a
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;
}
0

LVL 3

Author Comment

Hmm, so do you reckon this can be done any more efficient than your suggestion of:

================================================================================
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.
0

LVL 39

Expert Comment

>>>> if(aBoolArray[0]==&_B0)
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

0

LVL 84

Expert Comment

>> That looks to be wrong. Why are you comparing bools with pointers?
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.
0

LVL 3

Author Comment

"That looks to be wrong. Why are you comparing bools with pointers?"
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?
0

LVL 84

Expert Comment

Or if you can pack the bits in a single int:
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(&binaryArray, (1<<29)-1))
break;
printBinaryArray(binaryArray, numberOfBits); cout<<endl;
}
++*aBoolArray;

}
0

LVL 3

Author Comment

"that's what I thought at first too, but it looks like the definition of  aBoolArray changed between the two functions."
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.
0

LVL 3

Author Comment

"Or if you can pack the bits in a single int"
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.
0

LVL 84

Expert Comment

How about using 32/numberOfBits ints and doing a carry between ints whenever the plusOneToBinaryArray of one int results in 0?
0

LVL 7

Expert Comment

Unimatrix 001:

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.
0

LVL 3

Author Comment

"How about using 32/numberOfBits ints and doing a carry between ints whenever the plusOneToBinaryArray of one int results in 0?"
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?
0

LVL 3

Author Comment

nixfreak: Unfortunately this doesn't produce the correct result. This produces a pattern as:

00001000000000000000000000000
00001100000000000000000000000
...
00001111111111111111111111111

rather than:

00000000000000000000000000000
10000000000000000000000000000
01000000000000000000000000000
11000000000000000000000000000

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

LVL 3

Author Comment

With regards to a macro, to be honest I thought the complexity of having that in a macro would not be possible, as I regarded them as fine for simple things, but not as complex as this?
0

LVL 7

Expert Comment

Yeah the code is wrong:
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 :)!
0

LVL 84

Expert Comment

plusOneToBinaryArray would be faster with 32/numberOfBits ints
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.

0

LVL 7

Expert Comment

Frankly, the function is a good candidate for coding in assembly.
0

LVL 84

Expert Comment

What time do you get with sonething like this before the main loop?
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;
0

LVL 84

Expert Comment

another possibility could be using an int for the first maybe 4 or 8 bits, since most of the time the addone will only affect the first few bits, and then go to a slower 1 bit per int addone for the rarer cases, then most of your other operations can use the one bit per int structure and a few of them would have to access the first few bits within the int
0

LVL 3

Author Comment

"printBinaryArray could be slightly slower"
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.
0

LVL 3

Author Comment

ozo: For that suggestion I get 2500ms.
0

LVL 84

Expert Comment

Checking for a certain binary pattern in an int is just an == so that should be pretty fast
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.
0

LVL 84

Expert Comment

> For every second spent increasing the array approximately 4-5 minutes was spent carrying out the operations for each possible value.
Then it sounds like we are concentrating our effort in the wrong place.
0

LVL 3

Author Comment

"Checking for a certain binary pattern in an int is just an == so that should be pretty fast"
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.
0

LVL 3

Author Comment

"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.

Is everybody okay with that?
0

LVL 3

Author Comment

Ack... that should be:

"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?
0

LVL 84

Expert Comment

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

LVL 39

Expert Comment

>>>> So I'd have to convert an integer into a binary string
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

0

LVL 3

Author Comment

Ozo: I'm not quite sure if you wanted times for that, but if you did it was 2672ms... :)
Alex: I'll get back to you on that once I fully understand it all.

Thanks both,
Uni
0

LVL 3

Author Comment

Hi Alex,

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.
0

LVL 39

Expert Comment

>>>> I.e. I have 001010010 and want to count the instances of 001.

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;
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
0

LVL 39

Expert Comment

There is a shorter implementation of allBits not using a static array:

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
0

LVL 3

Author Comment

@Alex: Hmm, this will take a while for me to figure out.. :)

@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
0

LVL 3

Author Comment

Alex: I'm struggling to get my head around the BoolArray class you provided earlier.

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?
0

LVL 39

Expert Comment

>>>> Judging by the operations on this variable, this should be a pointer?
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

0

LVL 84

Expert Comment

> sizeof(unsigned int) gives the size in bytes which has 8 bits guaranteed.
not exactly, CHAR_BIT is guaranteed to be at least 8
0

LVL 39

Expert Comment

>>>> 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)

0

LVL 84

Expert Comment

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

LVL 39

Expert Comment

ozo is right. sizeof returns the size in chars and the number of bits in a char is defined by the constant CHAR_BIT defined in limits.h. I was trapped by a MSDN document where they told that a byte has always 8 bits what made me think that byte was 8 bits always and byte and char were not necessarily same size.

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
0

LVL 3

Author Comment

In what circumstances would a byte not be 8 bits? I've heard of this before, but I can't say I've ever come across it! :) ...Is it a CPU issue?
0

LVL 3

Author Comment

Hi. Well I think I may have got my head around Alex's idea... so I'm ready to close this question, any problems I'll make a new question for. Can I have recommendations on assigning the points?

Thanks. :)
Uni
0

LVL 39

Expert Comment

>>>> In what circumstances would a byte not be 8 bits
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
0

LVL 39

Expert Comment

>>>> Well I think I may have got my head around Alex's idea
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
0

LVL 3

Author Comment

Hi all,

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
0

LVL 84

Expert Comment

There was a split proposed in http:/Q_22463065.html

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
0

LVL 7

Expert Comment

int bitIndex=0;
while(bitIndex<aArraySize){
if( aBoolArray[bitIndex]^=1 ){
return false;
}
bitIndex++;
}
return true;
The code given by ozo in the first comment is IMO the most elegant (if not the fastest :) ).
0

LVL 3

Author Comment

Thanks all. Please complain if you're not happy with the splits.

Thanks again,
Uni
0

## Featured Post

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article locâ€¦
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.