Manipulating bits

[thiago777]

What is the best way to manipulate bits in a byte?
I got to a situation where I need to organize the bit's order of a byte in a big loop (I mean it), so I say "best" in every aspect, including performance.
The less convertion instructions and more cpu native ones, the better.

Let me be more specific:

I have a shift Integer() array that contains an order. Also, a buffer() byte array.

For example:

Dim shift as Integer() {2,1,0,7,5,4,6,3}
dim buffer as Byte() 'variable with data

in the case above and with a byte like 10010111, the byte should be transformed into 00110011.

take a look:

------------------------
From: 10010111
To : 00110011
------------------------

following the shift "index" order.

This seems a simple problem but the performance here is really critical. It would be great if we could do this only with Xor sort of instructions (since its low level)
Any suggestions?

[Plater]

What do you mean organize bits?
If I have byte 0xA5 then the bits are 10100101, what do you wish to do to those bits?

[thiago777]

Exactly, organize them.. I edited the 1st post. Please take a look.

I made it once concatenating strings of 1's to a StringBuilder but the performance was horrible, takes like 2 minutes to finish the loop..
cant think of any logic, if you have any ideas..

thank you!

[thiago777]

What do you mean organize bits?
If I have byte 0xA5 then the bits are 10100101, what do you wish to do to those bits?

This is my current code:

Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())
 
      'Lets shift byte's columns
      Dim worker As New System.Text.StringBuilder
      Dim bkupArray As Boolean()
      ReDim bkupArray(7)
 
      For p As Integer = 0 To buffer.GetUpperBound(0)
 
         'Separate each bit of byte
         bkupArray(0) = buffer(p) And 1
         bkupArray(1) = (buffer(p) And 2) >> 1
         bkupArray(2) = (buffer(p) And 4) >> 2
         bkupArray(3) = (buffer(p) And 8) >> 3
         bkupArray(4) = (buffer(p) And 16) >> 4
         bkupArray(5) = (buffer(p) And 32) >> 5
         bkupArray(6) = (buffer(p) And 64) >> 6
         bkupArray(7) = (buffer(p) And 128) >> 7
 
         'Create Shifted byte
         buffer(p) = 0 'clean old byte
         worker.Remove(0, worker.Length)
         worker.Append(bkupArray(shift(7)) & bkupArray(shift(6)) & bkupArray(shift(5)) & bkupArray(shift(4)) & bkupArray(shift(3)) & bkupArray(shift(2)) & bkupArray(shift(1)) & bkupArray(shift(0)))
 
         buffer(p) = StrToByteArray(worker.ToString)
      Next
 
 
   End Sub
 

[TRScheel]

This is my current code:

Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())
 
      'Lets shift byte's columns
      Dim worker As New System.Text.StringBuilder
      Dim bkupArray As Boolean()
      ReDim bkupArray(7)
 
      For p As Integer = 0 To buffer.GetUpperBound(0)
 
         'Separate each bit of byte
         bkupArray(0) = buffer(p) And 1
         bkupArray(1) = (buffer(p) And 2) >> 1
         bkupArray(2) = (buffer(p) And 4) >> 2
         bkupArray(3) = (buffer(p) And 8) >> 3
         bkupArray(4) = (buffer(p) And 16) >> 4
         bkupArray(5) = (buffer(p) And 32) >> 5
         bkupArray(6) = (buffer(p) And 64) >> 6
         bkupArray(7) = (buffer(p) And 128) >> 7
 
         'Create Shifted byte
         buffer(p) = 0 'clean old byte
         worker.Remove(0, worker.Length)
         worker.Append(bkupArray(shift(7)) & bkupArray(shift(6)) & bkupArray(shift(5)) & bkupArray(shift(4)) & bkupArray(shift(3)) & bkupArray(shift(2)) & bkupArray(shift(1)) & bkupArray(shift(0)))
 
         buffer(p) = StrToByteArray(worker.ToString)
      Next
 
 
   End Sub
 

Heres how I would have done it:

private static void ByteShifting()
{
    //00001010 = 10
    //10000000 = 128
 
    int[] shift = new int[] { 2, 1, 0, 7, 5, 4, 6, 3 };
    byte buffer = new byte();
    buffer = 10;
    int[] integerArrayFromByte = GetIntegerArrayFromByte(buffer);
    int[] integerArray = new int[8];
 
    Console.WriteLine();
    Console.Write("Byte to Int Array: ");
    for (int i = 0; i < integerArrayFromByte.Length; i++)
    {
        if (i != integerArrayFromByte.Length - 1)
        {
            Console.Write("{0}-", integerArrayFromByte[i]);
        }
        else
        {
            Console.Write("{0}", integerArrayFromByte[i]);
        }
    }
    Console.WriteLine();
 
    for (int i = 0; i < integerArray.Length; i++)
    {
        integerArray[i] = integerArrayFromByte[shift[i]];
    }
 
    Console.WriteLine();
    Console.WriteLine("Bytes Shifted: {0}", GetByteFromIntegerArray(integerArray));
    Console.WriteLine();
 
    PressAnyKeyToContinue();
}
 
private static int[] GetIntegerArrayFromByte(byte buffer)
{
    List<int> integerArray = new List<int>();
    //Console.WriteLine("\tCurrent Byte Value: {0}", buffer);
 
    for (int i = 7; i >= 0; i--)
    {
        if (buffer >= Math.Pow(2, i))
        {
            integerArray.Add(1);
            buffer -= (byte)Math.Pow(2, i);
        }
        else
        {
            integerArray.Add(0);
        }
    }
 
    return integerArray.ToArray();
}
 
private static byte GetByteFromIntegerArray(int[] integerArray)
{
    byte buffer = 0;
 
    for (int i = 0; i < integerArray.Length; i++)
    {
        if (integerArray[i] == 1)
        {
            buffer += (byte)Math.Pow(2, 7 - i);
        }
    }
 
    return buffer;
}
 

Didnt realize you did it in VB, be back in a few with the VB version of it...

[thiago777]

Thanks a lot, I will try that code.. but would be better if was in vb ;)

[Plater]

So you want to shove the 1s to the right on each half byte?
hmm very strange thing to desire. Can I ask why you need this? Seems like a waste?

I been trying for awhile and best I got was:

private void bitshove(byte b)
{
   int n = 0;
   if ((b & 0x01) == 0x01)
   {
       n++;
   }
   if ((b & 0x02) == 0x02)
   {
       n++;
   }
   if ((b & 0x04) == 0x04)
   {
       n++;
   }
   if ((b & 0x08) == 0x08)
   {
       n++;
   }
   //now n= number of 1s in the half byte
}
 

[TRScheel]

Thanks a lot, I will try that code.. but would be better if was in vb ;)

Here it is in VB

    Sub Main()
 
        '00001010 = 10
        '10000000 = 128
 
        Dim shift() As Integer = {2, 1, 0, 7, 5, 4, 6, 3}
        Dim buffer As Byte = 10
        Dim integerArrayFromByte() As Integer = GetIntegerArrayFromByte(buffer)
        Dim integerArray(7) As Integer
 
        Console.WriteLine()
        Console.WriteLine("Byte to Int Array: ")
        For i As Integer = 0 To integerArrayFromByte.Length - 1 Step 1
            If Not (i = integerArrayFromByte.Length - 1) Then
                Console.Write("{0}-", integerArrayFromByte(i))
            Else
                Console.Write("{0}", integerArrayFromByte(i))
            End If
        Next
        Console.WriteLine()
 
        For i As Integer = 0 To integerArray.Length - 1 Step 1
            integerArray(i) = integerArrayFromByte(shift(i))
        Next
 
        Console.WriteLine()
        Console.WriteLine("Bytes Shifted: {0}", GetByteFromIntegerArray(integerArray))
        Console.WriteLine()
 
        PressAnyKeyToContinue()
 
    End Sub
 
    Function GetIntegerArrayFromByte(ByVal buffer As Byte) As Integer()
 
        Dim integerArray As List(Of Integer) = New List(Of Integer)()
 
        For i As Integer = 7 To 0 Step -1
            If (buffer >= Math.Pow(2, i)) Then
                integerArray.Add(1)
                buffer -= Math.Pow(2, i)
            Else
                integerArray.Add(0)
            End If
        Next
 
        Return integerArray.ToArray()
    End Function
 
    Function GetByteFromIntegerArray(ByRef integerArray() As Integer) As Byte
        Dim buffer As Byte = 0
 
        For i As Integer = 0 To integerArray.Length - 1 Step 1
            If (integerArray(i) = 1) Then
                buffer += Math.Pow(2, 7 - i)
            End If
        Next
 
        Return buffer
    End Function
 
    Sub PressAnyKeyToContinue()
        Console.ReadKey(True)
    End Sub
 

As an aside...

This code is dirty as all hell. For one, it needs to have checks for the right size arrays being sent eveywhere. It checks no where for nulls (nothing in vb).

In addition, i would be my bottom dollar there's an easier way to grab the 1's and 0's outta a byte, but I couldnt figure it out in the 10 or so minutes that i wanted to spend on this, so you have those functions there.

Some final notes, the functions could use better names, and there is probably a way to do it without the Math.Pow as well. This WILL work faster then your string parse though.

[thiago777]

So you want to shove the 1s to the right on each half byte?
hmm very strange thing to desire. Can I ask why you need this? Seems like a waste?

I been trying for awhile and best I got was:

private void bitshove(byte b)
{
   int n = 0;
   if ((b & 0x01) == 0x01)
   {
       n++;
   }
   if ((b & 0x02) == 0x02)
   {
       n++;
   }
   if ((b & 0x04) == 0x04)
   {
       n++;
   }
   if ((b & 0x08) == 0x08)
   {
       n++;
   }
   //now n= number of 1s in the half byte
}
 

No, not like this. They must be ordered according to the variable "shift".

if I say the shift is ( 0 , 1 , 2 ,3 , 4 ,5 ,6 ,7)
and the byte is 10101010
then I would get the same 10101010

and when the order for example is ( 0 , 2 , 1 ,3 , 4 ,5 ,6 ,7 )
then the byte 10101010
would turn to be 11001010

(note that the second and third bit switched)

I think TRSCheel got the idea, Im trying to convert his code to VB and test the result. As soon as I have it I post it here.

[thiago777]

ok, you were faster than me :)
I try and tell you how your code's performance came out here..
thanks a lot
Thiago.

[TRScheel]

So you want to shove the 1s to the right on each half byte?
hmm very strange thing to desire. Can I ask why you need this? Seems like a waste?

I been trying for awhile and best I got was:

private void bitshove(byte b)
{
   int n = 0;
   if ((b & 0x01) == 0x01)
   {
       n++;
   }
   if ((b & 0x02) == 0x02)
   {
       n++;
   }
   if ((b & 0x04) == 0x04)
   {
       n++;
   }
   if ((b & 0x08) == 0x08)
   {
       n++;
   }
   //now n= number of 1s in the half byte
}
 

I am curious... trying to follow this logic, this does this right:

you test a byte against a byte with only the first bit as 1, and if they return exactly the same as the byte with only the first bit as 1, then the original byte has a 1, then continue... etc?

Because if so, then my code could be cleaned up quite a bit...


Hence...

0001001 & 00000001 = 00000001
0001001 & 00000010 = 00000000
0001001 & 00000100 = 00000000
0001001 & 00001000 = 00001000

correct?

[TRScheel]

ok, you were faster than me :)
I try and tell you how your code's performance came out here..
thanks a lot
Thiago.

Here, this will be faster:

And I think I have an order problem in the earlier ones, I ordered the bits backwards.

    Sub Main()
        Dim shift(8) As Integer
        Dim buffer As Byte
        Dim newBuffer As Byte
 
        shift = New Integer() {2, 1, 0, 7, 5, 4, 6, 3}
        buffer = 10
 
        newBuffer = ReArrangeBytes(buffer, shift)
 
        Console.WriteLine("{0}", newBuffer)
        Console.ReadKey(True)
    End Sub
 
    Function ReArrangeBytes(ByVal buffer As Byte, ByVal shift() As Integer) As Byte
 
        Dim result As Byte = 0
 
        For i As Integer = 0 To 7 Step 1
            Dim ToTest As Byte = Math.Pow(2, i)
            If ((buffer And ToTest) = ToTest) Then
                result += Math.Pow(2, shift(7 - i))
            End If
        Next
 
        Return result
    End Function
 

To Plater:

Didnt know that about the bytes. I remember learning something about it, but I dismissed it... probably shouldnt have, heh. Never really liked bytes

[oohay251]

here's a c# sample that doesn't make function calls to assign the positions.
If you pass an array of bit flags 0x01, 0x02, 0x04 , etc. to represent your re-ordering instead of ordinal positions 1 to 8....

public static class X
{
[Flags]
public enum BITPOSTION :byte { NONE=0, P1 = 0x01, P2 = 0x02, P3 = 0x04, P4 = 0x08, P5 = 0x10, P6 = 0x20, P7 = 0x40, P8 = 0x80 }
public static X.BITPOSTION shift(X.BITPOSTION v, params X.BITPOSTION[] bpos)
{
X.BITPOSTION d = X.BITPOSTION.NONE;
if ((v & X.BITPOSTION.P1) == X.BITPOSTION.P1) d |= bpos[0];
if ((v & X.BITPOSTION.P2) == X.BITPOSTION.P2) d |= bpos[1];
if ((v & X.BITPOSTION.P3) == X.BITPOSTION.P3) d |= bpos[2];
if ((v & X.BITPOSTION.P4) == X.BITPOSTION.P4) d |= bpos[3];
if ((v & X.BITPOSTION.P5) == X.BITPOSTION.P5) d |= bpos[4];
if ((v & X.BITPOSTION.P6) == X.BITPOSTION.P6) d |= bpos[5];
if ((v & X.BITPOSTION.P7) == X.BITPOSTION.P7) d |= bpos[6];
if ((v & X.BITPOSTION.P8) == X.BITPOSTION.P8) d |= bpos[7];
return d;
}
}
static class Program
{
public static void Main(string[] args)
{
MyConfigSection s = (MyConfigSection)ConfigurationManager.GetSection(" myConfig");
Console.WriteLine("Level: " + s.Level + "<br>");
Console.WriteLine("Name: " + s.Name);
while (true)
{
byte ax;
X.BITPOSITION result = X.BITPOSITION.NONE;
System.Byte.TryParse(Console.ReadLine(), System.Globalization.NumberStyles.HexNumber, null,out ax);
//This is a sample of how I want to re-order my bits
X.BITPOSTION[] av = { X.BITPOSTION.P2, X.BITPOSTION.P4, X.BITPOSTION.P7, X.BITPOSTION.P1, X.BITPOSTION.P3, X.BITPOSTION.P5, X.BITPOSTION.P8, X.BITPOSTION.P6 };
result = X.shift(ax, av);
Console.WriteLine("From {0:X}({1}) to {2:X}({3}) ", ax, ax, result, result.ToString());
}
return;
}
}

[thiago777]

Hey,
thanks everyone who helped me out of this problem that seemed so simple. Specially TRScheel who brought up the idea of using the Math.pow that is the core of all this I think.

Though, there is 2 little problems with the code you gave, first the corrrect operation to "add" the bits desired should be OR instead of +.

Second, the bits order are still reversed, that is because the pow(shift(7-i)) returns the positioning of the bit in Integer, causing it to be put in the left to right order, the opposite of our analisys that happens from right to left.

For example, when shift(7-i) (in the most inner loop) returns 6, that means it sould be in ( X, X ,X ,X ,X ,this, X, X) position, but 6 actually adds 100000 to the new byte, because pow(2,6) = 100000 (Note the reversed order).

in here:

newBuffer = newBuffer Or math.pow(2,shift(7-1))

and it doesnt help if you reverse the loop from 7 to 0, step -1 because that will just change the order we analyse the bits, therefore not affecting the final result.

The following is the code with the first problem fixed, but with the reversed order problem:

 For k As Integer = 0 To buffer.GetUpperBound(0)
 
         newBuffer = 0
 
         For i As Integer = 0 To 7
 
            If ((buffer(k) And Math.Pow(2, i)) > 0) Then
 
               newBuffer = newBuffer Or pos(7 - i)
 
            End If
         Next
 
         buffer(k) = newBuffer
 
      Next
 

Note: I put the buffer array in another loop, just to show the operation being processed with many bytes, but you can take that off for better clarity.

Actually I found a way around to this second problem, but I wont give the code for a while as a challange so that we can compare the solutions and check what was the best one. If no one post anything, then I post the solution I found ;)

Later,
Thiago.

PS.: oohay251, as soon as I can test your code I put the results here..tnks

[thiago777]

Ok,

here is the complete code following TRScheel's logic with the pow:

Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())
 
Dim result As Byte = 0
      Dim newBuffer As Byte
 
      'convert shift values integer>binary - for positioning
      Dim pos As Byte()
      ReDim pos(7)
      For m As Integer = 0 To 7
         If (shift(m) = 7) Then
            pos(m) = 1
         ElseIf (shift(m) = 6) Then
            pos(m) = 2
         ElseIf (shift(m) = 5) Then
            pos(m) = 4
         ElseIf (shift(m) = 4) Then
            pos(m) = 8
         ElseIf (shift(m) = 3) Then
            pos(m) = 16
         ElseIf (shift(m) = 2) Then
            pos(m) = 32
         ElseIf (shift(m) = 1) Then
            pos(m) = 64
         ElseIf (shift(m) = 0) Then
            pos(m) = 128
         End If
      Next
 
      For k As Integer = 0 To buffer.GetUpperBound(0)
         newBuffer = 0
         For i As Integer = 0 To 7
            If ((buffer(k) And Math.Pow(2, i)) > 0) Then
               newBuffer = newBuffer Or pos(7 - i)
            End If
         Next
         buffer(k) = newBuffer
      Next
End Sub

while the code is very small I had for some reason a horrible performance with this. I made the test with a 30MB buffer and compared the time.

With the StringBuilder's code the cpu took 1' 30 seconds to finish the loop, while with the pow it took 2' 20 seconds! almost the double of time.

Any other ideas for this? maybe with the StringBuilder's logic is the best as I can get?

Note that I dont use normal string in the first example, because normal's string concatenation and operations actually creates a new string every operation. But StringBuilder is just one object optimized to be changed very often without re-creating itself like a normal string.

[oohay251]

your performance is going to remain terrible as long as your making function calls for every bit position.

To test performance times, I personally would try using C or C++ to create an inline assembly routine and compile it to a library I could reference.

Also, if it fell in line with your needs, I would try re-ordering buffers of bytes at a time rather than one byte per function call.

[TRScheel]

Ok,

here is the complete code following TRScheel's logic with the pow:

Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())
 
Dim result As Byte = 0
      Dim newBuffer As Byte
 
      'convert shift values integer>binary - for positioning
      Dim pos As Byte()
      ReDim pos(7)
      For m As Integer = 0 To 7
         If (shift(m) = 7) Then
            pos(m) = 1
         ElseIf (shift(m) = 6) Then
            pos(m) = 2
         ElseIf (shift(m) = 5) Then
            pos(m) = 4
         ElseIf (shift(m) = 4) Then
            pos(m) = 8
         ElseIf (shift(m) = 3) Then
            pos(m) = 16
         ElseIf (shift(m) = 2) Then
            pos(m) = 32
         ElseIf (shift(m) = 1) Then
            pos(m) = 64
         ElseIf (shift(m) = 0) Then
            pos(m) = 128
         End If
      Next
 
      For k As Integer = 0 To buffer.GetUpperBound(0)
         newBuffer = 0
         For i As Integer = 0 To 7
            If ((buffer(k) And Math.Pow(2, i)) > 0) Then
               newBuffer = newBuffer Or pos(7 - i)
            End If
         Next
         buffer(k) = newBuffer
      Next
End Sub

while the code is very small I had for some reason a horrible performance with this. I made the test with a 30MB buffer and compared the time.

With the StringBuilder's code the cpu took 1' 30 seconds to finish the loop, while with the pow it took 2' 20 seconds! almost the double of time.

Any other ideas for this? maybe with the StringBuilder's logic is the best as I can get?

Note that I dont use normal string in the first example, because normal's string concatenation and operations actually creates a new string every operation. But StringBuilder is just one object optimized to be changed very often without re-creating itself like a normal string.

Wow, when I ran it, it took a fraction of a second.

[TRScheel]

Hey,
thanks everyone who helped me out of this problem that seemed so simple. Specially TRScheel who brought up the idea of using the Math.pow that is the core of all this I think.
...

Later,
Thiago.

PS.: oohay251, as soon as I can test your code I put the results here..tnks

I got this

Module Module1
 
    Sub Main()
        Dim shift(8) As Integer
        Dim buffer As Byte
        Dim newBuffer As Byte
        Dim originalTime As Long
 
        shift = New Integer() {2, 1, 0, 7, 5, 4, 6, 3}
        buffer = 10
        Console.WriteLine("{0} = {1}", GetBytes(buffer), buffer)
 
        originalTime = DateTime.Now.Ticks
        newBuffer = ReArrangeBytes(buffer, shift)
        Console.WriteLine("Elapsed Time: {0}", DateTime.Now.Ticks - originalTime)
 
        Console.WriteLine("{0} = {1}", GetBytes(newBuffer), newBuffer)
        Console.ReadKey(True)
    End Sub
 
    Function ReArrangeBytes(ByVal buffer As Byte, ByVal shift() As Integer) As Byte
        Dim result As Byte = 0
 
        For i As Integer = 0 To 7 Step 1
            Dim ToTest As Byte = Math.Pow(2, 7 - i)
            If ((buffer And ToTest) = ToTest) Then
                result = result Or Math.Pow(2, 7 - shift(i))
            End If
        Next
 
        Return result
    End Function
 
    Function GetBytes(ByVal buffer As Byte) As String
        Dim result As String = String.Empty
 
        For i As Integer = 0 To 7 Step 1
            Dim ToTest As Byte = Math.Pow(2, 7 - i)
            If ((buffer And ToTest) = ToTest) Then
                result += "1"
            Else
                result += "0"
            End If
        Next
 
        Return result
    End Function
 
End Module