# Bit-shifting to multiply and divide?

Discussion in 'C++' started by Nobody, Nov 14, 2004.

1. ### NobodyGuest

I have some code that I am trying to optimize for speed...

trying to squeeze every last CPU cycle out... I remembered an old trick
where dividing & multiplying can be sped up by using bitshifts and addition
/ subtraction instead (doing this saved me about 11% time on my 2.26ghz P4).
Really easy with powers of two. I implemented this last night when I was
tired, and this morning, I realize it was not exactly right (values were
slightly off)...

I am trying to multiply / divide by 255.

for some reason I thought:

(x << 8) - 1 = x * 255
(x >> 8) + 1 = x / 255

like I said, late at night....

seems like the correct formula is:

(x << 8) - x = x * 255;

but is it possible to do this for the division?

Nobody, Nov 14, 2004

2. ### Peter Koch LarsenGuest

"Nobody" <> skrev i en meddelelse
>I have some code that I am trying to optimize for speed...
>
> trying to squeeze every last CPU cycle out... I remembered an old trick
> where dividing & multiplying can be sped up by using bitshifts and
> 2.26ghz P4).

That 11% improvement you got must have been with code that wasn't compiled
at max. level of optimization.
> Really easy with powers of two. I implemented this last night when I was
> tired, and this morning, I realize it was not exactly right (values were
> slightly off)...
>
> I am trying to multiply / divide by 255.
>
> for some reason I thought:
>
> (x << 8) - 1 = x * 255
> (x >> 8) + 1 = x / 255
>
> like I said, late at night....
>
> seems like the correct formula is:
>
> (x << 8) - x = x * 255;
>
> but is it possible to do this for the division?
>

It probably is (i haven't studied your code carefully). What is important
here is that the compiler should know how to do it the best way, so just
continue writing x/8 or x/255 or whatever.

/Peter

Peter Koch Larsen, Nov 14, 2004

3. ### Karthik KumarGuest

Nobody wrote:
> I have some code that I am trying to optimize for speed...
>
> trying to squeeze every last CPU cycle out... I remembered an old trick
> where dividing & multiplying can be sped up by using bitshifts and addition
> / subtraction instead (doing this saved me about 11% time on my 2.26ghz P4).
> Really easy with powers of two. I implemented this last night when I was
> tired, and this morning, I realize it was not exactly right (values were
> slightly off)...
>
> I am trying to multiply / divide by 255.
>
> for some reason I thought:
>
> (x << 8) - 1 = x * 255
> (x >> 8) + 1 = x / 255
>
> like I said, late at night....
>
> seems like the correct formula is:
>
> (x << 8) - x = x * 255;

This is possible since -
x * 255 = x * (256 - 1 )
= (x * 256) - x
^^^^^^^^
Can be got by shifting to the left.

And here you get rid of the solitary multiplication.
do this for you anyway.

x / 255 != x / 256 * ( 1 + 1/255)

Not really sure if you want to express it this way.
Still you can't get rid of the division as you can see..

--
Karthik.
' Remove _nospamplz from my email to mail me. '

Karthik Kumar, Nov 14, 2004
4. ### Karthik KumarGuest

Karthik Kumar wrote:

[snipped]
>
> x / 255 != x / 256 * ( 1 + 1/255)

Oops .. Herez the right one.

x / 255 = x / 256 * ( 1 + 1/255)

--
Karthik.
' Remove _nospamplz from my email to mail me. '

Karthik Kumar, Nov 14, 2004
5. ### Method ManGuest

"Nobody" <> wrote in message
> I have some code that I am trying to optimize for speed...
>
> trying to squeeze every last CPU cycle out... I remembered an old trick
> where dividing & multiplying can be sped up by using bitshifts and

> / subtraction instead (doing this saved me about 11% time on my 2.26ghz

P4).
> Really easy with powers of two. I implemented this last night when I was
> tired, and this morning, I realize it was not exactly right (values were
> slightly off)...
>
> I am trying to multiply / divide by 255.
>
> for some reason I thought:
>
> (x << 8) - 1 = x * 255
> (x >> 8) + 1 = x / 255
>
> like I said, late at night....
>
> seems like the correct formula is:
>
> (x << 8) - x = x * 255;
>
> but is it possible to do this for the division?
>
>

I was once asked in an interview how to efficiently divide by 7 without
using division. I implemented it like so:

unsigned div7(unsigned x) {
long temp;
temp = (x * 293) >> 11; /* 1/7 is approx. equal to 293/2048 */
return (unsigned int) temp;
}

I am not sure if this helps (or is 100% correct), but you can use the same
strategy to divide by 255.

Method Man, Nov 14, 2004
6. ### joshGuest

Method Man wrote:
> "Nobody" <> wrote in message
>
>>I have some code that I am trying to optimize for speed...
>>
>>trying to squeeze every last CPU cycle out... I remembered an old trick
>>where dividing & multiplying can be sped up by using bitshifts and

[...]
>>but is it possible to do this for the division?

>
> I was once asked in an interview how to efficiently divide by 7 without
> using division. I implemented it like so:
>
> unsigned div7(unsigned x) {
> long temp;
> temp = (x * 293) >> 11; /* 1/7 is approx. equal to 293/2048 */
> return (unsigned int) temp;
> }
>
> I am not sure if this helps (or is 100% correct), but you can use the same
> strategy to divide by 255.

This works. I personally would write it more like:

unsigned div7(unsigned x)
{
return static_cast<unsigned>(
static_cast<unsigned long>(x * (2048/7)) / 2048);
}

(of course, then this technically uses division... and has *slightly*
higher error due to rounding)

If your compiler doesn't know how to convert multiplication/division by
powers of 2 into bit shifts, you need a better compiler. (are you sure

Division by 7, eg, is a different matter. The range where this method
is valid isn't the same as the range where a simple divide by 7 is
valid, so the compiler will probably not be able to do it automatically.

You're essentially doing a fixed-point multiply by the reciprocal.

-josh

josh, Nov 15, 2004
7. ### Niels DybdahlGuest

> x / 255 = x / 256 * ( 1 + 1/255)
>
> Not really sure if you want to express it this way.
> Still you can't get rid of the division as you can see..

And this is very close to:

x / 256 * ( 1 + 1/256)=x/256+x/65536

Niels Dybdahl

Niels Dybdahl, Nov 15, 2004