Jump to content
  • Advertisement


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


Swapping bits quickly

This topic is 5565 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I recently found this as an example of an interview test question: "What''s the quickest way to ''reverse'' all the bits of an 8-bit integer ie 01100100 -> 10011011?" Now they give the answer as to use a LUT but can''t you just use a logical NOT operator ''¬''? Which I''d think was faster? If you were doing it lots the LUT for 256 values would go in the cache easy but just doing it once wouldn''t have to be loaded (slow)? Incidentally this question is very cool : "You have 3 light switches in one room and 3 incandescant lights in another. What''s the least number of trips between rooms you need to establish which switch operates which light?" If you know the answer don''t give it away but I''d be interested to see how many people figure it out.

Share this post

Link to post
Share on other sites
Why can't you use the NOT operator?

--- Edit ---
Unless it's just for fun and not a question at all.

[edited by - SIaon on July 28, 2003 8:51:45 AM]

I'd say just test the bits:

void inverse(char &byte)
char temp=0;
for(int i=0;i<8;i++)
if(byte&1)//if the first bit of our byte is set
byte>>1;//shift the byte to the right by one

I don't know if all this is valid c++, im not used to doing bitwise operation in c++, but look at the comments and know how I mean it works.

[edited by - siaon on July 28, 2003 8:58:38 AM]

Share this post

Link to post
Share on other sites
A few ways to do this:

y = LUT[x];
y = ~x;
y = x^0xFF;
y = ( LUT1[x >> 4] ) & ( LUT2[ x & 0xF ] );

If it''s only 8-bit then lookup tables might be ok. The bottom solution uses two lookup tables, which uses less cache, but additional operations. Might be optimized if the processor supports parallel operations.

I know the answer for the #2 quesiton too.


Share this post

Link to post
Share on other sites
Guest Anonymous Poster
the original question was most likely to reverse the ORDER of the bits. 11010010 => 01001011
That problem would indeed be nicely solved with a LUT.
Using a LUT instead of ~ is just stupid.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!