Ale*_*ing 113 c++ bit-manipulation c++11
我有一些或多或少像这样的代码:
#include <bitset>
enum Flags { A = 1, B = 2, C = 3, D = 5,
E = 8, F = 13, G = 21, H,
I, J, K, L, M, N, O };
void apply_known_mask(std::bitset<64> &bits) {
const Flags important_bits[] = { B, D, E, H, K, M, L, O };
std::remove_reference<decltype(bits)>::type mask{};
for (const auto& bit : important_bits) {
mask.set(bit);
}
bits &= mask;
}
Clang> = 3.6做聪明的事情并将其编译为单个and指令(然后在其他地方内联):
apply_known_mask(std::bitset<64ul>&): # @apply_known_mask(std::bitset<64ul>&)
and qword ptr [rdi], 775946532
ret
但是我试过的每个版本的GCC都将这个编译成一个巨大的混乱,其中包括应该静态DCE的错误处理.在其他代码中,它甚至可以将important_bits等效数据作为数据与代码一致!
.LC0:
.string "bitset::set"
.LC1:
.string "%s: __position (which is %zu) >= _Nb (which is %zu)"
apply_known_mask(std::bitset<64ul>&):
sub rsp, 40
xor esi, esi
mov ecx, 2
movabs rax, 21474836482
mov QWORD PTR [rsp], rax
mov r8d, 1
movabs rax, 94489280520
mov QWORD PTR [rsp+8], rax
movabs rax, 115964117017
mov QWORD PTR [rsp+16], rax
movabs rax, 124554051610
mov QWORD PTR [rsp+24], rax
mov rax, rsp
jmp .L2
.L3:
mov edx, DWORD PTR [rax]
mov rcx, rdx
cmp edx, 63
ja .L7
.L2:
mov rdx, r8
add rax, 4
sal rdx, cl
lea rcx, [rsp+32]
or rsi, rdx
cmp rax, rcx
jne .L3
and QWORD PTR [rdi], rsi
add rsp, 40
ret
.L7:
mov ecx, 64
mov esi, OFFSET FLAT:.LC0
mov edi, OFFSET FLAT:.LC1
xor eax, eax
call std::__throw_out_of_range_fmt(char const*, ...)
我应该如何编写这段代码,以便两个编译器都可以做正确的事情？如果做不到这一点,我应该如何写它以保持清晰,快速和可维护？
Yak*_*ont 111
最佳版本是c ++ 17:
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return ((1ull<<indexes)|...|0ull);
}
然后
void apply_known_mask(std::bitset<64> &bits) {
constexpr auto m = mask<B,D,E,H,K,M,L,O>();
bits &= m;
}
回到c ++ 14,我们可以做这个奇怪的伎俩:
template< unsigned char... indexes >
constexpr unsigned long long mask(){
auto r = 0ull;
using discard_t = int[]; // data never used
// value never used:
discard_t discard = {0,(void(
r |= (1ull << indexes) // side effect, used
),0)...};
(void)discard; // block unused var warnings
return r;
}
或者,如果我们坚持使用c ++ 11,我们可以递归地解决它:
constexpr unsigned long long mask(){
return 0;
}
template<class...Tail>
constexpr unsigned long long mask(unsigned char b0, Tail...tail){
return (1ull<<b0) | mask(tail...);
}
template< unsigned char... indexes >
constexpr unsigned long long mask(){
return mask(indexes...);
}
所有3的Godbolt - 您可以切换CPP_VERSION定义,并获得相同的程序集.
在实践中,我会使用最现代化的.14节拍11因为我们没有递归,因此O(n ^ 2)符号长度(可以爆炸编译时间和编译器内存使用); 由于编译器没有死代码消除该数组,因此该数组技巧只是丑陋.
其中14个是最令人困惑的.在这里,我们创建一个全0的匿名数组,同时作为副作用构造我们的结果,然后丢弃数组.它的数量为0,等于我们的包的大小,再加上1(我们添加,因此我们可以处理空包).
Sne*_*tel 47
您正在寻找的优化似乎是循环剥离,可以启用-O3或手动启用-fpeel-loops.我不确定为什么这属于循环剥离的范围而不是循环展开,但可能它不愿意在其中展开具有非局部控制流的循环(因为可能来自范围检查).
但是,默认情况下,GCC无法剥离所有迭代,这显然是必要的.通过实验,传递-O2 -fpeel-loops --param max-peeled-insns=200(默认值为100)可以使用原始代码完成工作:https://godbolt.org/z/NNWrga
Sta*_*nny 10
如果仅使用C++ 11则必须(&a)[N]采用捕获数组的方法.这允许您编写一个单独的递归函数,而无需使用任何辅助函数:
template <std::size_t N>
constexpr std::uint64_t generate_mask(Flags const (&a)[N], std::size_t i = 0u){
return i < N ? (1ull << a[i] | generate_mask(a, i + 1u)) : 0ull;
}
将其分配给constexpr auto:
void apply_known_mask(std::bitset<64>& bits) {
constexpr const Flags important_bits[] = { B, D, E, H, K, M, L, O };
constexpr auto m = generate_mask(important_bits); //< here
bits &= m;
}
int main() {
std::bitset<64> b;
b.flip();
apply_known_mask(b);
std::cout << b.to_string() << '\n';
}
0000000000000000000000000000000000101110010000000000000100100100
// ^ ^^^ ^ ^ ^ ^
// O MLK H E D B
一个人真的必须欣赏C++在编译时计算任何可计算的东西的能力.它肯定会让我感到震惊(<>).
对于更高版本的C++ 14和C++ 17,yakk的答案已经很好地涵盖了这一点.
我鼓励你写一个合适的EnumSet类型.
EnumSet<E>在C++ 14(以后)基础上编写基础std::uint64_t是微不足道的:
template <typename E>
class EnumSet {
public:
constexpr EnumSet() = default;
constexpr EnumSet(std::initializer_list<E> values) {
for (auto e : values) {
set(e);
}
}
constexpr bool has(E e) const { return mData & mask(e); }
constexpr EnumSet& set(E e) { mData |= mask(e); return *this; }
constexpr EnumSet& unset(E e) { mData &= ~mask(e); return *this; }
constexpr EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
constexpr EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
std::uint64_t mData = 0;
};
这允许您编写简单的代码:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };
flags &= IMPORTANT;
}
在C++ 11中,它需要一些卷积,但仍然有可能:
template <typename E>
class EnumSet {
public:
template <E... Values>
static constexpr EnumSet make() {
return EnumSet(make_impl(Values...));
}
constexpr EnumSet() = default;
constexpr bool has(E e) const { return mData & mask(e); }
void set(E e) { mData |= mask(e); }
void unset(E e) { mData &= ~mask(e); }
EnumSet& operator&=(const EnumSet& other) {
mData &= other.mData;
return *this;
}
EnumSet& operator|=(const EnumSet& other) {
mData |= other.mData;
return *this;
}
private:
static constexpr std::uint64_t mask(E e) {
return std::uint64_t(1) << e;
}
static constexpr std::uint64_t make_impl() { return 0; }
template <typename... Tail>
static constexpr std::uint64_t make_impl(E head, Tail... tail) {
return mask(head) | make_impl(tail...);
}
explicit constexpr EnumSet(std::uint64_t data): mData(data) {}
std::uint64_t mData = 0;
};
并调用:
void apply_known_mask(EnumSet<Flags>& flags) {
static constexpr EnumSet<Flags> IMPORTANT =
EnumSet<Flags>::make<B, D, E, H, K, M, L, O>();
flags &= IMPORTANT;
}
即使是GCC 也会and在-O1 godbolt上产生一些指令:
apply_known_mask(EnumSet<Flags>&):
and QWORD PTR [rdi], 775946532
ret
从C++ 11开始,您还可以使用经典的TMP技术:
template<std::uint64_t Flag, std::uint64_t... Flags>
struct bitmask
{
static constexpr std::uint64_t mask =
bitmask<Flag>::value | bitmask<Flags...>::value;
};
template<std::uint64_t Flag>
struct bitmask<Flag>
{
static constexpr std::uint64_t value = (uint64_t)1 << Flag;
};
void apply_known_mask(std::bitset<64> &bits)
{
constexpr auto mask = bitmask<B, D, E, H, K, M, L, O>::value;
bits &= mask;
}
链接到编译器资源管理器:https://godbolt.org/z/Gk6KX1
这种方法优于模板constexpr函数的优点是,由于Chiel的规则,编译可能稍微快一点.