20

For T so that std::is_integral<T>::value && std::is_unsigned<T>::value is true, does the C++ standard guarantee that :

std::numeric_limits<T>::max() == 2^(std::numeric_limits<T>::digits)-1

in the mathematical sense? I am looking for a proof of that based on quotes from the standard.

Mat
  • 202,337
  • 40
  • 393
  • 406
Vincent
  • 57,703
  • 61
  • 205
  • 388
  • [This answer](http://stackoverflow.com/questions/12125650/what-do-the-c-and-c-standards-say-about-bit-level-integer-representation-and-m) could be helpful. – davidhigh Jan 18 '16 at 16:03

2 Answers2

15

I believe that this is implied by [basic.fundamental]/4 (N3337):

Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number of bits in the value representation of that particular size of integer.

TartanLlama
  • 63,752
  • 13
  • 157
  • 193
  • It is indeed and follows directly from `MAX = -1 = 2^n - 1` modulo `2^n`. – Baum mit Augen Jan 18 '16 at 16:01
  • 1
    If MAX is less than 2^n-1, then the quoted section implies that MAX+1 is not zero and hence that MAX is not the maximum - which would be a contradiction. – Martin Bonner supports Monica Jan 18 '16 at 16:04
  • Strictly speaking "obeying the laws of arithmetic modulo `2^n`" describes arithmetic operators and equality relations for the type, not the set of values that can be taken. Mathematically, the values used in modular arithmetic are _congruence classes_ of integers, and can be implemented using any complete set of representative values in the classes. Although I know it doesn't (and prefers to invoke undefined behaviour), the standard _could have_ chosen to stipulate that `signed int` obey the laws of arithmetic modulo `2^n` as well (then only `<` etc would distinguish `int` from `unsigned`). – Marc van Leeuwen Jan 19 '16 at 10:48
15

C++ specifies the ranges of the integral types by reference to the C standard. The C standard says:

For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2N − 1, so that objects of that type shall be capable of representing values from 0 to 2N − 1 using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.

Moreover, C++ requires:

Unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer.

Putting all this together, we find that an unsigned integral type has n value bits, represents the values in the range [0, 2n) and obeys the laws of arithmetic modulo 2n.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • So why are they saying "value bits in the object representation" one time, and "bits in the value representation" the other time? – Marc van Leeuwen Jan 18 '16 at 17:45
  • @MarcvanLeeuwen: The two language standards have developed slightly different styles of phrasing what is essentially the same idea. The first quote is from C11, the second from the C++ WD. – Kerrek SB Jan 18 '16 at 18:01