Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[Tutorial] A Complete Look at: Bit Shifting
Author Message
UBC_Wiskatos

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

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

Tony

Posted: Tue Jul 01, 2003 11:21 pm   Post subject: (No 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
Tony's programming blog. DWITE - a programming contest.
UBC_Wiskatos

Posted: Tue Jul 01, 2003 11:33 pm   Post subject: (No 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

I don't know what you mean by an actual line of code? Like, an actual working program?
rizzix

Posted: Wed Jul 02, 2003 12:10 am   Post subject: (No subject)

about the optimization part, it depends on the processor. some processors do mathematical operations faster than bit shifts.
UBC_Wiskatos

Posted: Wed Jul 02, 2003 1:16 am   Post subject: (No subject)

Really? I've never encountered that before... Multiplication in assembly takes a few cycles on an x86, a bit shift is considerably less.
Tony

Posted: Wed Jul 02, 2003 1:32 am   Post subject: (No subject)

thats why you get a math co-processor

and yes, I do mean an actual working program
Tony's programming blog. DWITE - a programming contest.
UBC_Wiskatos

Posted: Wed Jul 02, 2003 2:33 am   Post subject: (No subject)

tony wrote:
thats why you get a math co-processor

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

Posted: Wed Jul 02, 2003 2:58 am   Post subject: (No 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...
Tony's programming blog. DWITE - a programming contest.

UBC_Wiskatos

Posted: Wed Jul 02, 2003 11:05 am   Post subject: (No 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.
bugzpodder

Posted: Mon Jul 14, 2003 4:08 pm   Post subject: (No subject)

UBC_Wiskatos

Posted: Mon Jul 14, 2003 6:09 pm   Post subject: (No subject)

bugzpodder wrote: