Left-shift bit operation for multiplying int-variable: Limited Range for multiplying. Arithmetic pattern after exceeding?

Question

My actual concern is about this:

The left-shift bit operation is used to multiply values of integer variables quickly. But an integer variable has a defined range of available integers it can store, which is obviously very logical due to the place in bytes which is reserved for it.

Depending on 16-bit or 32-bit system, it preserves either 2 or 4 bytes, which range the available integers from

-32,768 to 32,767 [for signed int] (2 bytes), or 0 to 65,535 [for unsigned int] (2 bytes) on 16-bit

OR

-2,147,483,648 to 2,147,483,647 [for signed int] (4 bytes), or 0 to 4,294,967,295 [for unsigned int] (4 bytes) on 32-bit

My thought is, it should´t be able to multiply the values over the exact half of the maximum integer of the according range.

But what happens then to the values if you proceed the bitwise operation after the value has reached the integer value of the half of the max int value?

Is there an arithmetic pattern which will be applied to it?

---

One example (in case of 32-bit system):

unsigned int redfox_1 = 2147483647;
unsigned int redfox_2;
redfox_2 = redfox_1 << 1;

/* Which value has redfox_2 now? */

redfox_2 = redfox_1 << 2;

/* Which value has redfox_2 now? */

redfox_2 = redfox_1 << 3;

/* Which value has redfox_2 now? */


/* And so on and on */
/* Is there a arithmetic pattern what will be applied to the value of redfox_2 now?  */

the value stored inside redfox_2 shouldn´t be able to go over 2.147.483.647 because its datatype is unsigned int, which can handle only integers up to 4,294,967,295.

What will happen now with the value of redfox_2?

And Is there a arithmetic pattern in what will happen to the value of redfox_2?

Hope you can understand what i mean.

Thank you very much for any answers.

Answer 1

If you really want to see the pattern, then just write a program that prints it:

#include <iostream>
#include <ios>
#include <bitset>

int main()
{
    unsigned int redfox = 2147483647;
    std::bitset<32> b;

    for (int i = 0; i < 32; ++i)
    {
        redfox = redfox << 1;
        b = redfox;
        std::cout << std::dec << redfox << ", " << std::hex << redfox << ", " << b << std::endl;
    }
}

This produces:

4294967294, fffffffe, 11111111111111111111111111111110
4294967292, fffffffc, 11111111111111111111111111111100
4294967288, fffffff8, 11111111111111111111111111111000
4294967280, fffffff0, 11111111111111111111111111110000
4294967264, ffffffe0, 11111111111111111111111111100000
4294967232, ffffffc0, 11111111111111111111111111000000
4294967168, ffffff80, 11111111111111111111111110000000
4294967040, ffffff00, 11111111111111111111111100000000
4294966784, fffffe00, 11111111111111111111111000000000
4294966272, fffffc00, 11111111111111111111110000000000
4294965248, fffff800, 11111111111111111111100000000000
4294963200, fffff000, 11111111111111111111000000000000
4294959104, ffffe000, 11111111111111111110000000000000
4294950912, ffffc000, 11111111111111111100000000000000
4294934528, ffff8000, 11111111111111111000000000000000
4294901760, ffff0000, 11111111111111110000000000000000
4294836224, fffe0000, 11111111111111100000000000000000
4294705152, fffc0000, 11111111111111000000000000000000
4294443008, fff80000, 11111111111110000000000000000000
4293918720, fff00000, 11111111111100000000000000000000
4292870144, ffe00000, 11111111111000000000000000000000
4290772992, ffc00000, 11111111110000000000000000000000
4286578688, ff800000, 11111111100000000000000000000000
4278190080, ff000000, 11111111000000000000000000000000
4261412864, fe000000, 11111110000000000000000000000000
4227858432, fc000000, 11111100000000000000000000000000
4160749568, f8000000, 11111000000000000000000000000000
4026531840, f0000000, 11110000000000000000000000000000
3758096384, e0000000, 11100000000000000000000000000000
3221225472, c0000000, 11000000000000000000000000000000
2147483648, 80000000, 10000000000000000000000000000000
         0,        0, 00000000000000000000000000000000

Answer 2

Per the C 2018 standard, 6.5.7 4:

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

So, for unsigned integer types, the bits are merely shifted left, and vacated bit positions are filled with zeroes. For signed integer types, the consequences of overflow are not defined by the C standard.

Many C implementations will, in signed shifts, slavishly shift the bits, including shifting value bits into the sign bit, resulting in various positive or negative values that a naïve programmer might not expect. However, since the behavior is not defined by the C standard, a C implementation could also:

• Clamp the result at INT_MAX or INT_MIN (for int, or the corresponding maxima for the particular type).
• Shift the value bits without affecting the sign bit.
• Generate a trap.
• Transform the program, when the undefined shift is recognized during compilation and optimization, in arbitrary ways, such as removing the entire code path that performs the shift.