Computer Science Canada

[Tutorial] A Complete Look at: Bit Shifting
Author:  UBC_Wiskatos [ Tue Jul 01, 2003 5:51 pm ]
Post subject:  [Tutorial] A Complete Look at: Bit Shifting
This is the first tutorial in a series of articles I'm planning on writing when I, uh feel like it. Very Happy

Anyways, this tutorial focuses on bit shifting, something I haven't seen explained well anywhere. Bit shifting is a great optimization tool, and is a good thing to know, generally, when you get into Big Endian and Little Endian conversions, which I however, do not cover in this tutorial (perhaps a second part will cover all that stuff, this is mostly optimization oriented).

I'd love comments/questions/flames/rants on it, so you can check out the tutorial <a href="http://www.mironv.com/stuff/articles/ACompleteLookatOptimizatio.shtml">here</a>.
Author:  Tony [ Tue Jul 01, 2003 11:21 pm ]
Post subject: 
well thats kind of cool... though could you show an example of actual line of code for it?

also a note... that when shifting, number always gets modified by a power of 2 and when right-shifting it always floors the result to closest multiple of 2 since if last bit is 1, it will be lost Confused
Author:  UBC_Wiskatos [ Tue Jul 01, 2003 11:33 pm ]
Post subject: 
tony wrote:
well thats kind of cool... though could you show an example of actual line of code for it?

also a note... that when shifting, number always gets modified by a power of 2 and when right-shifting it always floors the result to closest multiple of 2 since if last bit is 1, it will be lost Confused


I don't know what you mean by an actual line of code? Like, an actual working program?
Author:  rizzix [ Wed Jul 02, 2003 12:10 am ]
Post subject: 
about the optimization part, it depends on the processor. some processors do mathematical operations faster than bit shifts.
Author:  UBC_Wiskatos [ Wed Jul 02, 2003 1:16 am ]
Post subject: 
Really? I've never encountered that before... Multiplication in assembly takes a few cycles on an x86, a bit shift is considerably less.
Author:  Tony [ Wed Jul 02, 2003 1:32 am ]
Post subject: 
thats why you get a math co-processor Laughing

and yes, I do mean an actual working program
Author:  UBC_Wiskatos [ Wed Jul 02, 2003 2:33 am ]
Post subject: 
tony wrote:
thats why you get a math co-processor Laughing

and yes, I do mean an actual working program


When you're going for pure optimization though, going to the math co-processor is still slower than bit-shifting, I believe.
Author:  Tony [ Wed Jul 02, 2003 2:58 am ]
Post subject: 
but as I mentioned above, bit shifting has a lot of flaws.

you can use it only when you know how many spaces to shift compile-time, else it will take up more time to figure out run-time then to just use standart operations. It also only works with 2^something numbers.

And even then you need to "know" that value ends with a 0, else when right-shifting the bit will be lost...
Author:  UBC_Wiskatos [ Wed Jul 02, 2003 11:05 am ]
Post subject: 
tony wrote:
but as I mentioned above, bit shifting has a lot of flaws.

you can use it only when you know how many spaces to shift compile-time, else it will take up more time to figure out run-time then to just use standart operations. It also only works with 2^something numbers.

And even then you need to "know" that value ends with a 0, else when right-shifting the bit will be lost...


Yes, that's why it is used for some optimization, more specifically, it is used in graphics optimization (I used it in my software blitter). Bit shifting is also invaluable when converting RGB values from different formats.

You usually do know most of the time what one of the values will be, and if you can optimize it by shifting, all the better. I don't know a situation where you'll have two unknowns a lot, but even then, if it is, say variable screen width, using function pointers and pointers, you can have no performance hit and still use bit shifting to speed it up.
Author:  bugzpodder [ Mon Jul 14, 2003 4:08 pm ]
Post subject: 
the link is down
Author:  UBC_Wiskatos [ Mon Jul 14, 2003 6:09 pm ]
Post subject: 
bugzpodder wrote:
the link is down


Whoops, I changed it a bit and forgot to update the link. It's fixed now, thanks for the heads-up!

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy