Thread: 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?

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

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

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.

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

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.

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

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?

Use & or | operators
Kurt

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

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