获得C＆＃x2B;＆＃x2B;的最低设置的最快方法是什么。 std :: bitset？

Question

我注意到 std :: bitset 没有用于返回或弹出的函数位置的最低集合（也不是最高的集合位）。什么是完成此任务的最快方法，特别是对于STD :: BITSET对象，不能保证为一定数量的位长吗？我在G ++编译器扩展程序中查看， c ++ 20 numerics numerics 找到与我的问题有关的任何东西。

要考虑的两种明显的方法将是在比特斯的长度上循环循环，并使用operator []或使用operator＆gt;＆gt;＆gt;逐渐移动位置直至第一个集合位置为成立。

Answer 1

像大多数现代实现一样，我将使用尾随零，以使其易于处理没有设置的情况。要利用硬件计数落后指令，我们可以使用to_ullong（），但是要使它起作用，我们需要掩盖该值以使其适合无符号>未签名的长长

#include <bitset>
#include <bit>
#include <climits>

template<size_t N>
size_t count_trailingzero(std::bitset<N> b)
{
    if (b.none())
        return N;                   // The whole bitset was zero

    const decltype(b) mask(-1ULL);  // Mask to get the lowest unsigned long long
    size_t tz = 0;                  // The number of trailing zero bits
    const int width = sizeof(unsigned long long)*CHAR_BIT;
    do {
        auto lsw = (b & mask).to_ullong();  // The least significant word
        auto lsb = std::countr_zero(lsw);   // Position of the least significant bit

        if (lsb < width)                    // Found the first set bit from right
            return tz + lsb;
        
        // A set bit was not found because the lsw is all zero
        // so we'll increase the number of trailing zero bits
        tz += width;

        // Shift the bitset to get the next higher significant word
        b >>= width;
    } while (b.any());

    return tz;
}

Demo on Godbolt< /a>

以这种方式，不需要对单个位进行循环，并且可以使用硬件加速度。但这仍然不是最有效的方法，因为每次迭代仍然需要掩盖整个bitset。这就是为什么std :: bitset不是一般操作的好工具，而我总是在实践中避免使用它们。将阵列包装钻头操作的课程在性能和灵活性方面会更好

Answer 2

没有.lsb（）或.msb（）成员函数，但是std :: bitset确实提供.size（）在“> @phuctv 用于.yany（） .count（）），您可以在其中构造LSB和MSB例程。

假设有效的std :: bitset您可以使用.yany（）（）（或仅检查未符号值），验证至少一个位是TRUE设置的。验证至少一个位是正确的，只需从bit-0循环到bit-（bitset.size（） - 1）使用检查设置位.test（）获得LSB。然后，只需在相同的测试中反向循环以找到MSB。

简短的实现将是：

#include <iostream>
#include <bitset>

int main () {
  
  size_t i = 0;                 /* bit indiex */
  std::bitset<8> bits (236);    /* bitset '11101100' */
  
  if (!bits.any()) {  /* validate at least 1 bit set */
    std::cerr << "pop count is zero.\n";
    return 1;
  }
  
  /* loop bit 0 to bits.size() - 1 for LSB */
  do {
    if (bits.test(i))             /* test if bit set */
      break;
  } while (++i < bits.size());
  
  std::cout << "lsb in '" << bits << "' is: " << i << '\n';
  
  /* loop bit bits.size() - 1 to 0 for MSB */
  i = bits.size();
  while (i--) {
    if (bits.test(i))             /* test if bit set */
      break;
  }
  
  std::cout << "msb in '" << bits << "' is: " << i << '\n';
}

示例使用/输出

$ ./bin//bitset_test
lsb in '11101100' is: 2
msb in '11101100' is: 7

---

扩展了std :: bitset并添加.lsb（） and .msb（）成员函数

除了简单地编写几个功能外，您还可以从std :: bitset添加.lsb（）和。 MSB（）成员函数到派生类。

使用以上相同实现的简短类声明可能是：

template<size_t Nb>
class mybitset : public std::bitset<Nb> {
  
  std::bitset<Nb> bits;
  
 public:
  mybitset (const std::bitset<Nb>&b) : std::bitset<Nb>{b} { bits = b; }
  
  size_t lsb();     /* extend std::bitset with .lsb() and .msb() members */
  size_t msb();
  
  template<size_t NB>
  friend std::ostream& operator << (std::ostream& os, const mybitset<NB>& b);
};

然后您可以直接使用.lsb（）和.msb（）成员，例如

int main () {
  
  mybitset<8> bits (236);       /* derived class */
  
  if (!bits.any()) {  /* validate at least one bit set */
    std::cerr << "bitset value is zero -- zero pop count.\n";
    return 1;
  }
  
  /* output LSB and MSB */
  std::cout << "lsb in '" << bits << "' is: " << bits.lsb() <<
             "\nmsb in '" << bits << "' is: " << bits.msb() << '\n';
}

（相同的输出）

Answer 3

有点较晚的答案，C ++ 20包括 ＆lt; /代码>具有您想要的功能。

特别是 std :: countr_zero 连续0位的数量从最小显着的位开始。

#include <bit>
#include <iostream>

// This requires C++20 (or later)

int main() {
  std::cout << "lsb of 0b0100u is " << std::countr_zero(0b0100u) << "\n";
}

// std::countr_zero(0b0100u) is 2.

Answer 4

您可以做这样的事情：

#include <bitset>
#include <iostream>
int main(int argc, char **argv) {
  std::bitset<32> your_bit{0B1010000};
  int lsb = your_bit[0];
  std::cout << lsb << '\n';
}