9

Can I check in C(++) if an array is all 0 (or false) without iterating/looping over every single value and without allocating a new array of the same size (to use memcmp)?

I'm abusing an array of bools to have arbitrary large bitsets at runtime and do some bitflipping on it

knittl
  • 246,190
  • 53
  • 318
  • 364
  • 2
    If you are using `std::bitset`, you can use the `none()` method. http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00263.html#ac224d7f896a9922057d9e14f307b30fd – Arun Oct 28 '10 at 15:48
  • 2
    Is there a reason why this is a problem because that is more or less what the machine code will need to do anyway – doron Oct 28 '10 at 15:49
  • @arunsaha: i have to set the size for a bitset at compile time, but i need to dynamically allocate memory at runtime – knittl Oct 28 '10 at 15:50
  • @doron: using `unsigned long long`s i can only use 64 bits, but i need arbitrary large segments of memory. i'm only using `+1` (bitflip magic) and need to compare against 0 (the reason for this question) – knittl Oct 28 '10 at 15:52
  • knittl: it should be easy to make your own container class for this, that contains a bool array and tracks the number of set bits. – Johan Kotlinski Oct 28 '10 at 16:10
  • @kotlinski: that's reinventing the wheel. – Fred Foo Oct 28 '10 at 16:26
  • 2
    @Noah - we benchmarked that and discarded it at one point because it was horribly slow - reinventing the wheel is sometimes OK if usage is limited and performance is important. – Steve Townsend Oct 28 '10 at 16:33
  • @Steve - may be the case. Only made use of it once and it was perfectly adequate for my needs. I'd certainly start with the existing wheel before creating a new one though. Generally speaking, the boost folks are smarter and/or more knowledgeable than I am. Then if I really need more performance or whatnot I rewrite the interface if possible. At any rate, it was pointless suggesting it since the OP has a severe case of NDH syndrome and thus can't be helped. – Edward Strange Oct 28 '10 at 16:53
  • @Noah - yes - if adding a `set bit` counter is not helpful, then OP is left with brute-force element checking, one way or another. – Steve Townsend Oct 28 '10 at 17:00

8 Answers8

8

You can use the following condition:

(myvector.end() == std::find(myvector.begin(), myvector.end(), true))

Obviously, internally, this loops over all values.

The alternative (which really should avoid looping) is to override all write-access functions, and keep track of whether true has ever been written to your vector.

UPDATE

Lie Ryan's comments below describe a more robust method of doing this, based on the same principle.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • 1
    be aware that, while the flag can reliably tell that the array contains all false if the flag is false; if the flag is true, it cannot reliably tell if the array does contain a true. If the flag is true, you'll still need to check whether there is any true. – Lie Ryan Oct 28 '10 at 15:59
  • 3
    A more sophisticated way is to keep track of how many `true`s is in the array. If you're changing a value from true to false, you decrement this counter, and if you're changing a value from false to true, then you increment the counter. Otherwise, if you're changing from true to true or from false to false, you do nothing. You can tell if the array is all false if the counter is zero. – Lie Ryan Oct 28 '10 at 16:01
  • 4
    One thing to keep in mind though is that, if you modify the array a lot and rarely do the "is all 0" check and if the array isn't too big, you're wasting more time modifying the counter than you would be if you were to check the array. – EboMike Oct 28 '10 at 16:04
  • 2
    It's not a good idea to override std::vector . Party, because standard container implementations aren't necessarily designed to be overridden. But also, in c++0x, std::vector won't be a bitset anymore. – Johan Kotlinski Oct 28 '10 at 16:31
  • @kotlinksi: Yes, to be safe, you'd need to write your own class that wraps `std::vector`, rather than derives from it. – Oliver Charlesworth Oct 28 '10 at 16:46
2

If it's not sorted, no. How would you plan on accomplishing that? You would need to inspect every element to see if it's 0 or not! memcmp, of course, would also check every element. It would just be much more expensive since it reads another array as well.

Of course, you can early-out as soon as you hit a non-0 element.

Your only option would be to use SIMD (which technically still checks every element, but using fewer instructions), but you generally don't do that in a generic array.

(Btw, my answer assumes that you have a simple static C/C++ array. If you can specify what kind of array you have, we could be more specific.)

EboMike
  • 76,846
  • 14
  • 164
  • 167
  • 1
    +1. I think your only option provided you have a contiguous array of integral types would be to use SIMD instructions as mentioned to check multiple elements at once. – Wyatt Anderson Oct 28 '10 at 15:50
1

If you know that this is going to be a requirement, you could build a data structure consisting of an array (possibly dynamic) and a count or currently non-zero cells. Obviously the setting of cells must be abstracted through, but that is natural in c++ with overloading, and you can use an opaque type in c.

dmckee --- ex-moderator kitten
  • 98,632
  • 24
  • 142
  • 234
1

Consider using boost::dynamic_bitset instead. It has a none member and several other std::bitset-like operations, but its length can be set at runtime.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • i cannot use external libraries (and don't want to either) – knittl Oct 28 '10 at 16:01
  • 1
    @knittl: then you can copy and paste the code from `boost::dynamic_bitset`. – Steve Jessop Oct 28 '10 at 16:07
  • This is a header-only library. You can just copy the `dynamic_bitset` directory into your project and include the main header in your source file. – Fred Foo Oct 28 '10 at 16:25
  • 1
    Then I'd suggest shooting yourself. NDH syndrome is a debilitating and painful disease somewhat along the lines of Alzheimer's or brain cancer. I know that I for one at least would rather end it all than die slowly in such an awful manner. – Edward Strange Oct 28 '10 at 16:39
1

Assume that you have an array of N element, you can do a bit check against a set of base vectors.

For example, you have a 15-element array you want to test.

You can test it against an 8-element zero array, an 4-element zero array, a 2-element zero array and a 1-element zero array.

You only have to allocate these elements once given that you know the maximum size of arrays you want to test. Furthermore, the test can be done in parallel (and with assembly intrinsic if necessary).

Further improvement in term of memory allocation can be done with using only an 8-element array since a 4-element zero array is simply the first half of the 8-element zero array.

Dat Chu
  • 10,822
  • 13
  • 58
  • 82
0

No, you can compare arrays with memcmp, but you can't compare one value against a block of memory.

What you can do is use algorithms in C++ but that still involves a loop internally.

Šimon Tóth
  • 35,456
  • 20
  • 106
  • 151
0

You don't have to iterate over the entire thing, just stop looping on the first non-zero value.

I can't think of any way to check a set of values other than inspecting them each in turn - you could play games with checking the underlying memory as something larger than bool (__int64 say) but alignment is then an issue.

EDIT: You could keep a separate count of set bits, and check that is non-zero. You'd have to be careful about maintenance of this, so that setting a set bit did not ++ it and so on.

Steve Townsend
  • 53,498
  • 9
  • 91
  • 140
0

knittl,

I don't suppose you have access to some fancy DMA hardware on the target computer? Sometimes DMA hardware supports exactly the operation you require, i.e. "Is this region of memory all-zero?" This sort of hardware-accelerated comparison is a common solution when dealing with large bit-buffers. For example, some RAID controllers use this mechanism for parity checking.

Andrew Cottrell
  • 3,312
  • 3
  • 26
  • 41