3
\$\begingroup\$

I made a tool set to facilitate bit manipulation as follows. Any comments are welcome, be it about the interface design, the implementation, or even the naming. Also, I want to make sure that the tool set is not lacking something for use-cases I failed to catch :-) Original code and unit tests can be found here and here.

/// 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;
}
\$\endgroup\$
2
  • \$\begingroup\$ What's the advantage of this over std::bitset? \$\endgroup\$ Commented Feb 1, 2016 at 4:15
  • \$\begingroup\$ @T.C. I don't actually need a bit stream, and std::bitset is a little heavy and inconvenient for me. \$\endgroup\$ Commented Feb 1, 2016 at 4:26

3 Answers 3

Reset to default
2
\$\begingroup\$ 
template <typename T>
constexpr unsigned num_bits(T = 0) {
  return sizeof(T) << 3;
}

For full generality, you should use std::numeric_limits. numeric_limits<T>::digits tells you the number of non-sign bits; numeric_limits<T>::is_signed tell you whether the type is signed so you can add 1 for the sign bit if needed. Your code is assuming that CHAR_BIT == 8 and that T has no padding bits, neither of which is necessarily true.

num_bits_set is the popcount, and should really be implemented with std::bitset::count(), which is very efficiently implemented, possibly using a compiler intrinsic such as GCC's __builtin_popcount() (which in turn is compiled down to a single popcnt instruction where possible).

\$\endgroup\$
4
  • \$\begingroup\$ Yes. I should have used CHAR_BIT instead of hard-coded 8. But is there any advantage in using std::numeric_limits over CHAR_BIT? Also, std::numeric_limits may not be specialized for each arithmetic type. I think sizeof(T) takes padding bits into account. No? std::bitset doesn't seem to have a constructor for signed integer types. Guess I will have to cast it to its unsigned counterpart of the same size, as then use that to construct the std::bitset. I didn't know that std::bitset::count() may be highly optimized. Thanks for the info :-) \$\endgroup\$ Commented Feb 1, 2016 at 4:49
  • 1
    \$\begingroup\$ @Lingxi The point is that you don't want to consider padding bits. Also, numeric_limits is specialized for every arithmetic type - eel.is/c++draft/limits#limits.numeric-2 \$\endgroup\$ Commented Feb 1, 2016 at 4:50
  • \$\begingroup\$ Learned a lot from you, as always. Gonna update the code~ \$\endgroup\$ Commented Feb 1, 2016 at 5:08
  • \$\begingroup\$ std::bitset::count() is not constexpr specified :-( This isn't much a problem. Just a little pity. \$\endgroup\$ Commented Feb 1, 2016 at 5:19
3
\$\begingroup\$

False optimization (and makes it hard to read).

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

This should be sizeof(T) * 8 that's so much easier to read. And if it quicker to shift that is what the compiler will actually do. Don't try and outsmart the compiler the only thing that will is happen is that you will outsmart yourself.

Also its not actually 8. TO be compliant and accurate use CHAR_BIT.

This is a bit inefficient.

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

You are using a runtime loop (over each bit). You could use a compile time loop over each byte. Because the number of bits set for each specific value for a byte it is easy to pre-calculate.

Note: For each byte there are only CHAR_BIT number of bits (usually 8). Which is 256 values. So you can swap space for time here for a single byte.

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

Overall its fine. But you can get the same functionality from using std::bitset and its more readable.

 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;
\$\endgroup\$
2
  • \$\begingroup\$ The false optimization and CHAR_BIT is a nice catch. Just updated the library code. The optimized num_bits_set() is inspiring, but a little too much. I don't think I will actually use it. Besides, it does memory access quite a bit. This overhead should be taken into account. As to std::bitset, I don't actually need a bit stream, and std::bitset is a little heavy and inconvenient for me. \$\endgroup\$ Commented Feb 1, 2016 at 4:38
  • \$\begingroup\$ Besides, it does memory access quite a bit: It fits in a single cache line. So multiple access is no slower than a single access. It's also how all the is<X>(char) like isspace() etc work. It will be your fastest technique. std::bitset is NOT a stream. its a very simple wrapper usually around a long (or multiple longs if size > 32). So it would add no cost and simplify your code. \$\endgroup\$ Commented Feb 1, 2016 at 19:00
2
\$\begingroup\$

Overall I think this is a really good straightforward implementation. It's easy to understand. Here are some improvements that I see:

Const Correctness

You should be making all of the parameters const. In all cases you're either returning a copy or the parameter is an index. Marking them as const can let the compiler do optimizations in some cases.

Use of head

What's the purpose of special casing the head bit? Aside from the case where it's the sign bit, are there enough cases to warrant making it special? (I can believe there are, it's just not immediately obvious to me.) I tend to use bit manipulation on flags, and not so much on numbers. (I did actually use std::sign_bit() for the first time just this week, though!) If there are a lot of cases where users of your functions will need to get/set the high bit, then keep it. Otherwise, I'm not sure it adds much.

Naming

Overall, the naming is great. I much prefer set and clear to set and reset. The word reset does not trigger clearing a bit in my mind.

If you are going to keep the head functions, you might consider a different name for head. I've never heard the high bit called the head bit. You could rename them as high_bit_idx(), high_bit_flag() or something similar. If the purpose is mainly for dealing with sign bits on numeric values you could name them sign_bit_idx() and sign_bit_flag(), etc.

What's missing?

I've only run into a few other things that might be useful, and these are definitely not 80% cases. I've seen cases where you need to determine the position of the first (highest) bit set. So you could have a function like find_highest_set_bit(T x) or something like that.

It could be useful to extend this to a bit stream, where you handle an unlimited number of bits, rather than just the bits in the type you're dealing with. That's more complicated, of course. I've done this before when dealing with image compression.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the detailed review. It does help! 1) I made all functions constexpr. As such, it's unnecessary to further const-qualify the parameters. 2) The head family is mainly a convenient shorthand to save you from typing num_bits() - 1 or head_bit_idx(). I guess I will just keep them along. 3) After a second thought, head IS a bad name. It doesn't following any existing practice. I renamed it to MSB which is widely known as a shorthand for most significant bit. 4) As to bit stream, I think std::bitset or std::vector<bool> will do it :-) \$\endgroup\$ Commented Feb 1, 2016 at 3:29
  • \$\begingroup\$ Ah, sorry about that. Yeah, I forgot about constexpr. Good point. Glad it helped at least a little! \$\endgroup\$ Commented Feb 1, 2016 at 3:43

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.