lshift & rshift

[Mark Bluemel]

I also try a << 1
and it converted it into a + a

Which presumably means that the designer of the compiler knew that it
was cheaper (fewer cycles) on the specific target architecture to add
"a" to itself than to use some other mechanism to achieve a 1-place left
shift.

If you don't want to trust the compiler writers to do a decent job of
optimisation, I suggest you move to writing assembler...

 

[iesvs]

If you don't want to trust the compiler writers to do a decent job of

optimisation, I suggest you move to writing assembler...

No, no, I trust them. It's their work, not mine.
In beginning my question was theoretical.
The real meaning was, is << a left shift or something who shift the
numbers from the less important bit to the most important.
And people said it's the second, not the first.

 

[karthikbalaguru]

No, no, I trust them. It's their work, not mine.
In beginning my question was theoretical.
The real meaning was, is << a left shift or something who shift the
numbers from the less important bit to the most important.
And people said it's the second, not the first.

Onceagain,
You have not replied to the below questions -
1) What is the optimisation level you have ?
2) Does it treat a<<1 and a*2 as a+a for all the optimisation
levels ?
3) What is the architecture you use ?

Karthik Balaguru

 

[iesvs]

I just need a precision about an operator. I saw many code with the
operator << and didn't know if it was portable.

Today I don't care if "<< 1" is faster than "* 2" or "+".

 

[karthikbalaguru]

I just need a precision about an operator. I saw many code with the
operator << and didn't know if it was portable.

Today I don't care if "<< 1" is faster than "* 2" or "+".

You have not yest answered these questions which will clarify your
doubts .

1) What is the optimisation level you have ?
2) Does it treat a<<1 and a*2 as a+a for all the optimisation
levels ?
3) What is the architecture you use ?
4) Also tell about the compiler and programming language you use ?

Karthik Balaguru

 

[Joachim Schmitz]

You have not yest answered these questions which will clarify your
doubts .

1) What is the optimisation level you have ?

As he said earlier (implicitly): no optimization

2) Does it treat a<<1 and a*2 as a+a for all the optimisation
levels ?

Yes (I've checked)

3) What is the architecture you use ?

From the assembly he posted: Intel ix86

4) Also tell about the compiler and programming language you use ?

gcc and C

Bye, Jojo

 

[iesvs]

1) What is the optimisation level you have ?

As he said earlier (implicitly): no optimization

No, I used to use -O3, but when I post my example I used no
optimization.

Yes (I've checked)

Ha, interesting.

From the assembly he posted: Intel ix86

686 to be exact (P4 I think).

gcc and C

We're in a C forum.

 

[Charlie Gordon]

pete said:


I agree. It does, however, show that shifting doesn't always double the
number. The fact that doubling doesn't always double the number is another
issue.

Why unnecessarily confuse the OP ?
left shifting by one is the same as doubling if the value shifted had
unsigned type or signed with a non negative value.

If the type is unsigned, the result of x << 1 is always the same as x + x
and x * 2, even in case of 'overflow' because the standard mandates modular
arithmetics.

If the type is signed, left or right shifting a negative value is
unspecified. The behaviour is implementation defined.

If the value is positive, right shifting by one is the same as dividing by
2, left shifting by one is the same as doubling, and invokes undefined
behaviour in case of overflow, just like addition and multiplication.

 

[user923005]

I can't, it was in past. But I'm sure. I asked a friend, and he
explain me that on some architecture (like the HP adding machine)
there wasn't a multiplication in the CPU, so the multiplication was a
software and it was better to use + than *. And it was not a lshift, I
swear it.

80% of the cost of software is maintenance.

So write code that is as clear and expressive as possible.

Do not try to out-think your compiler. Chances are very good that it
is better at optimization than you are.

If you *measure* a performance problem, then run a profiler against
the code to find out *where* the slow bits are. Typically, there will
be a couple places that need help. The way to fix these problem spots
is NOT by micro-optimizations like exchanging shifts for multiplies by
powers of two but by improving the algorithm. If (and only if) you
have measured to find out what is slow and you are unable to find or
produce a better algorithm, then it makes sense to do little tweaky
micro-optimizations or inline assembly. If you code that way from
scratch, then you are writing unmaintainable gobbledygook that won't
be fast anyway and will eventually cause great problems.

The first rule of optimization is: "Don't do it."
The second rule of optimization (for experts only) is: "Don't do it
yet."

 

[iesvs]

80% of the cost of software is maintenance.

So write code that is as clear and expressive as possible.

I don't care. When I read my codes I understand them, even those I
wrote 10 years ago, I can't explain why but I never forget one of my
code, I know it's rare.

Read and modify others code is a concept which leads to bugs, you
can't say I'm wrong.
You want to change something. You clear his function and you rewrite
it, but you have to know what are is in and his out, so a great API
reference.

Forget the concept that others will read your code. If they do that
it's because your code is stinky, if it was good they don't need to
have a look. It's like try something and thinking since the beginning
that we are going to fail.

 

[CBFalconer]

You have not yest answered these questions which will clarify your
doubts .

1) What is the optimisation level you have ?
2) Does it treat a<<1 and a*2 as a+a for all the optimisation
levels ?
3) What is the architecture you use ?
4) Also tell about the compiler and programming language you use ?

For heavens sake, give it up. Such answers have nothing to do with
the question in the first place.

 

[robertwessel2]

In beginning my question was theoretical.
The real meaning was, is << a left shift or something who shift the
numbers from the less important bit to the most important.
And people said it's the second, not the first.

The C standard defines a<<b to be a shift operations, and further
defines that it will be equivalent to ((a*(2**b))mod Uxxx_MAX) for
unsigned a's and non-negative b's.

For signed first operands, if the first operand is non-negative, and
if the result of (a*(2**b)) is representable in the type, then that's
the result. Otherwise (in the case of overflow or negative first or
second operands) the result is undefined.

In both cases, shift counts larger than the first parameter's width in
bits also have undefined results.

 

[Tor Rustad]

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 ?

First, bitwise operators, are intended for bit level operations on
unsigned types. If a is negative, a << 1 is undefined behavior, i.e. not
portable at all.


There are some very confused C programmers, that beleave a << 1, somehow
is faster than a *= 2. Such micro-optimization has been *nonsense* for
quite some years, when considering an optimizing C compiler.


Modern optimizing C compilers these days, are so advanced, that even
expert asm programmers have hard times beating it, a C newbie have less
chance than a snowball in hell.


Elsethread, somebody said one could count cycles from asm listing and
just compare timings. This typically not true, instructions can be
executed out-of-band, there can be multiple pipelines operating in
parallel, there can be branch-prediction etc. etc.


Optimizing these days, is a cache game.

If optimizing, focus rather on good algorithms, and keep
locality/compactness of data. Leave the rest to the compiler.

 

[Barry Schwarz]

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

The shift operators work on the value of the integer, not on its
representation. It doesn't matter if the storage scheme is
big-endian, little-endian, or confused-endian. The result is the
same. 1<<n evaluates to the value 2 raised to the power n as long as
the value is in the range of int (the same as repeatedly multiplying
by 2). For a positive value n, n>>1 evaluates to half the value of n
(the same as integer division).

strange behaviour on different architecture. Can I use them and be

Have no fear. But do take boundary conditions into consideration.
Negative values can behave in an implementation defined manner which
need not be consistent across different systems.

sure that a << 1 means a * 2 on every computer ? Is is in the ansi
standard of language C ?

There are drafts of the standard readily available on the internet.
Google for n1124.


Remove del for email

 

[Stephen Sprunk]

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).

If you want correct results, yes. They don't necessarily mean the same
thing. In a case where that microoptimization is safe and correct, any
decent compiler will do it for you, so you're wasting your time.

As the saying goes, "It's easier to make correct code fast than it is to
make fast code correct." Worry about getting the right answer and writing
clean, easy-to-maintain code first. When you've accomplished that, if
there's still a performance problem the compiler can't solve for you, then
you let a profiler tell you what needs fixing.

S

 

[Stephen Sprunk]

What ? I used to profile with my hands (like I debug with my hands).

If you just want to _guess_ what's going on, you're never going to get good
results. There's a reason profilers exist -- computers are far, far better
at the task than humans are. Spend your time worrying about writing
_correct_ code and let your tools figure out how to make it fast.

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.

No, you _don't_ need to know which is faster. It makes no sense to spend
effort shaving 1% off a loop that runs a million times (microoptimization)
when you can replace it with a loop that runs only a thousand times
(macrooptimization). For example, a macrooptimization would be looking at a
bubble sort that's running too slowly and replacing it with a quick sort,
i.e. working on the algorithms, not the specific implementation. Compilers
can't do major macrooptimizations (yet), but at least a profiler can tell
you where you need to spend your effort -- and where you don't.

S

 

[Richard Heathfield]

(e-mail address removed) said:

I don't care. When I read my codes I understand them, even those I
wrote 10 years ago, I can't explain why but I never forget one of my
code, I know it's rare.

The reason is simple - you've never written anything complex.

Read and modify others code is a concept which leads to bugs, you
can't say I'm wrong.

From what I've seen of your code, I can see where you might get this idea.

You want to change something. You clear his function and you rewrite
it, but you have to know what are is in and his out, so a great API
reference.

There isn't always enough time for a complete rewrite.

Forget the concept that others will read your code. If they do that
it's because your code is stinky, if it was good they don't need to
have a look.

Or because the requirements have changed. Both kinds are common.

It's like try something and thinking since the beginning
that we are going to fail.

Thinking is not what will make you fail. In your case, your biggest
weaknesses seem to be your preconceptions and your self-image.

 

[Joachim Schmitz]

No, I used to use -O3, but when I post my example I used no
optimization.

OK, can't guess that from yout posts

Ha, interesting.

And I said so in this thread. Exactly identical assembly code for all 3
expressions as of -O1, only a very slight variation in a+a for -O0 resp. no
optimization.

686 to be exact (P4 I think).

That's what I used to verify. On a SuSE Linux 10

We're in a C forum.

Indeed, but some of your statements in this and other thtreads (sizeof(char)
!= 1) made it difficult to believe that you were talking about C...

Bye, Jojo

 

[Philip Potter]

I don't care. When I read my codes I understand them, even those I
wrote 10 years ago, I can't explain why but I never forget one of my
code, I know it's rare.

Read and modify others code is a concept which leads to bugs, you
can't say I'm wrong.
You want to change something. You clear his function and you rewrite
it, but you have to know what are is in and his out, so a great API
reference.

Welcome to the real world.

Forget the concept that others will read your code. If they do that
it's because your code is stinky, if it was good they don't need to
have a look. It's like try something and thinking since the beginning
that we are going to fail.

No.

I can only assume that you have taken part in even a medium-sized software
project, or a project with other people involved, or a long-term project.

In many situations software needs to be changed because of changing
requirements. That doesn't mean it was written wrongly the first time, it means
that when it was first written, you didn't know what you would need in 5 or 10
years time.

Look at Microsoft Windows. Windows 3.1 didn't provide any support for 3d
graphics cards, because they didn't exist yet. Windows Vista has features that
allow windows to fly all over the place, all made possible by 3d cards.

When I started using the internet, HTML 3.2 was the standard web language. Then
a new version, HTML 4.0, came out. Browsers had to be rewritten to use the new
language, or they would be able to browse the web. CSS was invented. Browsers
had to be rewritten to read stylesheets. The .png file format came out. Browsers
had to be rewritten to display them.

Do you really think Mozilla Firefox, or Microsoft Internet Explorer, could exist
if they had only one developer for their whole lifetime? If not, how could they
be written in such a way that noone ever has to read or modify someone else's
code? What if someone leaves the project?

(When I was 4 years old, I knew everything. As I get older and learn more I seem
to know less and less...)

 

[Philip Potter]

There are drafts of the standard readily available on the internet.
Google for n1124.

n1256 has superceded n1124. But I wouldn't recommend you read it cover-to-cover.