lshift & rshift

[iesvs]

Hello guys,
every time a rode a doc or a book about the language C I saw that
operators << and >> exist. But each time they said that << translate
the digit to the left (and >> ...) but no one said if a << 1 mean
every time a * 2, because there is the problem with the way the
integer are stored. So I never use thoses operators because I fear
strange behaviour on different architecture. Can I use them and be
sure that a << 1 means a * 2 on every computer ? Is is in the ansi
standard of language C ?

 

[Richard Heathfield]

(e-mail address removed) said:

Hello guys,
every time a rode a doc or a book about the language C I saw that
operators << and >> exist. But each time they said that << translate
the digit

Each bit is moved one place to the left, the leftmost bit falls off the end
into the bit bucket (which should be emptied regularly), and the rightmost
bit is set to 0.

to the left (and >> ...)

Beware signed types when shifting. The danger is particularly - er -
dangerous when right-shifting negative numbers. What happens to the sign
bit? (Answer: it depends on the implementation.)

but no one said if a << 1 mean
every time a * 2,

Not every time, no. For example, consider a system where CHAR_BIT is 8.

unsigned char ch = 1;

ch <<= 1; /* ch is now 2 */
ch <<= 1; /* ch is now 4 */
ch <<= 1; /* ch is now 8 */
ch <<= 1; /* ch is now 16 */
ch <<= 1; /* ch is now 32 */
ch <<= 1; /* ch is now 64 */
ch <<= 1; /* ch is now 128 */
ch <<= 1; /* ch is now 0, even though 2 * 128 is 256. */

because there is the problem with the way the
integer are stored. So I never use thoses operators because I fear
strange behaviour on different architecture. Can I use them and be
sure that a << 1 means a * 2 on every computer ?

If you stick to unsigned types, and don't push any 1-bits off the end, yes.
But why bother? Why not just multiply by 2, if that's what you want to do?

Is is in the ansi standard of language C ?

Yes, but - like I said - you do need to be careful.

 

[Philip Potter]

Hello guys,
every time a rode a doc or a book about the language C I saw that
operators << and >> exist. But each time they said that << translate
the digit to the left (and >> ...) but no one said if a << 1 mean
every time a * 2, because there is the problem with the way the
integer are stored. So I never use thoses operators because I fear
strange behaviour on different architecture. Can I use them and be
sure that a << 1 means a * 2 on every computer ? Is is in the ansi
standard of language C ?

One of the problems with using the bit-shift operators to do arithmetic is you
no longer say what you mean. If you want to multiply something by 2, say so.

Another problem is that bit-shifting is not entirely defined for signed types.
This is partly because a bit-shift could move a value bit into a sign bit, or
vice versa, and partly because C allows different representations of signed
integers (2's complement, 1's complement, or sign-magnitude).

In the bad old days, some people used to use bit-shifts to perform simple
multiplications because it would run quicker. These days, compilers can spot for
themselves when this sort of trick is possible and will do so.

For arithmetic, use arithmetic operators. Save bit-shifting for when you need
bit-shifting semantics - for example, simulating a shift register.

 

[iesvs]

In the bad old days, some people used to use bit-shifts to perform simple

multiplications because it would run quicker. These days, compilers can spot for
themselves when this sort of trick is possible and will do so.

For arithmetic, use arithmetic operators. Save bit-shifting for when you need
bit-shifting semantics - for example, simulating a shift register.

So if I want to multiply an int by two I have to use a * 2 (or a + a),
but not << ? To be sure it works on every architecture (currently I
ignore the problem of the size of an int).

 

[Mark Bluemel]

So if I want to multiply an int by two I have to use a * 2 <snip>?

Why would you want to do it any other way?

 

[iesvs]

Why would you want to do it any other way?

If << is faster, it would be great. I love to have fast software, I'm
not rich and don't buy expensive computer.

 

[Ian Collins]

If << is faster, it would be great. I love to have fast software, I'm
not rich and don't buy expensive computer.

What did your profiler tell you?

 

[karthikbalaguru]

If << is faster, it would be great. I love to have fast software, I'm
not rich and don't buy expensive computer.

Did you try to view the assembly of a * 2 or the assembly of a + a .
I think,a*2 and a+a must internally be doing shifting using the shift
operators if shift operators are very fast.
Am i right ?

If thatz wrong then, How do you think, a*2 or a+a will be internally ?

Karthik Balaguru

 

[Mark Bluemel]

If << is faster, it would be great. I love to have fast software, I'm
not rich and don't buy expensive computer.

As others have already pointed out, the compiler will be more than
capable of applying this sort of optimisation if it is appropriate. In
general you should write clear, correct, expressive code and let the
compiler deal with optimisation. Any decent compiler is likely to do a
better job of optimising this sort of thing than you could.

If you have performance issues, you are generally better off looking for
better algorithms than fiddling with this sort of trivia.

If you have to get down to tuning at the code, rather than algorithm,
level then you need to profile your code as Ian has suggested. Only by
measuring will you find the bottlenecks.

 

[iesvs]

Did you try to view the assembly of a * 2 or the assembly of a + a .

I think,a*2 and a+a must internally be doing shifting using the shift
operators if shift operators are very fast.
Am i right ?

No you're wrong. A saw that it change a * 2 by a + a. (in reality I
was looking at a * 7) and I saw something like that :
b = a + a
c = b + b
c + b + a
So after I try a * 2 and get
a + a
But it didn't use lshift.

 

[iesvs]

What did your profiler tell you?

What is a profiler ?

 

[Ian Collins]

What is a profiler ?

A very useful tool that's included in any self respecting tool set.

http://en.wikipedia.org/wiki/Performance_analysis

 

[iesvs]

A very useful tool that's included in any self respecting tool set.

http://en.wikipedia.org/wiki/Performance_analysis

I never use these kind of stuffs.

 

[Ian Collins]

I never use these kind of stuffs.

Then you shouldn't be fiddling with micro-optimisations.

 

[pete]

(e-mail address removed) said:


Each bit is moved one place to the left,
the leftmost bit falls off the end
into the bit bucket (which should be emptied regularly),
and the rightmost bit is set to 0.


Beware signed types when shifting. The danger is particularly - er -
dangerous when right-shifting negative numbers.
What happens to the sign bit?
(Answer: it depends on the implementation.)


Not every time, no.
For example, consider a system where CHAR_BIT is 8.

unsigned char ch = 1;

ch <<= 1; /* ch is now 2 */
ch <<= 1; /* ch is now 4 */
ch <<= 1; /* ch is now 8 */
ch <<= 1; /* ch is now 16 */
ch <<= 1; /* ch is now 32 */
ch <<= 1; /* ch is now 64 */
ch <<= 1; /* ch is now 128 */
ch <<= 1; /* ch is now 0, even though 2 * 128 is 256. */

That example doesn't show a difference
between shifting and a doubling.

The result of each shift
is the same as what you would get from multiplication.

CHAR_BIT is 8

unsigned char ch = 1;

ch *= 2; /* ch is now 2 */
ch *= 2; /* ch is now 4 */
ch *= 2; /* ch is now 8 */
ch *= 2; /* ch is now 16 */
ch *= 2; /* ch is now 32 */
ch *= 2; /* ch is now 64 */
ch *= 2; /* ch is now 128 */
ch *= 2; /* ch is now 0, even though 2 * 128 is 256. */

 

[iesvs]

Then you shouldn't be fiddling with micro-optimisations.

What ? I used to profile with my hands (like I debug with my hands).
And when a micro operation is used many times it becomes a macro
optimisations. Yeah generally I don't care about a * 2 or a + a. But
sometimes I need to use that 1000..... times so I need to know which
is fastest.

 

[Mark Bluemel]

What ? I used to profile with my hands (like I debug with my hands).
And when a micro operation is used many times it becomes a macro
optimisations. Yeah generally I don't care about a * 2 or a + a. But
sometimes I need to use that 1000..... times so I need to know which
is fastest.

Which is where a profiler comes in...

 

[Ian Collins]

What ? I used to profile with my hands (like I debug with my hands).
And when a micro operation is used many times it becomes a macro
optimisations. Yeah generally I don't care about a * 2 or a + a. But
sometimes I need to use that 1000..... times so I need to know which
is fastest.

That's what a profiler is there to help you do. It may also tell you
that there is a bigger bottleneck elsewhere.

 

[iesvs]

Which is where a profiler comes in...

No. I know when I programm if * 2 will be used 10 times or 10000....
I know from the beginning where are the important and no important
part. I don't need a software to say me these kind of things, moreover
there are more dumbs than me (a computer beat myself, ha ha ha).

 

[Richard Bos]

So if I want to multiply an int by two I have to use a * 2 (or a + a),
but not << ?

No, if you want to multiply an int by two you use a*2. a+a is, like
a<<1, a micro-optimisation which in these days of good optimisers is
more likely to do harm than good. Make your code readable, and save the
tricks for when you have already proved you need them, not for when you
only think so.

To be sure it works on every architecture

To be sure, it does not. It may work on every architecture you know, but
that doesn't necessarily mean much if you've mainly worked with desktop
computers.

Shifting an unsigned integer always works, as long as your shift factor
is not negative or larger than the first operand's size.
Shifting a signed integer right works, but if it's negative, the result
is implementation-defined (i.e., it's not allowed to crash, but the
Standard doesn't demand any specific numeric result, it only requires
that the result _is_ a number and not a bus error; there are two
reasonable results, and I would expect to get either of these, but the
Standard doesn't even require this.) If the integer is positive, the
result is what you would expect.
Shifting a signed integer left only works if the expected result fits in
that integer type (in which case, it's required to be the actual
result). If the expected result would not fit, the result in this case
is undefined. This is worse than the previous case, because it means
that left-shifting a signed integer which is too large _can_ crash your
program.

Summary: only use bit-shifting if what you want to do _is_ bit-shifting,
and not if you want a "faster" multiplication or division, because that
may be counter-productive. Only use bit-shifting on signed integers if
you are sure of what you're doing. By preference, only use bit-shifting
on unsigned integers. It makes more sense for them, anyway.

Richard