Code Optimization

Interesting things in software development and code optimization

Bit manipulations

Hi,

Today, I will explain bit manipulations. As you know each bit set in its own position from 0 to 7.

As an example, Lets use the following byte 00000010 which is 0x02 in hex-decimal and 2 in decimal.

It has "1" at 1st place (lets count it from zero place to 7 place).


So shifting bits to the left will move all bits to the left:

00000010 << 2 = 00001000

As you see now 1 on the 3rd place, instead of 1st place, because of we have shifted all bits to the left 2 times. Same rule is for the right shifting.


Another type of bit manipulation is boolean operations like XOR, OR and AND.

OR just sets 1 on its place:

0010 OR 0001 = 0011
0010 OR 0010 = 0010


XOR makes the same as OR and inverts bits at the same places if they both equal to 1  (outputs 1 only when both bits differ):

0010 XOR 0001 = 0011
0010 XOR 0010 = 0000


AND leaves bits that equal to 1 at the same place only:

0010 AND 0001 = 0000
0010 AND 0010 = 0010


Ha, seems nothing too hard, doesn't? :)


You may ask - why do we need it? I will explain and show an example where and how to use it.
Lets imagine that you work with bitmaps in C#, do you want it to be really fast? I'm guess yes for sure. So lets figure out how to make it very fast.
As I said, graphic memory and images itself can be RGB and RGBA (in most general cases), and we will work with RGBA as it has transparent component with is called Alpha. So RGBA is just a group of 4 bytes, do you remember what type is represented by 4 bytes in C#? Yes, it is Int32. So we are going to use Int32 to work with our images. And here is how:

Rectangle rect = new Rectangle(0, 0, tmpi.Width, tmpi.Height);

BitmapData bmpd = tmpi.LockBits(rect, ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb);

Int32[] src = new Int32[bmpd.Stride / 4 * tmpi.Height];

System.Runtime.InteropServices.Marshal.Copy(bmpd.Scan0, src, 0, src.Length);

Do you think I'm crazy? :)
No, because of reading and writing 4 bytes instead of 1 byte is much faster, thus I do not use byte[].
But now we need to split Int32 onto RGBA and here is how we will do it:

public void SetPointAsIs(byte r, byte g, byte b, byte a, int x, int y)

{

src[Stride * Y + x] = (a << 24) + (r << 16) + (g << 8) + b;

}

public ColorBgra GetPoint(int x, int y)

{

Int32 argb = src[Stride * y + x];

ColorBgra c = new ColorBgra();

c.A = (byte)(argb >> 24);

c.R = (byte)(argb >> 16 & 0xff);

c.G = (byte)(argb >> 8 & 0xff);

c.B = (byte)(argb & 0xff);

return c;

}

This code will compiled into command like MOV ds:[edx + offset], 0x11223344, instead of four MOV op-codes that will move each byte separately.



Thank you, and see you next time :)

1vqHSTrq1GEoEF7QsL8dhmJfRMDVxhv2y