Archived

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

Swapping bits quickly

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

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 on other sites
OK, so if we don''t post the answer, how are we going to know if we figured it out ?

Bp.

Share on other sites
I figured it out.

(+1 informal, right?)

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 on other sites
the fastest (and easiest) way I know how to do this is:

x = ~x; // ~ flips the bits

Share on other sites
I think I see all the trips but my mind keeps going blank!

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 on other sites
To your second q. I have alot of solutions to do it in one turn. Now, the question is if any of those would count

/Fredrik

Share on other sites
OK, do we get the answer yet?
(I think I know what it is, but not certain).

Share on other sites
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 on other sites
**** 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 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;}

truePress any key to continue

"take a look around" - limp bizkit