Archived

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

d000hg

Swapping bits quickly

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
temp=temp|(1<processing
byte>>1;//shift the byte to the right by one
}
byte=temp;
}

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.


ToohrVyk

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
Guest Anonymous Poster
**** Spoiler ****

(am I begin cautious enough?)
Turn one switch on, let it be like that for 10 minutes. Then turn it off and turn some other switch on. Then go to room. The one that''s shining is the one that you just switched on. The one that''s hot is the one you held on for 10 minutes. Thus you only need to go there once.

Share this post


Link to post
Share on other sites

#include <iostream>

int main(int argc, char* argv[]) {
unsigned char original = 0x0F;
unsigned char inverted = 0xF0;
std::cout<<((inverted == 255 - original)?"true":"false")<<std::endl;
return 0;
}



true
Press any key to continue


"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Yeah sorry I think that should have been to reverse the order. My bad.
The light question is indeed as said - leave one on then turn it off, turn a second on and go to the room. The hot one you just turned off, the one on is the one you just turned on & the last one is obviously the 3rd one!

I failed on this by trying to do it through logic not lateral thinking btw! Who else got it?

Share this post


Link to post
Share on other sites