Please help me understand this...
Author 
Message 
jaime suar #1 / 16

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).  Thank you in advance, Jaime 

Mon, 28 Feb 2005 06:34:08 GMT 


Kenneth Brod #2 / 16

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 loworder _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 loworder 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 


Erik Max Franci #3 / 16

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 


Geoff Fiel #4 / 16

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 way  I'd opt for readability instead. 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; If the mask hadn't happened, the answer here would be 7. 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: > Thank you in advance,
I hope I've helped. Geoff  Geoff Field, Professional geek, amateur stagelevelling gauge.
au The suespammers.org mail server is located in California; do not send unsolicited bulk or commercial email to my suespammers.org address 

Tue, 01 Mar 2005 01:38:31 GMT 


Lars Dueni #5 / 16

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 TaDa! 

Tue, 01 Mar 2005 01:38:37 GMT 


Barry Schwar #6 / 16

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 


David Jone #7 / 16

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 


Dietmar Schindle #8 / 16

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 


HansBernhard Broeke #9 / 16

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 oldschool 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 microoptimization is usually a moot exercise these daysthe compiler will find them for you. 
Even if all the snow were burnt, ashes would remain. 

Tue, 01 Mar 2005 01:39:43 GMT 


Dan P #10 / 16

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 


Kiera #11 / 16

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 


Toby Speigh #12 / 16

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 


Erik Max Franci #13 / 16

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 


Geoff Fiel #14 / 16

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 clearer about it. Geoff  Geoff Field, Professional geek, amateur stagelevelling gauge.
au The suespammers.org mail server is located in California; do not send unsolicited bulk or commercial email to my suespammers.org address 

Fri, 04 Mar 2005 11:17:05 GMT 


Erik Max Franci #15 / 16

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 > matter addresses this point.
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/ Get your own customized newsfeed online in realtime ... for free! 

Mon, 07 Mar 2005 00:37:28 GMT 


Page 1 of 2

[ 16 post ] 

Go to page:
[1]
[2] 
