Bitwise Operations on Vector<Bool>

bitwise operations on vectorbool

If the number of bits are fixed at compile time, you would be much better off using std::bitset

If not, (i.e. number of bits varies at runtime), then you should see and can use boost::dynamic_bitset)

In both of these, it is extremely easy to do all the bitwise operations.

Bitwise operations on SINGLE BIT of std::vectorbool. Why the error?

std::vector<bool> is messy in the best case and an abomination in the worst. Its operator[] does not return a bool& but rather a proxy object (see here). This proxy does not have overloads vor all possible bitwise operations, hence you have to use ifs, its operator=(bool) or its flip().

EDIT: I just read your code and not your description what you want to do. Setting the xor of two bits is no problem at all:

out[i] = in[j] ^ in[k]; // Whatever the right indices are.

I think what you actually want to do is along the lines of:

bool tmp = false;
if(foo(i)>0 && foo(i)<in.size())
 tmp^=in[foo(i)];
if(bar(i)>0 && bar(i)<in.size())
 out[i]=tmp^in[bar(i)];

That is, if you want to return in[bar(i)]^in[foo(i)] if both pass the bounds check, return in[j] if only one (here denoted by j) passes the bounds check and false if none of them pass it.

Element-wise OR operation on vectors in C++

Try using std::transform:
http://www.cplusplus.com/reference/algorithm/transform/

// transform algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::transform
#include <vector>       // std::vector
#include <functional>   // std::plus

int op_increase (int i) { return ++i; }

int main () {
  std::vector<int> foo;
  std::vector<int> bar;

  // set some values:
  for (int i=1; i<6; i++)
    foo.push_back (i*10);                         // foo: 10 20 30 40 50

  bar.resize(foo.size());                         // allocate space

  std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
                                                  // bar: 11 21 31 41 51

  // std::plus adds together its two arguments:
  std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
                                                  // foo: 21 41 61 81 101

  std::cout << "foo contains:";
  for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Bitwise operator on two large sparse vectors without looping?

Don't use std::vector<bool> or similar for a sparse array.

A truly sparse array should have the ability to skip over large sections.

Encode your data as block headers, which state how long a region it is in bytes. Use all 1s in the length to say "the length of the length field is twice as long and follows", recursively.

So 0xFF0100 states that there is a block of length 512 following. (you can do a bit better by not permitting 0 nor 1-254, but that is rounding error).

Alternate blocks of "all 0s" with blocks of mixed 1s and 0s.

Don't read the block headers directly; use memcpy into aligned storage.

Once you have this, your | or & operation is more of a stitch than a bitwise operation. Only in the rare case where both have a non-zero block do you actually do bitwise work.

After doing & you might want to check if any of the non-0 regions are actually all 0.

This assumes an extremely sparse bitfield. Like, 1 bit in every few 10000 is set is a typical case. If by sparse you mean "1 in 10", then just use a vector of uint64_t or something.

operator |= on std::vectorbool

The main reason would be that std::vector<bool> is special, and its specification specifically permits an implementation to minimise memory usage.

For vectors of anything other than bool, the reference type can actually be a true reference (i.e. std::vector<int>::reference can actually be an int &) - usually directly referencing an element of the vector itself. So it makes sense for the reference type to support all operations that the underlying type can. This works because vector<int> effectively manages a contiguous array of int internally. The same goes for all types other than bool.

However, to minimise memory usage, a std::vector<bool> may not (in fact probably will not) work internally with an actual array of bool. Instead it might use some packed data structure, such as an array of unsigned char internally, where each unsigned char is a bitfield containing 8 bits. So a vector<bool> of length 800 would actually manage an array of 100 unsigned char, and the memory it consumes would be 100 bytes (assuming no over-allocation). If the vector<bool> actually contained an array of 800 bool, its memory usage would be a minimum of 800 bytes (since sizeof(bool) must be at least 1, by definition).

To permit such memory optimisation by implementers of vector<bool>, the return type of vector<bool>::operator[] (i.e. std::vector<bool>::reference) cannot simply be a bool &. Internally, it would probably contain a reference to the underlying type (e.g. a unsigned char) and information to track what bit it actually affects. This would make all op= operators (+=, -=, |=, etc) somewhat expensive operations (e.g. bit fiddling) on the underlying type.

The designers of std::vector<bool> would then have faced a choice between

1. specify that std::vector<bool>::reference support all the
   op= and hear continual complaints about runtime inefficiency from
   programmers who use those operators

2. Don't support those op= and field complaints from programmers who think such things are okay ("cleaner code", etc) even though they will be inefficient.

It appears the designers of std::vector<bool> opted for option 2. A consequence is that the only assignment operators supported by std::vector<bool>::reference are the stock standard operator=() (with operands either of type reference, or of type bool) not any of the op=. The advantage of this choice is that programmers get a compilation error if trying to do something which is actually a poor choice in practice.

After all, although bool supports all the op= using them doesn't achieve much anyway. For example, some_bool |= true has the same net effect as some_bool = true.

How to perform boolean operations in c++

To perform binary addition in C++, you can use the function described here:
Adding binary numbers in C++

I implemented the function from that link to fit your specifications like this:

std::vector<bool> add(const std::vector<bool>& a, const std::vector<bool>& b)
{
        bool c;
        std::vector<bool> result;
        for(int i = 0; i < a.size() ; i++){
                result.push_back(false);
                result[i] = ((a[i] ^ b[i]) ^ c); // c is carry
                c = ((a[i] & b[i]) | (a[i] & c)) | (b[i] & c);
        }
        return result;
}

This function takes two vectors of bools (and assumes they are the same size) and returns their result vector. Obviously this function doesn't handle overflow or numbers of different sizes. You can modify it yourself if you need those capabilities. Also, you seem to be talking about an overloaded operator for a bool vector, and you can do that by checking out operator overloading, but this logic will allow you to add two boolean numbers stored in vectors.

Using bitwise or equals (|= with a vector

std::vector<bool> is a specialization of a std::vector. This specialization saves space by using 1 bit for each bool, instead of 1 byte.

std::vector<bool>::operator[] returns a reference wrapper(in order to allow this space-save optimization), which apparently does not implement operator|.

---

Related Topics