techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Reversing a String of Bits

Given a Bit String (say 1101) - reverse it (i.e, 1011)
Complexity requirements weren't given..

I am troubled as to which data type cud store a sequence of bits efficiently ?

can i store it as char* ? [trying to think in terms of well known string reversal problem]
KB
Thursday, January 03, 2008
 
 
Well, we want a function to reverse the bits in a byte.  Given that, we can reverse a longer stream if needed (assuming the bit stream is a round number of bytes long).

You can reverse the bits in a byte with a loop, with a lookup table, or with clever math.  The math required is particularly clever (i.e., obscure) in this case, so I just used a lookup table when I needed to do this in production code.
Skorj Send private email
Thursday, January 03, 2008
 
 
What sort of app do you need to do this in?

(My area is business apps, so I do not play much at all in the bit-twiddling sandbox.)

I ask because reversing bits seems rather contrived.  What is the RW application?

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Thursday, January 03, 2008
 
 
thanks skorj.. can you elaborate a bit on how you used the hashing tactic?

btw, how good/bad is this:
Bitwise ANDing the number with 1 from LSB to get the value at current digit, right shift once to get next digit in line and continuing the process of AND and >> till you get all bits. push each outcoming bit onto a stack and when the number gets to 0, pop all bits?
KB
Thursday, January 03, 2008
 
 
No app Gene! A friend of mine asked me this and i suppose its an interview question!
KB
Thursday, January 03, 2008
 
 
i wonder if there is a clever trick using bitwise operators alone but as you said the math/logic must be tricky..
KB
Thursday, January 03, 2008
 
 
I needed to reverse the bits in a series of bytes as part of a hashing algorithm.

I just used a lookup table to reverse the bits in a byte:

BYTE reverse[] = { 0x00, 0x80, 0x40, ... };
BYTE output = reverse[input];

Very simple, and fast enough.
Skorj Send private email
Friday, January 04, 2008
 
 
Errr, that should really be

static const BYTE reverse[] ...

for performance reasons.
Skorj Send private email
Friday, January 04, 2008
 
 
Skorj: could you please explain how making array as static const can improve performance ??
gun0m
Friday, January 04, 2008
 
 
When the array is not static it must be pushed on the stack on every call.  This could be quite expensive.

A static array is allocated before main() is called.

const just because that how I use the array.
Skorj Send private email
Friday, January 04, 2008
 
 
Hmm, OK, technically static means it's allocated before the first time the function is called.  Some compilers actually wait for the first call to perform the initialization, which I've always found annoying (this actually varies between versions of the common compilers).
Skorj Send private email
Friday, January 04, 2008
 
 
Skorj: If the array is global then also will it be pushed
      into stack before every calculation ? Still making
      array static necessary?
gun0m
Friday, January 04, 2008
 
 
For a global array, it will not be pushed onto the stack. But making a global data structure unless and until it is a must does not make sense.
dark horse
Saturday, January 05, 2008
 
 
for global consts the reason to use static is mainly to limit the scope.
^Shhh^ Send private email
Saturday, January 05, 2008
 
 
A static variable declared in the scope of a function is just a global with visibility limited to the scope of the function (similarly for a static class member).

Constant values are the one thing that global storage is good for, though of course you always want to limit the scope to the code that needs them.
Skorj Send private email
Monday, January 07, 2008
 
 
unsigned int v;    // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)

  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

I haven't written this :-).
Ganesh M Send private email
Monday, February 11, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz