CODEWITHSUNDEEP
cbinarybit-manipulation
mma
mma

Reputation: 119

Modulo Behavior in C Left Shift Operation

The ISO C99 Standard for bitwise shift operators says the following in regard to left shift:

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 non-negative value, and E1×2E2 is representable in the result type, then that is the resulting value; otherwise, the behaviour is undefined.

I don't understand what is meant when it says "reduced modulo one more than the maximum value representable in the result type" in the context of shifting bits.

Upvotes: 2

Views: 814

Answers (3)

Andy
Andy

Reputation: 349

A nice way to think about this is by looking at binary representation of what is going on.

When is states that the value of the result is E1×2E2, reduced modulo one more than the maximum value representable in the result type. You can think of it like the following

Let us use an unsigned char which is an 8-bit type and has a maximum value 255

unsigned char ch = UCHAR_MAX
// ch : 255 : 1111 1111

Now let us left shift the value by one and also allow ourselves the ability to go beyond 8-bits (let us add another 4-bits)

ch = ch << 1;
// ch : 510 : 0001 1111 1110

We cannot store our 12-bit sudo number inside an unsigned char, so we need to keep the information that still fits and a way to do this is to modulo reduce by UCHAR_MAX + 1. Why UCHAR_MAX + 1 you may ask, well UCHAR_MAX + 1 looks like the following

UCHAR_MAX 
// 255 : 1111 1111

UCHAR_MAX + 1 
// 256 : 0001 0000 0000

So when we take our value that has exceeded its limits and modulo it by UCHAR_MAX + 1 we end up stripping all binary digits above our allowed 8-bit value.

ch % (UCHAR_MAX + 1)
// 510 % 256 = 254
// 0001 1111 1110 % 0001 0000 0000 = 1111 1110

Providing the expected result of shifting ch << 1 which is what C will output.

At a computational level, this is not going to happen as we cannot arbitrarily just exceed are allowed size, so left shifting 1 beyond the maximum value causes a wrap-around which changes the least significant bit to 0.

I hope this helps along with the other answers that have already been provided for this question!

Upvotes: 0

Codor
Codor

Reputation: 17605

The maximum value representable in the result type will have all of its bits set, which not a single power of two. However, the number against which the modulo operation is done (when the value starts to wrap) is a power of two, namely the next one, which can be obtained by adding one to the largest representable value.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272497

It's basically talking about integer wrapping. If the mathematical value is bigger than the max representable value of the type, then it wraps, i.e. modulo arithmetic.

Upvotes: 1

Related Questions