Shifting the sign bit in .NET

Question

I'm reading bits from a monochrome bitmap. I'm storing every 16 bits in a short in the reverse order. If the bit in the bitmap is black, store a 1. If white, store a 0.

E.g.: for bitmap: bbbw bbbw bbbw wwww
my short is: 0000 0111 0111 0111

The 1st way I tried to do this was:

short m;
// ...
Color c = bmp.GetPixel(j, i);
if (c.R == Color.Black)
    m |= short.MinValue;
m >>= 1;
// ...

After one assignment and shift, I got the expected -32768 (1000 0000 0000 0000).
After the 2nd time I got -16384 (1100 0000 0000 0000).

I changed my code to use ushort and changed the if line to s |= (ushort)Math.Pow(2, 15); and now it works.

My question is: why will the sign bit not shift in .NET? Is there a way to shift the sign bit?

Answer 1

Right shifting signed integers in C# fills the left bits with the sign bit. Effectively, the result of right shifting a signed integer by a single bit is equivalent to dividing it by 2.

You can find this kind of right shifting in other places too. For example, x86 assembly provides two distinct instructions, sar (which fills the left bits with sign bit) and shr (which fills left bits with zero).

If you don't want this behavior in C#, you'll have to use unsigned types when shifting.

Answer 2

The short answer to your question, as you found out is to use unsigned integer to avoid bringing in the sign bit, and that's all fine. However do consider the following

Optimization hint

Assuming that you have to do a lot of such conversions (typically there are a lot of pixels in a bitmap), you should consider using an array of 256 bytes which would provide directly the reversed version of the bit pattern (or whatever the conversion may be) for one complete byte. Then by directly indexing this array, with either the hi or low byte value of the 16 bits word, you get the results for all of 8 bits. In some cases where time/performance is at a premium (and space is available...) you can even use a 64k array size, processing one full word at a time.

Given the conversion specified in your example, you'd have the pre-calculated values array be something like:

    byte[] mirror = { 
       0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
       0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
       0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x78, 0xF8,
       // etc..
       0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
    };

Answer 3

http://msdn.microsoft.com/en-us/library/k2ay192e.aspx

"The >> operator shifts the bits of expression1 right by the number of bits specified in expression2. The sign bit of expression1 is used to fill the digits from the left. Digits shifted off to the right are discarded. The data type of expression1 determines the data type returned by this operator."

Answer 4

per http://www.blackwasp.co.uk/CSharpShiftOperators.aspx

...signed integers use the highest order bit to determine if the value of a variable is positive or negative and that the remaining bits use two's complement notation for negative values The highest order bit would normally be considered as the overflow bit for a shift left operation. To allow for this, C# understands that this bit should not be adjusted for signed data types and that negative numbers should be shifted accordingly. Thus shifting works for negative values as well as positive ones.

int value = -240;
int halved = value >> 1;      // Result = -120