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:
[code=vbnet]
Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())

'Lets shift byte's columns
Dim worker As New System.Text.Str ingBuilder
Dim bkupArray As Boolean()
ReDim bkupArray(7)

For p As Integer = 0 To buffer.GetUpper Bound(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(b kupArray(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
[/code]

[TRScheel]

This is my current code:
[code=vbnet]
Private Sub ShiftMe(ByVal buffer As Byte(), ByVal shift As Integer())

'Lets shift byte's columns
Dim worker As New System.Text.Str ingBuilder
Dim bkupArray As Boolean()
ReDim bkupArray(7)

For p As Integer = 0 To buffer.GetUpper Bound(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(b kupArray(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
[/code]

Heres how I would have done it:

[CODE=cpp]
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[] integerArrayFro mByte = GetIntegerArray FromByte(buffer );
int[] integerArray = new int[8];

Console.WriteLi ne();
Console.Write(" Byte to Int Array: ");
for (int i = 0; i < integerArrayFro mByte.Length; i++)
{
if (i != integerArrayFro mByte.Length - 1)
{
Console.Write(" {0}-", integerArrayFro mByte[i]);
}
else
{
Console.Write(" {0}", integerArrayFro mByte[i]);
}
}
Console.WriteLi ne();

for (int i = 0; i < integerArray.Le ngth; i++)
{
integerArray[i] = integerArrayFro mByte[shift[i]];
}

Console.WriteLi ne();
Console.WriteLi ne("Bytes Shifted: {0}", GetByteFromInte gerArray(intege rArray));
Console.WriteLi ne();

PressAnyKeyToCo ntinue();
}

private static int[] GetIntegerArray FromByte(byte buffer)
{
List<int> integerArray = new List<int>();
//Console.WriteLi ne("\tCurrent Byte Value: {0}", buffer);

for (int i = 7; i >= 0; i--)
{
if (buffer >= Math.Pow(2, i))
{
integerArray.Ad d(1);
buffer -= (byte)Math.Pow( 2, i);
}
else
{
integerArray.Ad d(0);
}
}

return integerArray.To Array();
}

private static byte GetByteFromInte gerArray(int[] integerArray)
{
byte buffer = 0;

for (int i = 0; i < integerArray.Le ngth; i++)
{
if (integerArray[i] == 1)
{
buffer += (byte)Math.Pow( 2, 7 - i);
}
}

return buffer;
}
[/CODE]

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

[CODE=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 integerArrayFro mByte() As Integer = GetIntegerArray FromByte(buffer )
Dim integerArray(7) As Integer

Console.WriteLi ne()
Console.WriteLi ne("Byte to Int Array: ")
For i As Integer = 0 To integerArrayFro mByte.Length - 1 Step 1
If Not (i = integerArrayFro mByte.Length - 1) Then
Console.Write(" {0}-", integerArrayFro mByte(i))
Else
Console.Write(" {0}", integerArrayFro mByte(i))
End If
Next
Console.WriteLi ne()

For i As Integer = 0 To integerArray.Le ngth - 1 Step 1
integerArray(i) = integerArrayFro mByte(shift(i))
Next

Console.WriteLi ne()
Console.WriteLi ne("Bytes Shifted: {0}", GetByteFromInte gerArray(intege rArray))
Console.WriteLi ne()

PressAnyKeyToCo ntinue()

End Sub

Function GetIntegerArray FromByte(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.Ad d(1)
buffer -= Math.Pow(2, i)
Else
integerArray.Ad d(0)
End If
Next

Return integerArray.To Array()
End Function

Function GetByteFromInte gerArray(ByRef integerArray() As Integer) As Byte
Dim buffer As Byte = 0

For i As Integer = 0 To integerArray.Le ngth - 1 Step 1
If (integerArray(i ) = 1) Then
buffer += Math.Pow(2, 7 - i)
End If
Next

Return buffer
End Function

Sub PressAnyKeyToCo ntinue()
Console.ReadKey (True)
End Sub
[/CODE]


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.

[CODE=vb]
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.WriteLi ne("{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
[/CODE]


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.BITPOST ION v, params X.BITPOSTION[] bpos)
{
X.BITPOSTION d = X.BITPOSTION.NO NE;
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 = (MyConfigSectio n)Configuration Manager.GetSect ion("myConfig") ;
Console.WriteLi ne("Level: " + s.Level + "<br>");
Console.WriteLi ne("Name: " + s.Name);
while (true)
{
byte ax;
X.BITPOSITION result = X.BITPOSITION.N ONE;
System.Byte.Try Parse(Console.R eadLine(), System.Globaliz ation.NumberSty les.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.WriteLi ne("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:

[CODE=vb]newBuffer = newBuffer Or math.pow(2,shif t(7-1))[/CODE]

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:

[CODE=vb]
For k As Integer = 0 To buffer.GetUpper Bound(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
[/CODE]

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:

[CODE=vb]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.GetUpper Bound(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[/CODE]

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.