How does the bit layout of the floats give me certain values after bit shifting?

user_15676895 0
Viewed 139

Out of curiosity and wanting to learn more about floating point, I ran the following C code:

#include <stdio.h>

int main() {
  float a = 1.0 + ((float) (1 << 22));
  float b = 1.0 + ((float) (1 << 23));
  float c = 1.0 + ((float) (1 << 24));

  printf("a = %.6f\n", a);
  printf("b = %.6f\n", b);
  printf("c = %.6f", c);
}

The results were:

a = 4194305.000000
b = 8388609.000000
c = 16777216.000000

I'm confused on why I got these results. Can anyone explain why the bit layout of a, b, and c causes each value to be what it is? I'm new to bit shifting and floats and a clear explanation would be greatly appreciated. Thank you.

bit bit-shift floating-point c
2 Answers
(1 << 22)

is an integer value equal to

2^22 = 4194304

then you convert it to float by doing (float) (1 << 22) which gives you the same value

4194304.0

and then you add 1.0 to get the result 4194305.0

The same applies to the other cases.

So this is not about "layout of floats" - it's rather about layout of integers and conversion from integer to float.

However, the last case where you use 1 << 24 is a bit interesting (and relates to float format).

(1 << 24) is 16777216

and can be converted to the same float value, i.e.

16777216.0

But when you do

1.0 + 16777216.0

you still get

16777216.0

The reason is the limited precision of floats (i.e. not all numbers can be presented in the float format). The value 16777217.0 can't be presented in the float format so adding 1.0 to 16777216.0 still gives you 16777216.0

BTW: There are several rounding modes (see e.g. https://en.wikipedia.org/wiki/Floating-point_arithmetic#Rounding_modes) so when an exact result can't be presented in the float format, you need to know your systems rounding mode to figure out which value will be used instead of the exact result.

user_43864270

I'm going to expand on 4386427's answer and get into the weeds a bit about why 16777216.0 + 1 == 16777216.0 (this is partly for my own benefit - each time I explain it I understand it a little more deeply myself).

First, a fundamental truth - you cannot squeeze an infinite number of real values into a finite number of bits. Binary floating point formats can only store approximations of all but a tiny number of real values; the only values that can be represented exactly are sums of powers of 2 that don't exceed the precision of the type (more on that below).

A floating point value x is represented by the model

x = s * be * Σ(k=1,p) (fk * b-k)

where

  • s is the sign (+/- 1)
  • b is the base (2 for binary floating point, 10 for decimal floating point, etc.)
  • p is the precision (number of base-b digits in the significand),
  • e is an exponent value
  • fk is the k'th digit in the significand

As an example, let's look at how we'd represent the value 3.14159 in binary floating point. Binary means our base b is 2, so our significand can only contain the digits 0 or 1. So instead of expressing 3.14159 as a sum of powers of 10 (3 * 100 + 1 * 10-1 + 4 * 10-2 + ...), we need to express it as a sum of powers of 2.

We can start by repeatedly dividing by 2 until we get a value less than 1; dividing by 2 twice (i.e., dividing by 4) gives us 0.7853975 (we'll multiply those 2s back in later). Now we need to express that as a binary fraction.

1 * 2-1 is 0.12, or 0.5 decimal. 1 * 2-1 + 1 * 2-2 is 0.112, or 0.75 decimal. So, we keep adding bits as long as they sum up to a value less than or equal to 0.7853975. A half hour later with an Excel spreadsheet, I get

0.11001001000011111100111110000000110111000011001112

So to express 3.14159 in our binary floating point model, we can write

1 * 22 * (1 * 2-1 + 1 * 2-2 + 0 * 2-3 + 0 * 2-4 + 1 * 2-5 + ... )

which is more compactly represented as

1 * 22 * 0.11001001000011111100111110000000110111000011001112

Remember we divided the significand by 4 earlier, so we multiply it back with the 22. However, before we go any further, we're going to normalize that fraction such that the digit to the left of the radix point is non-zero; we can do that by multiplying by 2 (giving us a significand of 1.570795):

1 * 21 * 1.1001001000011111100111110000000110111000011001112

So, that's how we represent 3.14159 in our binary floating point model - how do we actually store it?

Floating point formats vary (most systems use IEEE-754, but there are some that don't), but they all pretty much do the same thing - they reserve one bit for the sign, some number of bits for the exponent, and some number of bits for the significand. The IEEE-754 single-precision (float) format looks like this:

 3 32222222 2221111111111
 1 09876543 21098765432109876543210
+-+--------+-----------------------+
| |        |                       |
+-+--------+-----------------------+
 ^ ^        ^
 | |        |
 | |        +----------------------- significand
 | +-------------------------------- exponent
 +---------------------------------- sign bit

1 bit is reserved for the sign (0 for positive, 1 for negative), 8 bits are reserved for the exponent, and 23 bits are reserved for the significand. The leading digit before the radix point in the significand isn't explicitly stored - it's assumed to be 1 for normalized values and 0 for subnormal/non-normal values (which we won't get into here).

We don't reserve a second sign bit for exponents - rather, we offset the exponent value. For an 8-bit exponent, 000000002 represents -127 (reserved by IEEE-754 for either zero or denormal values), 0111111112 represents 0, 100000002 represents 1, and 111111112 represents 128 (reserved for +/- infinity or NaN).

So we would encode our value as

+-+--------+-----------------------+
|0|10000000|10010010000111111001111|  assumes leading 1 before radix point
+-+--------+-----------------------+

Now, here's where we hit our precision problem - a 32-bit float can only store the first 23 bits of the significand after the radix point, meaning we can only store the fraction 1.100100100001111110011112. Unfortunately, it took us 50 bits to represent our binary fraction completely; we've lost half of the precision required. As a result, we're not storing 3.14159, we are storing 3.14158987998962.

But here's another issue - let's add 1 to that significand:

+-+--------+-----------------------+
|0|10000000|10010010000111111010000|
+-+--------+-----------------------+

That is the next higher value we can represent in this format. This adds up to 3.14159011840820, meaning we cannot store any values between those two. Now, the difference here is small - on the order of one 10-6. But, as the magnitude of the values increases (by increasing the exponent), that gap gets larger. Instead of multiplying our original fraction by 21, let's multiply it by 223 (8388608):

+-+--------+-----------------------+
|0|10010110|10010010000111111001111|
+-+--------+-----------------------+

That gives us a value of 13176783.0. Again, we add 1 to the significand:

+-+--------+-----------------------+
|0|10010110|10010010000111111010000|
+-+--------+-----------------------+

which gives us 13176784.0. As you can see, the gap between representable values has gone from being one in a million to, well, 1. Once the exponent gets larger than the number of bits in the significand, then you start getting gaps larger than 1.

And this, ultimately, is why adding 1.0 to 16777216.000000 didn't change the value - you cannot represent 16777217.0 in a 32-bit float1. The next representable value is 16777218.0. When the exponent is 24, the gap between values is 2. When it's 25, the gap is 4, and that gap size keeps doubling as the exponent increases.

Unless you have a good reason not to, it's advised to use double instead of float. Being a wider type, it can represent a wider range of values with greater precision than float. If you had used double instead of float in your program it would have behaved as expected.

But just like with float, double can only represent an infinitesimally small number of real values exactly and will have gaps between representable values. Since floating point values are approximations, arithmetic with floating point values is only approximate, and errors will accumulate.

  1. Well, that and the fact that to add floating point values you have to bring their exponents into agreement, and by shifting 1.0 23 digits to the left, you basically wind up with zero.
user_1345540
Related