Swapping bits quickly
Author
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.
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]
--- 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]
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
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
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
/Fredrik
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.
That problem would indeed be nicely solved with a LUT.
Using a LUT instead of ~ is just stupid.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
