Author Message Please help me understand this...

In a Windows programming book by Charles Petzold, I encountered the following:

| iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
|                                                        |
| or, as a C programmer might tend to write it,          |
|                                                        |
| iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

I can make sense of the equivalence between
2*(( SomeExpression )/16)
and
( SomeExpression ) >> 3

What I **don't** follow is why mask off the lower four bits
with (( ... ) & ~15).
-----

Jaime
--

Mon, 28 Feb 2005 06:34:08 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

The above are _not_ equivalent.  See below.

Quote:
> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

Because, by dividing by 16 and then multiplying by 2, the result
is _not_ the same as dividing by 8 (or shifting right by 3).  The
division by 16 has caused the low-order _4_ bits to be lost.

In other words, it's the same as dividing by 8 (or shifting right
by 3) and then masking off the low-order 1 bit.

Depending on context, it might make more logical sense to mask off
4 bits and shift by 3, than to shift by 3 and mask 1, though the
results are the same.

--

+---------+----------------------------------+-----------------------------+
| Kenneth |     kenbrody at spamcop.net      | "The opinions expressed     |
|    J.   |    http://www.hvcomputer.com     |  herein are not necessarily |
|  Brody  |      http://www.fptech.com       |  those of fP Technologies." |
+---------+----------------------------------+-----------------------------+
--

Tue, 01 Mar 2005 01:38:25 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the
> following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).

Because in integer arithmetic, 2*(x/16) is not the same thing as x/8.
Put in terms of shifts, 2*(x/16) could be written (x >> 4) << 1.  That's
not the same thing as x >> 3, because x >> 4 will destructively shift
that bit off, and y << 1 will replace it with a zero.

--

__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/  \ Freedom is a road seldom travelled by the multitudes
\__/ Public Enemy
Church / http://www.alcyone.com/pyos/church/
A lambda calculus explorer in Python.
--

Tue, 01 Mar 2005 01:38:28 GMT  Please help me understand this...

Quote:
> In a Windows programming book by Charles Petzold, I encountered the
following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

Personally, as a C programmer, I *wouldn't* write it this

Quote:
> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)

Note that this is *exactly* equivalent (mathematically, anyway)
to division by 8, which in turn is *exactly* equivalent (in bitwise
terms) to a shift left by 3 bits.

Quote:
> and
>   ( SomeExpression ) >> 3

> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

The idea is that when one multiplies by 2 (as the top expression
does), it's effectively a right shift by one bit, with a 0 going into
the bottom bit (LSB).  The mask here could equally well have been
~8 rather than ~15 in order to leave the LSB clear after the shift left
by 3.

Work it through.  Let's say cBitsPixel = 15 (0x0F) and cx = 3.

iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;
= 2 * ((3  * 0x0F     + 15) / 16);
= 2 * ((0x2D         + 15) / 16);
= 2 * ((0x3C             ) / 16);
= 2 * (3);
= 6;

iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;
= (3  * 0x0F       + 15) & ~15) >> 3 ;
= (0x2D            + 15) & ~15) >> 3 ;
= (0x3C                ) & ~15) >> 3 ;
= (0x30                )) >> 3 ;
= 6;

There is a saving here if your compiler is not doing adequate
optimisation because you use a mask and a shift (cheap operations)
instead of a multiply and divide.

Quote:

I hope I've helped.

Geoff

--
Geoff Field,    Professional geek, amateur stage-levelling gauge.

au
The suespammers.org mail server is located in California; do not send
unsolicited bulk or commercial e-mail to my suespammers.org address
--

Tue, 01 Mar 2005 01:38:31 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

There are at least two ways to look at this problem: one trying to get
the right answer, the other trying to understand what the code is doing.

1. Naming the value of (cx * cBitsPixel + 15) just 'width', what the
expression '2 * (width / 16)' does is transforming  the bitpattern

... b7 b6 b5 b4 b3 b2 b1 b0

into the bitpattern

...b10 b9 b8 b7 b6 b5 b4  0

If you'd just compute 'width >> 3', you'd get

...b10 b9 b8 b7 b6 b5 b4 b3

which is wrong because of the extra b3. Masking off the lower four bits
before shifting solves the problem. You could of course use '(width >>
3) & ~1' for the same result, but that would obscure what the code is
doing.

2. What the expression

2 * ((cx * cBitsPixel + 15) / 16)

really computes is

(((cx * cBitsPixel + 15) / 16) * 16) / 8

that is the width of (cx * cBitsPixel) pixels rounded up to the next
multiple of 16, and then divided by 8 to get the number of bytes
required.

The expression '(val / 16) * 16' is equivalent to '(val >> 4) << 4',
which results in val with the lower four bits masked out: 'val & ~15'.
Division by 8 is equivalent to '>> 3', so we get:

((cx * cBitsPixel + 15) & ~15) >> 3

Ta-Da!
--

Tue, 01 Mar 2005 01:38:37 GMT  Please help me understand this...

Quote:

>In a Windows programming book by Charles Petzold, I encountered the following:

>  | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>  |                                                        |
>  | or, as a C programmer might tend to write it,          |
>  |                                                        |
>  | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

>I can make sense of the equivalence between
> 2*(( SomeExpression )/16)
>and
>  ( SomeExpression ) >> 3

There not quite equivalent as discussed below.

Quote:

>What I **don't** follow is why mask off the lower four bits
>with (( ... ) & ~15).

The first expression involves a division by 16 and then a multiply by
two.  This is almost the same as simply dividing by 8 except the
result will always be even.  Looked at another way, the /16 removes
the four low order bits and the 2* inserts a new low order bit of 0.
The end result is the three low order bits are discarded and the
fourth is set to 0 and it ends up as the new low order bit.

The second expression achieves the same result masking off all four
low order bits and shifting to left three.  The fourth low order bit
ends up in the low order position.  Since it which was masked off, the
result is also always even.  Since the three low order bits contribute
nothing to the result, the ~15 could have been replaced with a ~8 with
no change to the final answer.  The purpose of the & is to insure the
fourth bit is 0 before the shift.

It might be easier to visualize as ((SomeExpression) >>3) & ~1 which
removes the three low order bits and then sets the new low order bit
to 0.

<<Remove the del for email>>
--

Tue, 01 Mar 2005 01:38:48 GMT  Please help me understand this...

Quote:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

When you have 2*(( SomeExpression )/16), that is NOT the same as
( SomeExpression ) >> 3.  The reason is that whenever you do the
integer division ( SomeExpression )/16 you get an integer.  So,
when you multiply it by 2, you are *guaranteed* to get an even
number.  This is not the case with shifting right by 3.  For
example, your number could be ...101001, which when shifted right
by 3 would give you ...101.

The mask is not so much for the lower three bits but for that
fourth bit.  It is needed to guarantee it to be zero.  There are,
of course, other ways to do this, such as
iWidthBytes = (cx * cBitsPixel + 15) >> 3) & ~1 ;

I hope that makes sense.

David Jones
--

Tue, 01 Mar 2005 01:38:49 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

These aren't equivalent. The least significant bit of the first
expression's value is 0 (because the value is a multiple of 2), the LSB
of the second value is the fourth bit from the right of SomeExpression.

Quote:
> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

I think you do now.
--

Tue, 01 Mar 2005 01:38:55 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the following:
>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

Mr. Petzold doesn't know "a C programmer"'s tendencies good enough to
tell the truth, here, I think...

Quote:
> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

You're misguided.  These two statements are not equivalent.  The
difference is that the least significant bit in the first expression's
result is guaranteed to be zero.  In the second, it's not.

An old-school C programmer (setting aside the issue that you shouldn't
ever shift a signed integer in a portable program) would have written:

((SomeExpression) >> 3) & ~1

or maybe a bit more cryptically:

((SomeExpression & ~8) >> 3

or, to stay closer to the original

((SomeExpression >> 4) << 1

OTOH, all such obfuscating micro-optimization is usually a moot
exercise these days---the compiler will find them for you.
--

Even if all the snow were burnt, ashes would remain.
--

Tue, 01 Mar 2005 01:39:43 GMT  Please help me understand this...

Quote:
>In a Windows programming book by Charles Petzold, I encountered the following:

>  | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>  |                                                        |
>  | or, as a C programmer might tend to write it,          |
>  |                                                        |
>  | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

>I can make sense of the equivalence between
> 2*(( SomeExpression )/16)
>and
>  ( SomeExpression ) >> 3

>What I **don't** follow is why mask off the lower four bits
>with (( ... ) & ~15).
>              -----

The lower 3 bits don't matter, because the shift will discard them,
anyway.  The 4th bit does matter, because the result of the expression
must be an even number (compare with the original expression).

Dan
--
Dan Pop
DESY Zeuthen, RZ group

--

Tue, 01 Mar 2005 01:39:45 GMT  Please help me understand this...

Quote:

> In a Windows programming book by Charles Petzold, I encountered the following:

>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
>   |                                                        |
>   | or, as a C programmer might tend to write it,          |
>   |                                                        |
>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |

> I can make sense of the equivalence between
>  2*(( SomeExpression )/16)
> and
>   ( SomeExpression ) >> 3

> What I **don't** follow is why mask off the lower four bits
> with (( ... ) & ~15).
>               -----

Because otherwise the two are not equivalent since bit 3 of
SomeExpression is ignored in the former, whereas it is used in the
latter expression you gave.

e.g.:

Suppose SomeExpression = 8.

Then, (SomeExpression) >> 3 is 1.

However, 2 * (SomeExpression / 16) = 0 since (8/16) = 0 in integer
arithmetic.

Regards,
Kieran Elby
--

Tue, 01 Mar 2005 01:39:53 GMT  Please help me understand this...

Jaime> In a Windows programming book by Charles Petzold, I encountered
Jaime> the following:
Jaime>
Jaime>   | iWidthBytes = 2 * ((cx * cBitsPixel + 15) / 16) ;      |
Jaime>   |                                                        |
Jaime>   | or, as a C programmer might tend to write it,          |
Jaime>   |                                                        |
Jaime>   | iWidthBytes = (cx * cBitsPixel + 15) & ~15) >> 3 ;     |
Jaime>
Jaime>
Jaime> I can make sense of the equivalence between
Jaime>  2*(( SomeExpression )/16)
Jaime> and
Jaime>   ( SomeExpression ) >> 3
Jaime>
Jaime> What I **don't** follow is why mask off the lower four bits
Jaime> with (( ... ) & ~15).
Jaime>               -----

I looks like we're doing integer arithmetic, which means that dividing
by 16 then multiplying by 2 has the same effect as dividing by 8 and
clearing bit 0.

So (2 * (foo / 16)) == ((foo >> 3) & ~1)

If we do the masking first, before the shift, then we have to mask
with ~(1<<3) i.e. 8.  The bottom three bits of the mask have no
effect, as their result gets shifted out, so any value between 8 and
15 is okay.  Your book chose 15.
--

Tue, 01 Mar 2005 01:39:55 GMT  Please help me understand this...

Quote:

> > I can make sense of the equivalence between
> >   2*(( SomeExpression )/16)

> Note that this is *exactly* equivalent (mathematically, anyway)
> to division by 8, which in turn is *exactly* equivalent (in bitwise
> terms) to a shift left by 3 bits.

That some be true of SomeExpression were real, but it is not; it is an
integer expression, and so 2*(x/16) involves integer mathematics.  In
integer mathematics, where division can involve loss of precision, they
are not equivalent.

--

__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/  \ The revolution will not televised
\__/ Public Enemy
Blackgirl International / http://www.blackgirl.org/
The Internet resource for black women.
--

Wed, 02 Mar 2005 16:19:35 GMT  Please help me understand this...

Quote:

> > > I can make sense of the equivalence between
> > >   2*(( SomeExpression )/16)

> > Note that this is *exactly* equivalent (mathematically, anyway)
> > to division by 8, which in turn is *exactly* equivalent (in bitwise
> > terms) to a shift left by 3 bits.

> That some be true of SomeExpression were real, but it is not; it is an
> integer expression, and so 2*(x/16) involves integer mathematics.  In
> integer mathematics, where division can involve loss of precision, they
> are not equivalent.

Yes, I'm extremely aware of that.  In fact, the rest of my post on the
matter addresses this point.  An equivalent expression to the original
is actually closer to:

((SomeExpression) / 8) & ~1

or:

((Some Expression) >> 3) & ~1

As my post said, /8 is identical in effect to >>3.  I just wish I'd been

Geoff
--
Geoff Field,    Professional geek, amateur stage-levelling gauge.

au
The suespammers.org mail server is located in California; do not send
unsolicited bulk or commercial e-mail to my suespammers.org address
--

Fri, 04 Mar 2005 11:17:05 GMT  Please help me understand this...

Quote:

> > > Note that this is *exactly* equivalent (mathematically, anyway)
> > > to division by 8, which in turn is *exactly* equivalent (in
> > > bitwise
> > > terms) to a shift left by 3 bits.

> > That some be true of SomeExpression were real, but it is not; ...

> Yes, I'm extremely aware of that.  In fact, the rest of my post on the

You said that it was exactly equivalent, and that is obviously not the
case.  It _would_ be true if the division operator involved were
division over the reals, but it was not; it is integer division.

--

__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/  \ Success and failure are equally disastrous.
\__/ Tennessee Williams
REALpolitik / http://www.realpolitik.com/