3 ways to toggle a bit represented as a char

Question

I wrote this:

#include <iostream>
#include <vector>

int main()
{
    std::vector<char> v = {0, 0, 0};
    v[0] = v[0] == 0 ? 1 : 0;
    v[1] = !v[1];
    v[2] ^= 1;
    std::cout << (int)v[0] << (int)v[1] << (int)v[2] << "\n";
    return 0;
}

which toggles all bits, but I actually care on changing only the i-th bit.

What am I interested in is which one of these ways should one use in a c++ project, when the only thing that you care is speed (not memory and readability)?

---

The reason for using std::vector<char> as a bitset is that in my timings I found that it's faster than a vector of ints or chars, and std::bitset.

Fungible

What do you mean by "which one should I use" -- clearly only one of the four operations produces the correct result?! – Upanddown

Kerrek updated! @Thriller I am not experienced, can you please explain? – Fungible

xor and the first two have different semantics (for initial values different from 0 or 1). – Nicker

do you mean: v[2] ^= 1; instead of v[3] – Thriller

the result is ok 111 but you may wanted: v[2] ^= 1; not v[3] – Thriller

First of all stop using vector<char>. I know what you're doing with them from your previous questions, and there is just no way that following a pointer to a bunch of chars is ever faster than just having the bits right there in an integer. – Spyglass

@harold: you mean for example as long as its a vector<char> which can be assigned values non-bool?? do you recommend bitset? – Thriller

@Thriller well he's using them as bitset. As for the actual std::bitset, sometimes it has overhead when an index can't be proven to be in range statically, but it's generally fine. It's not very flexible though so you'd often end up calling to_ulong on it, do some operation, then convert back.. – Spyglass

@harold my choice for std::vector<char> is really driven by my timings. Moreover, there is a function to get the results I eventually need based on my previous questions. I would be happy to change if there is reason. – Fungible

Answer 1

You can instead use either std::bitset as long as you are interested in bits or use directly vector of bool not char:

#include <iostream>
#include <vector>

int main()
{
    std::vector<bool> v = { 0, 0, 0 };

    for (int i(0); i < v.size(); i++)
        v[i] = !v[i];

    for (int i(0); i < v.size(); i++)
        std::cout << (int)v[i];

    std::cout << std::endl;

    std::cin.get();
    return 0;
} 

• the bitwise not ! is recommended due to its speed and cleanness.

Thriller

std::vector<bool> is said to be slow and my timings over vectors of ints, chars and bools, as well as std::bitset agree. std::bitset seems to be a choice when memory is of main important, the timings drove me to use std::vector<char>, since I care about speed. So for the vector of chars, you still think that ! is faster? Forget about readability for a second. – Fungible

I posted an answer with some timings, please take a look, you might spot any mistake, if there is one! :) Thank you for your time! – Fungible

@gsamaras: I am sorry I meant logical not not bitwise negation operator ~ – Thriller

Answer 2

Following Raindrop7's answer, I decided to base on How-to-store-binary-data-when-you-only-care-about-speed? and do a Time Measurement with this code:

#include <ctime>
#include <ratio>
#include <chrono>
#include <iostream>
#include <vector>
#include <random>

#define T int

std::uniform_int_distribution<int> uni_bit_distribution(0, 1);
std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());

// g++ -Wall -std=c++0x -O3 toggle_all_bits_one_by_one.cpp
int main()
{
    const int N = 1000000;
    const int D = 100;

    using namespace std::chrono;
    high_resolution_clock::time_point t1 = high_resolution_clock::now();


    std::vector<T> v;
    v.resize(N * D);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < D; ++j)
            v[j + i * D] = uni_bit_distribution(generator);


    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    duration<double> time_span = duration_cast<duration<double> >(t2 - t1);

    std::cout << "Build " << time_span.count() << " seconds.\n";

    t1 = high_resolution_clock::now();

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < D; ++j)
            //v[j + i * D] = v[j + i * D] == 0 ? 1 : 0;
            // Build 3.95191 seconds. Time to toggle all bits one by one 0.0490182 seconds.
            //v[j + i * D] = !v[j + i * D];
            // Build 3.82705 seconds. Time to toggle all bits one by one 0.0477722 seconds.
            v[j + i * D] ^= 1;
            // Build 3.74881 seconds. Time to toggle all bits one by one 0.046955 seconds.

    t2 = high_resolution_clock::now();
    time_span = duration_cast<duration<double> >(t2 - t1);
    std::cout << "Time to toggle all bits one by one " << time_span.count() << " seconds.\n";

    return 0;
}

which on my machine prove that little effect does the method selection gives, as expected. So, in general, focus on readability.

---

For #define T char, I got:

v[j + i * D] = v[j + i * D] == 0 ? 1 : 0;
// Build 3.65369 seconds. Time to toggle all bits one by one 0.0580222 seconds.
//v[j + i * D] = !v[j + i * D];
// Build 3.65898 seconds. Time to toggle all bits one by one 0.0573292 seconds.
//v[j + i * D] ^= 1;
// Build 3.95643 seconds. Time to toggle all bits one by one 0.0570291 seconds.

Fungible