## Flip the endian-ness of a long in C#

**Programming challenge:**

Write me a function with this signature **in C#**:

public (unsafe?) long Reverse(long i, int bits)

...to flip the endian-ness (LSB/MSB) of a long, but **just the # of significant bits specified**.

Example, if the input is 376, with bits=11, the output is 244 (decimal, base 10).

376 = 000

00101111000244 = 00000011110100

Example, if the input is 900, with bits=11, the output is 270.

900 = 000

01110000100

270 = 00000100001110

Example, if the input is 900, with bits=12, the output is 540.

900 = 00

001110000100

540 = 00001000011100

Example, if the input is 154, with bits=4, the output is 5.

154 = 0000001001

1010

5 =00000000000101

And make it FAST...;)

#### About Scott

Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.

About Newsletter

public long Reverse(long word, int bits)

{

ulong n = (ulong)word {{ (64-bits);

n = n }} 32 | n {{ 32;

n = n }} 0xf & 0x0000ffff | n {{ 0xf & 0xffff0000;

n = n }} 0x8 & 0x00ff00ff | n {{ 0x8 & 0xff00ff00;

n = n }} 0x4 & 0x0f0f0f0f | n {{ 0x4 & 0xf0f0f0f0;

n = n }} 0x2 & 0x33333333 | n {{ 0x2 & 0xcccccccc;

n = n }} 0x1 & 0x55555555 | n {{ 0x1 & 0xaaaaaaaa;

return (long) n | word & (-1 {{ bits);

}

I tried this:

long reverse(long data,int bits)

{

int i;

long l;

l = 0;

for(i = 0; i < bits; i++)

{

l |= (long) (((data & (((long) 1)<<i)) ? 1:0)) << (bits - 1 - i);

}

return l;

}

But got stuck in middle with the left shift not working the same in C# as it does in C++.

Then I headed in this general direction but got lost along the way:

public unsafe long Reverse(long i)

{

byte b1, b2, b3, b4;

b1 = (byte)(i & 255);

b2 = (byte)((i >> 8) & 255);

b3 = (byte)((i >> 16) & 255);

b4 = (byte)((i >> 24) & 255);

return (long)(((int)b1 << 24) + ((int)b2 << 16) + ((int)b3 << 8) + b4);

}

You just whip yours out, or did you have it lying around?

The right shift has two different behavior (arithmetic versus logical shift) depending on whether the type is signed or not.

(ulong) >>

(long) >>

http://jasonf-blog.blogspot.com/2006/08/hanselmans-endianess-converter.html

public long Reverse(long i, int bits)

{

long reversed = 0;

int j = 0;

for (j = 0; (j < (bits / 2)) && (j < 32); j++)

{

// Swap elements j, bits-j

reversed |= (((i >> (bits - j - 1)) & 0x1) << j);

reversed |= (((i >> j) & 0x1) << (bits - j - 1));

}

if (0 != (bits % 2))

{

// for an odd bits value, assign the middle value

reversed |= (((i >> (bits - j - 1)) & 0x1) << j);

}

return reversed;

}

I'd be interested in seeing the timing results...

-Joe

public static long Reverse(int i, int bits)

{

int rev = 0;

while (bits-- > 0)

{

rev <<= 1;

rev = rev + (i & 1);

i >>= 1;

}

return rev;

}

Yes, mine is O(N), but N is the value of bits, which is <= 32, while all the so-called O(1) solutions here are really O(ln N) where N is the number of bits in i. I would expect an insignificant speed difference among them.

{

Mask m = new Mask(bits);

long result;

long rval;

long calculatedRight=0;

long lMaskLeft;

// Get the block of bits

result = l & m.Right;

for (int i = 0; i < bits; i++)

{

// result = 543

rval = result >> (bits - (i + 1)); // if bits is 3 then rval=5

// Add to build

calculatedRight += (rval << i);

// Calculate new result

result = result - (rval << bits - (i + 1));

}

// Zero out the right part... and keep just the left part.

lMaskLeft = l & m.Left;

// Return the left part and the new calculated right part.

return lMaskLeft + calculatedRight;

}

public class Mask

{

private long _left;

private long _right;

public Mask(int bits)

{

this._left = (long.MaxValue) << bits;

this._right = long.MaxValue >> (64 - (1 + bits));

}

public long Left

{

get { return _left; }

}

public long Right

{

get { return _right; }

}

}

public unsafe static long Reverse(long i, int bits)

{

long x = 0;

for(int bit = 0; bit < bits; bit++)

{

x |= ((i & (1 << bit)) == 0) ? 0 : (1 << (bits - bit - 1));

}

return x;

}

I was curious about the difference between this solution and Nicholas' solution, so I called each method 4,000 times in a loop. According to Performance Explorer using instrumented profiling, the looping solution requires 0.822978 seconds whereas Nicholas' solution requires 0.418179 seconds (roughly twice as fast).

I tried timing all of the variations using the StopWatch class (starting it before the function call, and stopping it after, repeating for x iterations, and then averaging the ElapsedTicks. The results usually put Nicholas's solution first, but not consistently. Ivan's approach was consistently always last, though. :(

But, then out of curiosity, I commented out the Reverse() function calls, and didn't see any changes in my timings!!! That suggests some sort of Heisenberg phenomenon with my method.

An additional point of consideration: using 16-bit tables increased the memory requirements by a factor of 512 over the 8-bit table. So for the cost of 128+ KB of memory, you get a 15% improvement over Nicholas's algorithm that has no memory requirements. Memory is cheap, but in this case, would it make Scott's HDTV change channels any faster? Probably not.

The C# code from my trials is at the link that I posted above.

Comments are closed.

public long Reverse(long i, int bits) {

i = ((i >> 1) & 0x5555555555555555) | ((i & 0x5555555555555555) << 1);

i = ((i >> 2) & 0x3333333333333333) | ((i & 0x3333333333333333) << 2);

i = ((i >> 4) & 0x0F0F0F0F0F0F0F0F) | ((i & 0x0F0F0F0F0F0F0F0F) << 4);

i = ((i >> 8) & 0x00FF00FF00FF00FF) | ((i & 0x00FF00FF00FF00FF) << 8);

i = ((i >> 16) & 0x0000FFFF0000FFFF) | ((i & 0x0000FFFF0000FFFF) << 16);

i = ( i >> 32 ) | ( i << 32);

return i >> (64 - bits);

}