>

다음과 같이 비트 조작을 용이하게하는 툴 세트를 만들었습니다. 인터페이스 디자인, 구현 또는 이름 지정에 대한 의견이 있으면 언제든지 환영합니다. 또한 도구 세트에 유스 케이스를위한 것이 부족하지 않은지 확인하고 싶습니다. :-) 원래 코드 및 단위 테스트를 찾을 수 있습니다 여기 및 여기 .

/// The index is zero-based, starting from the least significant bit.
/// The most significant bit or sign bit is the head bit.
template <typename T>
constexpr unsigned num_bits(T = 0) {
  return sizeof(T) << 3;
}
template <typename T>
constexpr unsigned head_bit_idx(T = 0) {
  return num_bits<T>() - 1;
}
template <typename T>
T bit_flag(unsigned idx) {
  // since C++14, `1 << (num_bits<int> - 1)` is well-defined and makes `INT_MIN`
  return static_cast<T>(1) << idx;
}
template <typename T>
constexpr T head_bit_flag() {
  return static_cast<T>(1) << head_bit_idx<T>();
}
template <typename T>
bool test_bit(T x, unsigned idx) {
  return x & bit_flag<T>(idx);
}
template <typename T>
bool test_head_bit(T x) {
  return test_bit(x, head_bit_idx(x));
}
template <typename T>
T set_bit(T x, unsigned idx) {
  return x | bit_flag<T>(idx);
}
template <typename T>
T set_head_bit(T x) {
  return set_bit(x, head_bit_idx<T>());
}
template <typename T>
T clear_bit(T x, unsigned idx) {
  return x & ~bit_flag<T>(idx);
}
template <typename T>
T clear_head_bit(T x) {
  return clear_bit(x, head_bit_idx<T>());
}
template <typename T>
T flip_bit(T x, unsigned idx) {
  return x ^ bit_flag<T>(idx);
}
template <typename T>
T flip_head_bit(T x) {
  return flip_bit(x, head_bit_idx<T>());
}
template <typename T>
unsigned num_bits_set(T x) {
  unsigned cnt = 0;
  // behavior of signed type underflow is unspecified
  std::make_unsigned_t<T> v = x;
  while (v) {
    ++cnt;
    v &= v - 1;
  }
  return cnt;
}

  • 답변 # 1

    template <typename T>
    constexpr unsigned num_bits(T = 0) {
      return sizeof(T) << 3;
    }
    
    

    완전한 일반성을 위해서는 std::numeric_limits 를 사용해야합니다 . 와이즈 비즈  부호없는 비트 수를 알려줍니다. 와이즈 비즈  필요한 경우 부호 비트에 1을 추가 할 수 있도록 유형의 부호 여부를 알려줍니다. 귀하의 코드는 numeric_limits<T>::digits 를 가정하고 있습니다.  그리고 그 numeric_limits<T>::is_signed  패딩 비트가 없으며 둘 다 사실이 아닙니다.

    CHAR_BIT == 8  popcount이며 실제로 T 로 구현해야합니다. 는 GCC의 num_bits_set 와 같은 컴파일러 내장 함수를 사용하여 매우 효율적으로 구현됩니다.  (차례로 차례로 단일 std::bitset::count() 로 컴파일됩니다.  가능한 경우 교육).

  • 답변 # 2

    잘못된 최적화 (읽기 어렵게 함)

    __builtin_popcount()
    
    

    이것은 popcnt 여야합니다  읽기가 훨씬 쉽습니다. 그리고 그것이 더 빨리 바뀌면 컴파일러가 실제로 할 일입니다. 컴파일러를 능가하려고하지 마십시오. 앞으로 일어날 일은 유일하게 자신을 능가하는 것입니다.

    또한 실제로는 그렇지 않습니다. 8. 준수하고 정확한 사용 template <typename T> constexpr unsigned num_bits(T = 0) { return sizeof(T) << 3; } .

    이것은 약간 비효율적입니다.

    sizeof(T) * 8
    
    

    각 루프에서 런타임 루프를 사용하고 있습니다. 각 바이트에 컴파일 타임 루프를 사용할 수 있습니다. 바이트의 각 특정 값에 대해 비트 수가 설정되므로 미리 계산하기가 쉽습니다.

    참고 : 각 바이트마다 CHAR_BIT 만 있습니다  비트 수 (보통 8). 256 개의 값입니다. 따라서 여기에서 시간을위한 공간을 단일 바이트로 교체 할 수 있습니다.

    template <typename T>
    unsigned num_bits_set(T x) {
      unsigned cnt = 0;
      // behavior of signed type underflow is unspecified
      std::make_unsigned_t<T> v = x;
      while (v) {
        ++cnt;
        v &= v - 1;
      }
      return cnt;
    }
    
    

    전체적으로 괜찮습니다. 그러나 CHAR_BIT 를 사용하여 동일한 기능을 얻을 수 있습니다  더 읽기 쉽습니다.

    unsigned num_bits_set_count_value[] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  // 000-015
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  // 016-031
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  // 032-047
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 048-063
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  // 064-079
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 080-095
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 096-111
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  // 112-127
    // ---
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  // 128-143
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 144-159
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 160-175
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  // 176-191
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  // 192-207
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  // 208-223
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  // 224-239
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; // 240-255
    // Use compile time meta program
    // to unwind a multi byte value into a set of adds
    // these will all be inlined.
    template <int x>
    unsigned num_bits_set_count(char const* byteStream) {
        return num_bits_set_count_value[*byteStream]
             + num_bits_set_count<x - 1>(byteStream + 1);
    }
    template<> unsigned num_bits_set_count<0>(char const*) {return 0;}
    template <typename T>
    unsigned num_bits_set(T x) {
       return num_bits_set_count<sizeof(T)>(reinterpret_cast<char const*>(&x));
    }
    
    

  • 답변 # 3

    전체적으로 이것은 이것이 매우 간단한 구현이라고 생각합니다. 이해하기 쉽습니다. 다음과 같은 개선 사항이 있습니다.

    정확한 정확성

    모든 매개 변수를 std::bitset 로 만들어야합니다 . 모든 경우에 사본을 반환하거나 매개 변수가 색인입니다. 그들을 int a {86}; std::bitset<sizeof(a) * CHAR_BIT> x(a); // test bit 5 x[5] // set bit 5 x[5] |= 1; // reset bit 5 x[5] ^= 1; 로 표시  경우에 따라 컴파일러에서 최적화를 수행 할 수 있습니다.

    와이즈 비즈 사용 const 를 특별 케이싱의 목적은 무엇입니까  비트? 부호 비트 인 경우를 제외하고, 특수하게 만드는 데 충분한 사례가 있습니까? (나는 그것이 즉시 나에게 명백하지 않다는 것을 믿을 수있다.) 나는 비트에 대해 비트 조작을 사용하는 경향이있다. (실제로 const 를 사용했습니다.  그러나 이번 주에 처음으로!) 함수 사용자가 높은 비트를 가져 오거나 설정해야하는 경우가 많으면 유지하십시오. 그렇지 않으면 많이 추가 될지 모르겠습니다.

    이름 지정

    전체적으로 명명이 훌륭합니다. 나는 head 를 선호합니다  그리고 head   std::sign_bit() 로  그리고 set . 단어 clear  내 마음에 약간의 지우기를 트리거하지 않습니다.

    와이즈 비즈를 지키려고한다면   set 의 다른 이름을 고려할 수도 있습니다. . 나는 reset 라는 높은 비트를들은 적이 없다  비트. 이름을 reset 로 바꿀 수 있습니다 head  또는 비슷한 것. 목적이 주로 숫자 값의 부호 비트를 다루는 것이라면 head 로 이름을 지정할 수 있습니다.  그리고 head

    무엇이 누락 되었습니까?

    유용 할 수있는 몇 가지 다른 것들만 봤는데, 80 %가 아닙니다. 첫 번째 (가장 높은) 비트 세트의 위치를 ​​결정 해야하는 경우를 보았습니다. 그래서 당신은 high_bit_idx() 와 같은 기능을 가질 수 있습니다  또는 그런 것.

    이를 비트 스트림으로 확장하면 처리하는 형식의 비트가 아닌 무제한의 비트를 처리 할 수 ​​있습니다. 물론 더 복잡합니다. 이미지 압축을 다룰 때 전에이 작업을 수행했습니다.

    high_bit_flag()

  • 이전 performance - TI-84의 이중 적분 솔버
  • 다음 리눅스 C 포트 노크 구현