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:

Whoops, I changed it a bit and forgot to update the link. It's fixed now, thanks for the heads-up!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 11 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: