# Thread: division by a power of 2

1. ## division by a power of 2

A question about performance:

int x = 0;
...
...
x = 123456 * z; // z is not zero, is dynamic

int y = x / 2;

Everywhere I read this is a shift operation, but this to me seem like the compiler has to take into account the sign, so it must do a complete division which takes much cycles than a >>

this to me seem more in that sense

unsigned int x = 0
x
...
...
x = 123456 * z // z is not zero, is dynamic

int y = x / 2; // the compiler here will use >>

am I correct?

2. You do realize that this is a difference of literally a few nanoseconds of execution time, right?

Either way, I'm not sure what you're asking. Assuming compiler optimization is turned on, the compiler can make decisions on how to best optimize the code, and sometimes this involves replacing division with shifts. And, whether the number is signed or unsigned is irrelevant: shifting can be performed on either type whether you code it or the compiler optimizes it in.

Edit: look at the ANSI C Standard section 3.3.7.

3. I do not how the sign can play a key role here.However if your compiler is clever enough it is going to select the best approach for your code

EDIT -> memcpy is too fast :P

4. A shift right operation works independent of the sign.
If I remember right that is called sign extension. That means for a shift right operation the bits on the left are alwais filled with the original sign bit.
try this

Code:
```#include <stdio.h>

int main() {
printf("%d\n", -1234 >> 1);
printf("%d\n", 1234 >> 1);
}```
output :
Code:
```-617
617```
btw I don't think that the compiler will translate a division by a power of two into a shift operation. The optimizer might do.
Kurt

EDIT: beaten by two

5. Originally Posted by memcpy
You do realize that this is a difference of literally a few nanoseconds of execution time, right?

Either way, I'm not sure what you're asking. Assuming compiler optimization is turned on, the compiler can make decisions on how to best optimize the code, and sometimes this involves replacing division with shifts. And, whether the number is signed or unsigned is irrelevant: shifting can be performed on either type whether you code it or the compiler optimizes it in.
What I want is to know how the compiler works because knowledge is better for any programmer. It could be worthy for your propouses or be only general culture. Both are positive.

You say is irrelevant, but I suspect no. The compiler cannot replace a / with a >> for a signed because then the sign bit will be moved also, and the result could be different. I suspect in the first case the compiler can't do the optimization while in the seconds it can.
It could be a question of nanoseconds, but if the operation is trillions of time repeated it could be a notificable penalty.

6. > he compiler cannot replace a / with a >> for a signed because then the sign bit will be moved also
Incorrect. Again, if I'm not mistaken, a shift will produce the same results whether it is performed upon a signed or unsigned value.

> but if the operation is trillions of time repeated it could be a notificable penalty.
I did a quick test counting cycles of a million shifts, yielding:
Code:
```signed division: 7000360 cycles
unsigned division: 6999935 cycles
signed shift: 7000027 cycles
unsigned shift: 7010618 cycles```
No appreciable difference, and the division was faster than the shifting half of the time.

7. Originally Posted by memcpy
Incorrect. Again, if I'm not mistaken, a shift will produce the same results whether it is performed upon a signed or unsigned value.
Of course the result would be the same, but I am not asking if the shight will produce the same result, what I am asking is if the compile can replace the division by a shift, and It cann't because if a division by two of a negative number the the result would not be the same.
Of course for an unsigned int it can, but it assume the programmer knows that is always possitive, so its declared as unsingned.
The real test would be to see the asm output and compare the results and count cycles for each instruction but I dont know how to do that
Also could you provide the code for your test. It must be doing without constant, in the manner that the compiler dont know the sign when dividing.

8. Originally Posted by Kempelen
.... , and It cann't because if a division by two of a negative number the the result would not be the same..
Wrong. See my prev post
Kurt

9. Originally Posted by ZuK
A shift right operation works independent of the sign.
If I remember right that is called sign extension. That means for a shift right operation the bits on the left are alwais filled with the original sign bit.
try this

Code:
```#include <stdio.h>

int main() {
printf("%d\n", -1234 >> 1);
printf("%d\n", 1234 >> 1);
}```
output :
Code:
```-617
617```
btw I don't think that the compiler will translate a division by a power of two into a shift operation. The optimizer might do.
Kurt

EDIT: beaten by two
Thanks, this goes in the direction in the answer I hoped. Anyway if I use a shift in my code (not for the porposes of dividing), and I want always to be filled with 0, or 1 at right, how I do that?

10. Use & or | operators
Kurt

11. Thanks, today I have learn something I didn't know before. To make a shift (not for dividing) you must know the sign influence the result, so that if you expect a diferent result other operations must to be done.
Before I thought a shifht operation is always filled with 0, and I bet most programmer incorrectle thing the same.
Very valueable info for the operations I am doing know....

12. It is unspecified whether signed >> is an arithmetic or logical shift. In other words you will get a platform-specific result when right shifting a signed integer.

That said, all sane platforms use sign-extending right shift, which means it is equivalent to dividing by two.

13. O_o

Write the code with the division and let the compiler give you the best optimizations it can give you.

You don't have to worry whether or not you "sign extension" that way.

Soma

14. While you're busy messing with the very low level detail that any decent compiler will take care of, don't forget the big picture.
Optimization of Computer Programs in C

If you screw up in the design and implementation stage by choosing poor algorithms and data structures, then no amount of micro-management will rescue you.

And make sure you identify REAL problem areas using whatever profiling tools you have.

15. I have to say Kempelen, I really like the way you thought analytically about this problem.

Phantomotap's response is one valid side of the coin. The other is that if what you really logically want is a bitshift, using a division, and working out what the relevant power of two should be in order to perform the correct shift is at least as crazy.

So the overall result is that as a C programmer you can use whichever best expresses your intentions, and the compiler will generally do a good job of translating that to efficient code.

Popular pages Recent additions