切换表示为字符的位的 3 种方法

Question

我写了这个：

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

它切换所有位，但我实际上只关心更改第 i 个位。

我感兴趣的是，当您唯一关心的是速度（而不是内存和可读性）时，应该在 c++ 项目中使用这些方法中的哪一种？

使用std::vector<char>作为bitset的原因是.

Answer 1

只要您对位感兴趣，您可以改用 std::bitset 或直接使用 bool 的向量而不是 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;
}

推荐 bitwise not ! 因为它的速度和清洁度。

Answer 2

根据 Raindrop7 的回答，我决定基于并使用以下代码进行时间测量：

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

这在我的机器上证明了方法选择的影响很小，正如预期的那样。所以，总的来说，关注可读性。

对于#define T char，我得到：

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 种方法

3 ways to toggle a bit represented as a char

c++

algorithm

bit-manipulation

vector

toggle