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.

What do you mean by "which one should I use" -- clearly only *one* of the four operations produces the correct result?! — Kerrek SB, Nov 26 '16 at 13:23
Kerrek updated! @Raindrop7 I am not experienced, can you please explain? — gsamaras, Nov 26 '16 at 13:32
xor and the first two have different semantics (for initial values different from 0 or 1). — krzaq, Nov 26 '16 at 13:34
the result is ok `111` but you may wanted: `v[2] ^= 1;` not `v[3]` — Raindrop7, Nov 26 '16 at 13:37
First of all stop using `vector`. 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. — harold, Nov 26 '16 at 13:39
@harold: you mean for example as long as its a vector which can be assigned values non-bool?? do you recommend bitset? — Raindrop7, Nov 26 '16 at 13:42
@Raindrop7 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.. — harold, Nov 26 '16 at 13:52
@harold my choice for `std::vector` is really driven by [my timings](http://stackoverflow.com/questions/40773463/how-to-store-binary-data-when-you-only-care-about-speed/40793069#40793069). Moreover, [there is a function](http://stackoverflow.com/questions/40813022/generate-all-sequences-of-bits-within-hamming-distance-t) to get the results I eventually need based on my previous questions. I would be happy to change if there is reason. — gsamaras, Nov 26 '16 at 15:19

score 1 · Accepted Answer · edited Nov 26 '16 at 15:22

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.

edited Nov 26 '16 at 15:22

gsamaras

71,951
46
188
305

answered Nov 26 '16 at 14:16

Raindrop7

3,889
3
16
27

1

`std::vector` is said to be slow and [my timings over vectors of ints, chars and bools, as well as std::bitset](http://stackoverflow.com/questions/40773463/how-to-store-binary-data-when-you-only-care-about-speed/40793069#40793069) agree. `std::bitset` seems to be a choice when memory is of main important, the timings drove me to use `std::vector`, since I care about speed. So for the vector of *char*s, you still think that `!` is faster? Forget about readability for a second. – gsamaras Nov 26 '16 at 15:23
1

I posted an [answer](http://stackoverflow.com/a/40820206/2411320) with some timings, please take a look, you might spot any mistake, if there is one! :) Thank you for your time! – gsamaras Nov 26 '16 at 16:01
@gsamaras: I am sorry I meant `logical not` not bitwise negation operator `~` – Raindrop7 Nov 26 '16 at 20:21

score 1 · Answer 2 · edited May 23 '17 at 11:59

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.

3 ways to toggle a bit represented as a char

2 Answers2

Linked