6

I am writing an integer-like class that represents a value that lies somewhere in a range. For instance, the value of bounded::integer<0, 10> is somewhere in the range [0, 10]. For this class, I have defined radix to be 2.

What should the value of digits be for bounded::integer<-100, 5>?

What about bounded::integer<16, 19>?

0

2 Answers 2

6

After reading the standard a bit more and thinking about this, I believe I have the best answer, but I am not certain.

First, the definition of digits, taken from the latest C++14 draft standard, N3797, § 18.3.2.4:

static constexpr int digits;

8 Number of radix digits that can be represented without change.

9 For integer types, the number of non-sign bits in the representation.

10 For floating point types, the number of radix digits in the mantissa

The case of bounded::integer<-100, 5> is the same as for bounded::integer<0, 5>, which would give a value of 2.

For the case of bounded::integer<16, 19>, digits should be defined as 0. Such a class cannot even represent a 1-bit number (since 0 and 1 aren't in the range), and according to 18.3.2.7.1:

All members shall be provided for all specializations. However, many values are only required to be meaningful under certain conditions (for example, epsilon() is only meaningful if is_integer is false). Any value that is not "meaningful" shall be set to 0 or false.

I believe that any integer-like class which does not have 0 as a possible value cannot meaningfully compute digits and digits10.

Another possible answer is to use an information theoretic definition of digits. However, this is not consistent with the values for the built-in integers. The description explicitly leaves out sign bits, but those would still be considered a single bit of information, so I feel that rules out this interpretation. It seems that this exclusion of the sign bit also means that I have to take the smaller in magnitude of the negative end and the positive end of the range for the first number, which is why I believe that the first question is equivalent to bounded::integer<0, 5>. This is because you are only guaranteed 2 bits can be stored without loss of data. You can potentially store up to 6 bits as long as your number is negative, but in general, you only get 2.

bounded::integer<16, 19> is much trickier, but I believe the interpretation of "not meaningful" makes more sense than shifting the value over and giving the same answer as if it were bounded::integer<0, 3>, which would be 2.

I believe this interpretation follows from the standard, is consistent with other integer types, and is the least likely to confuse the users of such a class.

To answer the question of the use cases of digits, a commenter mentioned radix sort. A base-2 radix sort might expect to use the value in digits to sort a number. This would be fine if you set digits to 0, as that indicates an error condition for attempting to use such a radix sort, but can we do better while still being in line with built-in types?

For unsigned integers, radix sort that depends on the value of digits works just fine. uint8_t has digits == 8. However, for signed integers, this wouldn't work: std::numeric_limits<int8_t>::digits == 7. You would also need to sort on that sign bit, but digits doesn't give you enough information to do so.

2
  • "The second number, ranged_integer<16, 19> is much trickier," The question I'd ask is what is digits used for? For example, you could use it in a radix sort. I'd expect that digits provides all necessary information; yet it doesn't for your ranged_integers. I cannot store a 3-digit number in ranged_integer<16,19> and a radix-sort on the first 3 digits would yield wrong results.
    – dyp
    Oct 26, 2013 at 16:59
  • @DyP I was referring to the order in the question. I will edit my answer to make that more clear, so you don't have to jump back and forth. Answering your radix-sort example will take a little more space than I think I have in a comment, so I will edit that response in, too. Oct 26, 2013 at 19:28
0

You are over-thinking it. There are two simple options for digits specializations for your own ranged_integer

  • log2(Last-First) when you are representing the range [First, Last).
  • the value of N * numeric_limits<U>::digits which corresponds to the smallest underlying storage std::array<U, N> in which you can store your range.

Note that your class ranged_integer can internally do a transformation to map a range of e.g. [-100, 5] onto [0, 105] so that you don't have to worry about sign-bits etc.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.