RSS Feed

techInterview Discussion

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]

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.

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

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?

No app Gene! A friend of mine asked me this and i suppose its an interview question!

i wonder if there is a clever trick using bitwise operators alone but as you said the math/logic must be tricky..

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.

Errr, that should really be

static const BYTE reverse[] ...

for performance reasons.

Skorj: could you please explain how making array as static const can improve performance ??

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.

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: If the array is global then also will it be pushed
      into stack before every calculation ? Still making
      array static necessary?

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.

for global consts the reason to use static is mainly to limit the scope.

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.

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 :-).