[RESOLVED] Reverse bit order of byte

[Frozen001]

So as I contiure my project, I have now realized thay I need to reverse the order of the bytes that are being sent out a com port. For example:

I build a Byte Array that contains for example:

B5, 65, 32, 0A, 0A, 60


I need this to be:

AD, A6, 4C, 50, 50, 06

Is there a simple command to do this?

[jmcilhinney]

Can you elaborate on why you believe you need to do this? It might be perfectly legitimate, or it might not. If it is, the exact why might dictate the exact how.

[Frozen001]

Can you elaborate on why you believe you need to do this? It might be perfectly legitimate, or it might not. If it is, the exact why might dictate the exact how.

The device I am communicating in is dictating the order of the bits which is opposite of what I originally wrote my code for. If there is a simple way to just flip the bit order I would not have to re-do my code.

The original documentation on the device outlined the frames, and I had assumed when builfin the bytes it was MSB first, but after some testing, and further digging into the documentation, it appears to be LSB first.

[Poppa Mintin]

Hi Frozen...

I've been trying all afternoon to convert your reversed binary number back to a hex' number !
Converting a decimal number to binary is simple:

       BinValue = Convert.ToString(DecValue, 2)

Reversing the result is a fairly simple function:

    Private Function GetBinary(ByVal decValue As Int32) As String
        Dim binNum As String = Convert.ToString(decValue, 2)
        Dim answer As String = ""
        For i = binNum.Length - 1 To 0 Step -1
            answer &= binNum.Chars(i)
        Next
        Return answer
    End Function

In reality I've been trying to convert any binary number to anything other than a string.


Poppa.

[Shaggy Hiker]

It's an interesting problem. My second thought was to do this:

Public function ReverseByte (inByte as Byte) As Byte
 Dim ret as Byte
 
 for x=0 to 7
  ret = ret Or ((inByte >> x And 1)
 Next

 Return ret
End Function

That's freehand, so there may well be errors.

[paulg4ije]

Crude, but it works:

    Private Function bitReverse(iNum As Integer) As Integer

        Dim iResult As Integer

        If (iNum And 128) = 128 Then iResult += 1
        If (iNum And 64) = 64 Then iResult += 2
        If (iNum And 32) = 32 Then iResult += 4
        If (iNum And 16) = 16 Then iResult += 8
        If (iNum And 8) = 8 Then iResult += 16
        If (iNum And 4) = 4 Then iResult += 32
        If (iNum And 2) = 2 Then iResult += 64
        If (iNum And 1) = 1 Then iResult += 128

        Return iResult

    End Function

[paulg4ije]

Shaggy's is much neater ;-)

[dbasnett]

A hack I found somewhen, somewhere

    Public Function RevByte(byt As Byte) As Byte
        Dim b As Integer = byt
        b = (b And &HF0) >> 4 Or (b And &HF) << 4
        b = (b And &HCC) >> 2 Or (b And &H33) << 2
        b = (b And &HAA) >> 1 Or (b And &H55) << 1
        Return CByte(b And &HFF)
    End Function

Test with

        For x As Integer = 0 To 255
            Dim byt As Byte = CByte(x)
            Debug.Write(Convert.ToString(byt, 2).PadLeft(8, "0"c))
            Debug.Write(" ")
            byt = RevByte(byt)
            Debug.WriteLine(Convert.ToString(byt, 2).PadLeft(8, "0"c))
        Next

edit: IF speed is an issue then use a table lookup.

[Frozen001]

db

I found the same hack you found after I posted. :

    Private Function ReverseBits(x As Byte) As Byte
        x = (((x And &HAA) >> 1) Or ((x And &H55) << 1))
        x = (((x And &HCC) >> 2) Or ((x And &H33) << 2))
        x = (((x And &HF0) >> 4) Or ((x And &HF) << 4))
        Return ((x))

    End Function

[Frozen001]

dupe

[Shaggy Hiker]

While messier, that should be slightly faster than mine. I have 8 And, 8 Or, and 8 bit shifts. That has 6 And, 6 bit shifts, and three Or. It also has no loop, whereas I do, but you could unroll the loop to dispense with that.

[dbasnett]

While messier, that should be slightly faster than mine. I have 8 And, 8 Or, and 8 bit shifts. That has 6 And, 6 bit shifts, and three Or. It also has no loop, whereas I do, but you could unroll the loop to dispense with that.

I think I'd use a table if there were many of these.

        Dim tbl() As Byte = {0, 128, 64, 192, 32, 160, 96, 224,
                                16, 144, 80, 208, 48, 176, 112, 240,
                                8, 136, 72, 200, 40, 168, 104, 232,
                                24, 152, 88, 216, 56, 184, 120, 248,
                                4, 132, 68, 196, 36, 164, 100, 228,
                                20, 148, 84, 212, 52, 180, 116, 244,
                                12, 140, 76, 204, 44, 172, 108, 236,
                                28, 156, 92, 220, 60, 188, 124, 252,
                                2, 130, 66, 194, 34, 162, 98, 226,
                                18, 146, 82, 210, 50, 178, 114, 242,
                                10, 138, 74, 202, 42, 170, 106, 234,
                                26, 154, 90, 218, 58, 186, 122, 250,
                                6, 134, 70, 198, 38, 166, 102, 230,
                                22, 150, 86, 214, 54, 182, 118, 246,
                                14, 142, 78, 206, 46, 174, 110, 238,
                                30, 158, 94, 222, 62, 190, 126, 254,
                                1, 129, 65, 193, 33, 161, 97, 225,
                                17, 145, 81, 209, 49, 177, 113, 241,
                                9, 137, 73, 201, 41, 169, 105, 233,
                                25, 153, 89, 217, 57, 185, 121, 249,
                                5, 133, 69, 197, 37, 165, 101, 229,
                                21, 149, 85, 213, 53, 181, 117, 245,
                                13, 141, 77, 205, 45, 173, 109, 237,
                                29, 157, 93, 221, 61, 189, 125, 253,
                                3, 131, 67, 195, 35, 163, 99, 227,
                                19, 147, 83, 211, 51, 179, 115, 243,
                                11, 139, 75, 203, 43, 171, 107, 235,
                                27, 155, 91, 219, 59, 187, 123, 251,
                                7, 135, 71, 199, 39, 167, 103, 231,
                                23, 151, 87, 215, 55, 183, 119, 247,
                                15, 143, 79, 207, 47, 175, 111, 239,
                                31, 159, 95, 223, 63, 191, 127, 255}

[Shaggy Hiker]

I'm not sure that I would. While a table lookup is fast, and faster options also exist (a binary search of an ordered set is possible, in this case), the And, Or, and << operators are among the fastest on a CPU. That function should be so fast that it would zip through thousands of bytes in a millisecond on modern computers.

[Poppa Mintin]

Looks like you've got plenty of answers...

I'm going to add my pennyworth anyway; several hours later than intended... SWMBO had dinner ready and then we need my lappy to watch TV. (Sorry)

Ok, so I figured that you don't actually need to reverse the binary string, just add it up backwards. This is the code I used to test with, it had a 'Test' Button, four Labels and a TextBox to input test values.

    Private Sub Button2_Click() Handles Button2.Click
        Dim hexVal, sum, bit As Int32, binStrg, hexStrg As String

        sum = 0 : bit = 1
        hexStrg = TextBox1.Text.ToUpper.Trim
        hexVal = "&H" & hexStrg
        binStrg = Convert.ToString(hexVal, 2)
        Label1.Text = hexStrg
        Label2.Text = binStrg
        For i = 0 To binStrg.Length - 1
            If binStrg.Chars(i) = "1" Then sum += bit
            bit += bit
        Next
        Label3.Text = sum.ToString
        Label4.Text = Hex(sum).ToString
        TextBox1.Text = ""
        TextBox1.Select()
    End Sub

That worked ok, so then all I had to do was turn it into a function.

    Private Function ReverseHex(ByVal hexStr As String) As String
        Dim hexVal, sum, bit As Int32, binStr As String

        sum = 0 : bit = 1                            'Set initial values.
        hexStr = hexStr.ToUpper.Trim                 'Ensure we're in upper case without extra spaces.
        hexVal = "&H" & hexStr                       'Convert raw hex string into a hex value.
        binStr = Convert.ToString(hexVal, 2)         'Convert the hex value into a binary string.
        For i = 0 To binStr.Length - 1               'Add up all the '1' bits BACKWARDS.
            If binStr.Chars(i) = "1" Then sum += bit
            bit += bit                               'Double the value of the next bit.
        Next
        Return Hex(sum).ToString                     'Convert the integer sum back to a Hex string,
                                                     'and return it.
    End Function

Poppa.


PS
Oh dear... Didn't test with hex values without 'A' to 'F' ! hex inputs of only numerals or which start with a numeral don't work !
Back to the drawing board.

Pop.

[Poppa Mintin]

PS
Oh dear... Didn't test with hex values without 'A' to 'F' ! hex inputs of only numerals or which start with a numeral don't work !
Back to the drawing board.

Pop.

Just to correct the error.
I had to 'fudge' the method a little to take care of that oversight:

    Private Function ReverseHex(ByVal hexStr As String) As String
        Dim adj, bit, hexVal, sum As Int32, binStr As String

        sum = 0 : bit = 1                            'Set initial values.
        hexStr = hexStr.ToUpper.Trim                 'Ensure we're in upper case without extra spaces.
        hexVal = "&H" & hexStr                       'Convert raw hex string into a hex value.
        binStr = Convert.ToString(hexVal, 2)         'Convert the hex value into a binary string.
        adj = binStr.Length                          'Adjust for binary strings less than 8 bits.
        While adj < 8 : bit += bit : adj += 1 : End While
        For i = 1 To binStr.Length                   'Add up all the '1' bits BACKWARDS.
            If binStr.Chars(i - 1) = "1" Then sum += bit
            bit += bit                               'Double the value of the next bit.
        Next
        hexStr = Hex(sum).ToString                   'Convert the integer sum back to a Hex string,
        If hexStr.Length < 2 Then hexStr = "0" & hexStr
        Return hexStr                                'Return the Hex string.
    End Function

Probably not as neat as your current algorithm, and definitely not as neat as I originally thought, and I've no idea about speed, but at least it works. (I hope!)


Poppa.

[dbasnett]

I'm not sure that I would. While a table lookup is fast, and faster options also exist (a binary search of an ordered set is possible, in this case), the And, Or, and << operators are among the fastest on a CPU. That function should be so fast that it would zip through thousands of bytes in a millisecond on modern computers.

In general I agree. The OP will know or find out if the speed of reversing needs improvement.

[passel]

I'm not sure that I would. While a table lookup is fast, and faster options also exist (a binary search of an ordered set is possible, in this case), the And, Or, and << operators are among the fastest on a CPU. That function should be so fast that it would zip through thousands of bytes in a millisecond on modern computers.

I guess technically, I don't agree.
Both of your solutions ( Frozen001 and S H) involved calling a function and returning a value in addition to the operations to reverse the bits.
So you have the overhead of the function call in addition to the operations.

Also, I don't see how any kind of search, binary or otherwise, can be faster than just directly accessing a value from an array.

In almost every case I've seen that involved speeding up an operation, if you can just directly return the value from an array (i.e. in this case you're just fetch the reversed value from the array using the source byte (0 to 255) as an index). It will beat any function call and most any result that involves more than a couple of operations.

Of course, we're talking .Net here, and array access may be wrapped by a class access that slows things down over other languages, such as VB6 or C, but I would hope it wouldn't make accessing the elements of an array as slow as doing a function call.

[Shaggy Hiker]

Yeah, I was thinking of something else...something wrong, when I suggested the binary search. A direct array access would be the fastest, but there's a real question of how it was built. As long as DB has already done it...you can't top copy and paste. In practice, though, I'd be inclined to build the array on program startup, at which point you have to question whether or not the performance difference would matter to anybody. After all, that kind of technique can also be applied to random number generators, trig functions, and several other things. That used to be done, but today, the performance gain isn't worth the bother. The same seems likely to be the case here, as well.

[philo]

Works with VB5/6, optimized with some hardwired factorization and the \ operator.

Public Function ReverseByteBits(b As Byte) As Byte
    ReverseByteBits = ((((b And 128) \ 4 + (b And 64)) \ 4 + (b And 32)) \ 4 + (b And 16)) \ 2 + ((((b And 1) * 4 + (b And 2)) * 4 + (b And 4)) * 4 + (b And 8)) * 2
End Function