Archived

This topic is now archived and is closed to further replies.

UBC_Wiskatos

Tutorial on Bit Shifting

Recommended Posts

I've made up a tutorial on how bit shifting works in terms of multiplication and optimization. It is my first tutorial, so please if you have any crits, I would love to hear them. I'm going to put up a second part which involves using bit shifting for converting RGB values and big endian/little endian stuff. You can check out the tutorial, here. [edited by - UBC_Wiskatos on July 2, 2003 12:01:02 PM]

Share this post


Link to post
Share on other sites
Nice, I always wanted to know about bit shifting, and I get it now. Anyway, it''s pretty explanatory. Nice work...

Battleguard



Only questions raise questions. Questions are raised by people, by curiousity, the gift of nature to all human beings. And curiosity is satisfied by answers, which in turn raise questions, which lead to answers. And this curiosity is what keeps SCIENCE alive...

Share this post


Link to post
Share on other sites
question.... doesent certain compilers (namely visual C++ professional and above) already do these optimizations internaly? I believe i figured this out before after checking the asm code.......

Curiously

Ricky Cesar
Omerae Interactive

Share this post


Link to post
Share on other sites
Please don''t take offense, Wisk, but your tutorial is extremely misleading. The compiler is more than capable of recognizing that bitshifting can be used for multiplication, and choosing the appropriate operator sequence to maximize performance. Moreover, it (the compiler) knows a heck of a lot more than you about the target architecture''s performance profile, so it will often do a better job. Lastly, you''ve neglected to mention the problems and incompatibilities that bitshifting signed integers can cause. Overall, not a bad description of how binary arithmetic works, but should be accompanied by a frank assessment of how much difference the techniques you present will make.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
quote:
Original post by PaulCesar
question.... doesent certain compilers (namely visual C++ professional and above) already do these optimizations internaly? I believe i figured this out before after checking the asm code.......

Curiously

Ricky Cesar
Omerae Interactive


I''m pretty sure they might, although I don''t know exactly. Even if they do, I figure it is always nice to know the underlying workings of some concepts, even if they may be done for you.

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
Please don''t take offense, Wisk, but your tutorial is extremely misleading. The compiler is more than capable of recognizing that bitshifting can be used for multiplication, and choosing the appropriate operator sequence to maximize performance. Moreover, it (the compiler) knows a heck of a lot more than you about the target architecture''s performance profile, so it will often do a better job. Lastly, you''ve neglected to mention the problems and incompatibilities that bitshifting signed integers can cause. Overall, not a bad description of how binary arithmetic works, but should be accompanied by a frank assessment of how much difference the techniques you present will make.


How appropriate. You fight like a cow.


None taken, it was more of a tutorial on how the concept works and how one would apply it, so you know anyway, even if the compiler might do it for you. I will add to my tutorial though, for sure. Thank you for your criticism!

Share this post


Link to post
Share on other sites
Sure, most compilers will translate 'variable * 2' into variable << 1. But it never hurts to know.
Who knows, one day your job might require you to work with assembler. And maybe you'd need to be able to optimize by hand even. (Before you go and say 'No one needs assembler nowadays', if you go into hi-end car electrics, you will)

Besides that, bit shifts can be used for a lot more then just fast multiplications and divisions.

One very famous example might be AES (Advanced Encryption Standard). Relies almost entirely on bitshifts. This way AES is not only ways more secure then DES or 3DES, but also a lot faster.

Let's say you have to check the single bits of a char, how'd you do that without shifts?


for (long n=0;n<8;n++)
{
   if (((mychar >> n) & 1) == 1)
      break;
}

std::cout << "The " << n << " last bits of mychar are empty";


Edit: I know the example is stupid. Maybe go look up "crc" on google, that might be something else that requires shifts.

[edited by - Wildfire on July 2, 2003 12:48:48 PM]

Share this post


Link to post
Share on other sites
for some reason i thought i was correct. Nice tutorial though wisk. I could have used some of that 6 years ago when i was doing asm on my ol' system.

somehow i miss the good old denthor days..... anybody remember?

[edited by - paulcesar on July 2, 2003 1:07:12 PM]

Share this post


Link to post
Share on other sites
I've been doing a fair bit of 80386 assembler in my youth. (Though assembly was already 'dead' at that time). I think it tought me a lot about how computers really work though. And I learned quite a few tricks that come in handy even when working with C++.
Edit: Maybe I should say 8086, never came around to try the fancy protected mode stuff the 386 offers =(

[edited by - Wildfire on July 2, 2003 1:11:39 PM]

Share this post


Link to post
Share on other sites