Bitwise Shift Clarification

Assume I have the variable `x` initialized to `425`. In binary, that is `110101001`.

Bitshifting it to the right by 2 as follows: `int a = x >> 2;`, the answer is: `106`. In binary that is `1101010`. This makes sense as the two right-most bits are dropped and two zero's are added to the left side.

Bitshifting it to the left by 2 as follows: `int a = x << 2;`, the answer is: `1700`. In binary this is `11010100100`. I don't understand how this works. Why are the two left most bits preserved? How can I drop them?

Thank you,

-
what type has x? – neagoegab Nov 11 '11 at 0:37
is x a signed integer ? – Steven smethurst Nov 11 '11 at 0:40

3 Answers

This is because `int` is probably 32-bits on your system. (Assuming x is type `int`.)

So your `425`, is actually:

``````0000 0000 0000 0000 0000 0001 1010 1001
``````

When left-shifted by 2, you get:

``````0000 0000 0000 0000 0000 0110 1010 0100
``````

Nothing gets shifted off until you go all the way past 32. (Strictly speaking, overflow of signed-integer is undefined behavior in C/C++.)

To drop the bits that are shifted off, you need to bitwise AND against a mask that's the original length of your number:

``````int a = (425 << 2) & 0x1ff;  //  0x1ff is for 9 bits as the original length of the number.
``````
-

First off, don't shift signed integers. The bitwise operations are only universally unambiguous for unsigned integral types.

Second, why shift if you can use `* 4` and `/ 4`?

Third, you only drop bits on the left when you exceed the size of the type. If you want to "truncate on the left" mathematically, perform a modulo operation:

``````(x * 4) % 256
``````

The bitwise equivalent is AND with a bit pattern: `(x << 2) & 0xFF`

(That is, the fundamental unsigned integral types in C are always implicitly "modulo 2n", where n is the number of bits of the type.)

-
The reason I want to do that is say I have this char array: `00000001101010010100000000100000`, I want to separate the first 6 bits, and then the rest divide them in fives. – darksky Nov 11 '11 at 0:59
@Nayefc: I see. Well, shift and AND until you have everything. – Kerrek SB Nov 11 '11 at 1:00
The bitwise operations are unambiguous for positive integers. But other than that, I agree. – Oliver Charlesworth Nov 11 '11 at 1:15
@OliCharlesworth: What about left-shifting a positive integer? Suddenly you're in the realm of how signedness is implemented... – Kerrek SB Nov 11 '11 at 1:16
@Kerrek: Clearly, if you're going to start shifting bits out of range, then yes, it's undefined. If you're not going to do that, its behaviour is perfectly intuitive, and therefore unambiguous (IMHO). It's certainly no less ambiguous than the equivalent multiplication (which would cause overflow). – Oliver Charlesworth Nov 11 '11 at 1:25

Why would you expect them to be dropped? Your int (probably) consumes 4 bytes. You're shifting them into a space that it rightfully occupies.

The entire 4-byte space in memory is embraced during evaluation. You'd need to shift entirely out of that space in memory to "drop" them.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}