CODEWITHSUNDEEP
cbit-manipulationbitwise-operatorsisobit-shift
Vivek Maran
Vivek Maran

Reputation: 2753

Bitwise shift operators on signed types

I am trying to understand the behavior of bitwise operators on signed and unsigned types. As per the ISO/IEC document, following are my understandings.

Left shift Operator

Right Shift Operator

Upvotes: 7

Views: 5917

Answers (4)

Jagdeep Sidhu
Jagdeep Sidhu

Reputation: 361

If you really want to understand the bitwise shift operators. Look at these simple rules:

1) In left shift, E1 << E2, all the vacant bits on right side will be filled by zeroes, does not matter if the number is signed or unsigned, always zeroes will be shifted in.

2) In left shift, E1 >> E2, all the vacant bits on left side, will be 0 if number is positive, and will be 1 if number is negative.Keep in mind that an unsigned number is never negative. Also some implementations might also fill them with 0 on some machines even if number is negative, so never rely on this.

All other scenarios could be explained by these two simple rules. Now if you want to know the value of result after shifting , just write the bit representation of number and shift manually on paper and enter bits at vacant spaces using these two rules. Then you would be able to understand better how bit shifting works.

For example lets take int i = 7;
i<<2
now i = 0000 0000 0000 0000 0000 0000 0000 0111
perform two left shits according to rule 1 would be:

0000 0000 0000 0000 0000 0000 0001 1100

which will give it value of 28 ( E1 * 2E2 = 7 *2*2 = 28), which is same as representated by bit pattern.

Now let me explain the "reduced modulo" thing, well if you are shifting a big number, than the bits on left hand side will be lost, "reduced modulo" compensates for it, So if your resultant value if greater than the maximum value that the data type could hold, the bits on left will be lost , and then: result = (E1*2*E2) % ( maximumValue + 1).

For various other cases, just keep the above rules in mind , and you are good :)

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183888

Q1: The behaviour of the left shift operator on negative values of signed integer types is undefined, as is the behaviour for positive values of signed integer types when the result E1 * 2^E2 is not representable in the type.

That is explicitly mentioned in section 6.5.7, paragraph 4 and 5 of the standard (n1570 draft):

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 × 2^E2 , reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Q2: The reduction modulo one more than the maximum value representable in the unsigned integer type means that the bits that are shifted out on the left are simply discarded.

Mathematically, if the maximal value of the unsigned type is 2^n - 1 (and it is always of that form), the result of shifting E1 left by E2 bits is the value V in the range from 0 to 2^n - 1 such that the difference

(E1 * 2^E2 - V)

is divisible by 2^n, that is, it's the remainder you get when dividing E1 * 2^E2 by 2^n.

Q3: The behaviour upon shifting right negative values of signed integer types is implementation-defined. The most common behaviour (at least on two's complement machines) is an arithmetic shift, that is, the result is the quotient rounded down (towards negative infinity).

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2 . If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Upvotes: 8

David Grayson
David Grayson

Reputation: 87416

Q2: "value reduced modulo X" means "value mod X" in math and can be written as "value % X" in C. That part just explains how integer overflows work.

Upvotes: 1

melpomene
melpomene

Reputation: 85767

  • Re: Q1
    If E1 is negative, the behavior is undefined.

  • Re: Q2
    Unsigned arithmetic is "cyclic", that is, it wraps around so UINT_MAX + 1 is 0 again. It's as if every calculation was done modulo UINT_MAX+1. Another way to think about it is that excess bits that don't fit in on the left are simply dropped.

  • Re: Q3
    If E1 is negative, the result is implementation-defined. That is, it depends on your machine/compiler/options, but the behavior has to be documented ("defined") somewhere, ususally the compiler manual. Two popular choices are to fill the incoming bits on the left with 1 (arithmetic shift) or with 0 (logical shift).

Upvotes: 5

Related Questions