C++快速位集短路按位运算

发布于 2024-12-18 20:50:18 字数 1160 浏览 3 评论 0原文

演示问题：给定两个 std::bitset，a 和 b 检查两个 中是否设置了任何位a 和 b。

对于这个问题有两个相当明显的解决方案。这很糟糕，因为它创建了一个新的临时位集，并将值复制到各种位置只是为了将它们丢弃。

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    return (a & b).any();
}

这个解决方案很糟糕，因为它一次一位，这不太理想：

template <size_t N>
bool any_both_bit_by_bit(const std::bitset<N>& a, const std::bitset<N>& b)
{
    for (size_t i = 0; i < N; ++i)
        if (a[i] && b[i])
            return true;
    return false;
}

理想情况下，我能够做这样的事情，其中 block_type 是 uint32_t 或无论 bitset 存储什么类型：

template <size_t N>
bool any_both_by_block(const std::bitset<N>& a, const std::bitset<N>& b)
{
    typedef std::bitset<N>::block_type block_type;
    for (size_t i = 0; i < a.block_count(); ++i)
        if (a.get_block(i) & b.get_block(i))
            return true;
    return false;
}

有没有一种简单的方法可以做到这一点？

原文

A demo problem: Given two std::bitset<N>s, a and b check if any bit is set in both a and b.

There are two rather obvious solutions to this problem. This is bad because it creates a new temporary bitset, and copies values all sorts of places just to throw them away.

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    return (a & b).any();
}

This solution is bad because it goes one bit at a time, which is less than ideal:

template <size_t N>
bool any_both_bit_by_bit(const std::bitset<N>& a, const std::bitset<N>& b)
{
    for (size_t i = 0; i < N; ++i)
        if (a[i] && b[i])
            return true;
    return false;
}

Ideally, I would be able to do something like this, where block_type is uint32_t or whatever type the bitset is storing:

template <size_t N>
bool any_both_by_block(const std::bitset<N>& a, const std::bitset<N>& b)
{
    typedef std::bitset<N>::block_type block_type;
    for (size_t i = 0; i < a.block_count(); ++i)
        if (a.get_block(i) & b.get_block(i))
            return true;
    return false;
}

Is there an easy way to go about doing this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

森林散布 2024-12-25 20:50:18

我用 g++ 优化编译了您的第一个示例，它生成的代码与您的第三个解决方案相同。事实上，使用较小的位集（320 位）就可以完全展开它。如果没有调用函数来确保 a 和 b 的内容在 main 中是未知的，它实际上优化了整个事情（知道两者都是） 0）。

教训：编写明显、可读的代码并让编译器处理它。

回复收藏 0 原文

南城旧梦 2024-12-25 20:50:18

您说您的第一种方法“复制各种位置的值只是为了将它们丢弃”。但实际上只有一个额外的值复制（当 operator& 的结果返回到 any_both_new_temp 时），并且可以通过使用引用而不是值来消除它：

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    std::bitset<N> tmp = a;
    tmp &= b;
    return tmp.any();
}

（但显然它仍然会创建一个临时 bitset 并将 a 复制到其中。）

You say that your first approach "copies values all sorts of places just to throw them away." But there's really only one extra value-copy (when the result of operator& is returned to any_both_new_temp), and it can be eliminated by using a reference instead of a value:

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    std::bitset<N> tmp = a;
    tmp &= b;
    return tmp.any();
}

(But obviously it will still create a temporary bitset and copy a into it.)

回复收藏 0 原文

~没有更多了~