Shifting Bits

[pjdenyer]

Hi all, I have a series of bytes and I want to shift them in sequence by 2 bits right.

$00, $00, $3E, $07, $C0, $0F
   -->  -->  -->  -->  -->  --> add new byte if necessary

Any ideas for a quick routine would be appreciated.

[trastikata]

Hi all, I have a series of bytes and I want to shift them in sequence by 2 bits right.

$00, $00, $3E, $07, $C0, $0F
   -->  -->  -->  -->  -->  --> add new byte if necessary

Not sure what exactly are you trying to do. Why add a new byte if it's a right shift?

Do you want to carry over the bits from the following bytes to the previously shifted bytes?

How many bytes do you have to shift?

16-bit or 8-bit compiler?

[Stephen Moss]

First thoughts are that if all the data is in a single Dword variable then I would think all you would need is...

Dword >> 2 for the 2 bit shift right, then once you have shifted by at least 8 bits to add a new byte would be...
Dword.Byte3 = New_Byte to add new data to the high byte of the Dword which should read 0 following the previous shift right operations (If memory serves Right shift, shifts out the LSB, Left shift out the MSB).

However, if that data is held in a Byte array, then there maybe a better way than this but shift data out of array element 0, then once that is empty run a loop that copies the data of each array element into the previous element (1 into the now clear 0, 2 into 1, 3 into 2 and so on).
Once the data in the last element has been shifted then load the New_Byte data into the last element of the array. 

[pjdenyer]

Thanks Stephen, my memory has been jogged, I have used the array method before - a long time ago.

Just to update, the number of bytes varies and if the last byte is say $1F, I would need to add another byte to hold the bits shited right from the previous byte.

[top204]

Below is a clever, but a little inefficient, method of shifting a whole byte array's contents two bit positions to the right. I've just knocked it together and tested it, and it uses two procedures I created that turn a byte array into a form of bit array named: ReadBitArray and WriteBitArray.

You will be able to adapt it so it creates an extra byte to write too in the array, but the code listing below only writes to the array itself, and the last shifts are discarded:

Code Select Expand

'
'   /\\\\\\\\\
'  /\\\///////\\\
'  \/\\\     \/\\\                                                 /\\\          /\\\
'   \/\\\\\\\\\\\/        /\\\\\     /\\\\\\\\\\     /\\\\\\\\   /\\\\\\\\\\\  /\\\\\\\\\\\  /\\\\\\\\\
'    \/\\\//////\\\      /\\\///\\\  \/\\\//////    /\\\/////\\\ \////\\\////  \////\\\////  \////////\\\
'     \/\\\    \//\\\    /\\\  \//\\\ \/\\\\\\\\\\  /\\\\\\\\\\\     \/\\\         \/\\\        /\\\\\\\\\\
'      \/\\\     \//\\\  \//\\\  /\\\  \////////\\\ \//\\///////      \/\\\ /\\     \/\\\ /\\   /\\\/////\\\
'       \/\\\      \//\\\  \///\\\\\/    /\\\\\\\\\\  \//\\\\\\\\\\    \//\\\\\      \//\\\\\   \//\\\\\\\\/\\
'        \///        \///     \/////     \//////////    \//////////      \/////        \/////     \////////\//
'                                  Let's find out together what makes a PIC Tick!
'
' Demonstrate using a byte array as a form of bit array and shifting its contents two bits to the right
' Written for the Positron8 compiler by Les Johnson.
'
    Device = 18F25K20                                       ' Tell the compiler what device to compile for
    Declare Xtal = 16                                       ' Tell the compiler what frequency the device will be operating at (in MHz)
'
' Setup USART1
'
    Declare Hserial1_Baud = 9600                            ' Set the Baud rate to 9600
    Declare HRSOut1_Pin = PORTC.6                           ' Set the TX pin
'
' Create any variables for the demo here
'   
    '
    ' Create the byte array that is to be shifted, and fill it with values
    '
    Dim bSourceArray[10] As Byte Heap = %10100011, %10100011, %10100011, %10100011, %10100011, %10100011, %10100011, %10100011, %10100011, %10100011
    Dim bTempArray[10]   As Byte Heap                       ' Create a temporary byte array to holds the contents of "bSourceArray"
    Dim MyBit    As Bit                                     ' Holds the bit written and read to/from the array
    Dim bBitNum  As Byte                                    ' Holds the bit number within the array
    Dim bIndex   As bBitNum                                 ' Alias to loop for the display of the bits on a serial terminal
    Dim bMaxBits As Byte                                    ' Holds the maximum bits within the byte array, minus 1

'-------------------------------------------------------------------------
' The main program starts here
' Shift the contents of the byte array "bSourceArray" by 2 to the right
' Displays the bits before and after the shifts on a serial terminal
'
Main:      
    HRSOut "Before:"                                        ' \
    For bIndex = 0 To Bound(bSourceArray)                   ' |
        HRSOut Bin8 bSourceArray[bIndex], "|"               ' | Display the original array's contents on a serial terminal
    Next                                                    ' |
    HRSOut 13                                               ' /
'
' Shift the contents of the array: bSourceArray, once to the right
'
    bMaxBits = (SizeOf(bSourceArray) * 8) - 1               ' Calculate the bit size of the byte array holding the values to shift
    For bBitNum = 0 To bMaxBits                             ' Create a loop for the bit numbers
        MyBit = ReadBitArray(bSourceArray, bBitNum)         ' Read a bit from the array
        If bBitNum <= bMaxBits Then                         ' Is it OK to write to the destination array's bit?
            WriteBitArray(bTempArray, bBitNum + 1, MyBit)   ' Yes. So write the bit to the bit position in front
        EndIf
    Next                                                    ' Close the bit counting loop
    bSourceArray = bTempArray                               ' Copy the contents of bTempArray into bSourceArray
'
' Shift the contents of the array: bSourceArray, once to the right again for a final shift of two bit positions
'
   For bBitNum = 0 To bMaxBits                              ' Create a loop for the bit numbers
        MyBit = ReadBitArray(bSourceArray, bBitNum)         ' Read a bit from the array
        If bBitNum <= bMaxBits Then                         ' Is it OK to write to the destination array's bit?
            WriteBitArray(bTempArray, bBitNum + 1, MyBit)   ' Yes. So write the bit to the bit position in front
        EndIf
    Next                                                    ' Close the bit counting loop
    bSourceArray = bTempArray                               ' Copy the contents of bTempArray into bSourceArray
   
    HRSOut "After :"                                        ' \
    For bIndex = 0 To Bound(bSourceArray)                   ' |
        HRSOut Bin8 bSourceArray[bIndex], "|"               ' | Display the shifted array's contents on a serial terminal
    Next                                                    ' |
    HRSOut 13                                               ' /

'-------------------------------------------------------------------------
' Read a bit from a Byte array so it acts as a form of Bit array
' Input     : pArrAddr holds the address of the Byte array holding the bits
'           : pBitNum holds the bit number to read (0 to 255)
' Output    : Returns the state of the bit (1 or 0)
' Notes     : Uses bit shifting for the positioning of the bit to read
'
Proc ReadBitArray(ByRef pArrAddr As wRdFSR1, pBitNum As PP0), Bit
Global Dim wRdFSR1 As FSR1L.Word                            ' Create a global 16-bit SFR of FSR1L\H so it can be used as a parameter
Global Dim PP0     As Byte System                           ' Create a global 8-bit compiler system variable so it can be used as a parameter
    Dim PP0H       As Byte System                           ' Create a compiler system variable
    Dim bBitShift  As PP0H                                  ' Holds the bit shift value

    pArrAddr = pArrAddr + (pBitNum / 8)                     ' Find the element of the array that holds the bit, and move up to it
    bBitShift = pBitNum // 8                                ' Calculate the amount of shifts required for the bit's position within the byte  
    WREG = INDF1                                            ' \
    WREG = WREG << bBitShift                                ' | Return the bit from its position within the array's element
    Result = WREG.7                                         ' /
EndProc

'-------------------------------------------------------------------------
' Write a bit to a Byte array so it acts as a form of Bit array
' Input     : pArrAddr holds the address of the byte array holding the bits
'           : pBitNum holds the bit number to write (0 to 255)
'           : pValue holds the value to write to the bit (1 or 0)
' Output    : None
' Notes     : Uses masking for the bit to write
'
Proc WriteBitArray(ByRef pArrAddr As wWrFSR1, pBitNum As PP0, pValue As Bit)
Global Dim wWrFSR1 As FSR1L.Word                            ' Create a global 16-bit SFR of FSR1L\H so it can be used as a parameter
Global Dim PP0     As Byte System                           ' Create a global 8-bit compiler system variable so it can be used as a parameter
    Dim PP0H       As Byte System                           ' Create a compiler system variable
    Dim bMask      As PP0H                                  ' Holds the bit mask
    Dim bRevMask   As PP0                                   ' Holds the reversed bit mask
    Dim bBits      As Byte                                  ' Holds the loop for the bits reversal
   
    pArrAddr = pArrAddr + (pBitNum / 8)                     ' Find the element of the array that holds the bit, and move up to it
    WREG = pBitNum // 8                                     ' \
    bMask = 1 << WREG                                       ' / Calculate a mask for the bit's position within the byte
    For bBits = 7 DownTo 0                                  ' \
        Ror bMask                                           ' | Reverse the mask, so the bits start at bit-7, and not bit-0 of the array's element
        Rol bRevMask                                        ' |
    Next                                                    ' /
    If pValue = 1 Then                                      ' Is the bit to be set?
        bRevMask = INDF1 | bRevMask                         ' Yes. So "Or" in the bit mask
    Else                                                    ' Otherwise... The bit is to be cleared
        bRevMask = ~bRevMask                                ' So... Complement the mask first
        bRevMask = INDF1 & bRevMask                         ' "And" in the bit mask
    EndIf
    INDF1 = bRevMask                                        ' Write the modified byte to the array's element
EndProc

On the serial terminal, it will display:

Before:10100011|10100011|10100011|10100011|10100011|10100011|10100011|10100011|10100011|10100011|
After :00101000|11101000|11101000|11101000|11101000|11101000|11101000|11101000|11101000|11101000|

[pjdenyer]

Excellent Les.

Thanks

[top204]

Below is a more conventional, and more efficient, method of shifting a complete byte array's elements contents two bits to the right, and it has an overflow if the final element's shift will contain a value:

Code Select Expand

'
'   /\\\\\\\\\
'  /\\\///////\\\
'  \/\\\     \/\\\                                                 /\\\          /\\\
'   \/\\\\\\\\\\\/        /\\\\\     /\\\\\\\\\\     /\\\\\\\\   /\\\\\\\\\\\  /\\\\\\\\\\\  /\\\\\\\\\
'    \/\\\//////\\\      /\\\///\\\  \/\\\//////    /\\\/////\\\ \////\\\////  \////\\\////  \////////\\\
'     \/\\\    \//\\\    /\\\  \//\\\ \/\\\\\\\\\\  /\\\\\\\\\\\     \/\\\         \/\\\        /\\\\\\\\\\
'      \/\\\     \//\\\  \//\\\  /\\\  \////////\\\ \//\\///////      \/\\\ /\\     \/\\\ /\\   /\\\/////\\\
'       \/\\\      \//\\\  \///\\\\\/    /\\\\\\\\\\  \//\\\\\\\\\\    \//\\\\\      \//\\\\\   \//\\\\\\\\/\\
'        \///        \///     \/////     \//////////    \//////////      \/////        \/////     \////////\//
'                                  Let's find out together what makes a PIC Tick!
'
' Demonstration of shifting a complete byte array's contents, two bits to the right
'
' Written for the Positron8 compiler by Les Johnson.
'
    Device = 18F25K20                                       ' Tell the compiler what device to compile for
    Declare Xtal = 16                                       ' Tell the compiler what frequency the device will be operating at (in MHz)
'
' Setup USART1
'
    Declare Hserial1_Baud = 9600                            ' Set the Baud rate to 9600
    Declare HRSOut1_Pin   = PORTC.6                         ' Set the TX pin
'
' Create any variables for the demo here
'
    Dim bIndex    As Byte                                   ' Holds an index to the array's elements
    Dim bStore    As Byte                                   ' Used as storage for an element's value
    Dim wTemp     As Word                                   ' Holds the elements contents to shift right
    Dim bTempLow  As wTemp.Byte0                            ' Alias to the low byte of wTemp
    Dim bTempHigh As wTemp.Byte1                            ' Alias to the high byte of wTemp. This will be shifted, and the overflow value will be placed in bTempLow
'
' Create a byte array that contains the values to shift right by two bits. Always leave the last element blank to hold the overflow
'
    Dim bSourceArray[11] As Byte Heap = %10100101, %10100111, %10100111, %10100101, %10100110, %10100111, %10100111, %10100111, %10100111, %10100111, %00000000

'-------------------------------------------------------------------------
' The main program starts here
' Shift a complete byte array's contents, two bits to the right and place any overflow shifts into the array's overflow element
' Display the array's contents before and after the shift on a serial terminal
'
Main:
    HRSOut "Before:"                                        ' \
    For bIndex = 0 To Bound(bSourceArray)                   ' |
        HRSOut Bin8 bSourceArray[bIndex], " | "             ' | Display the original array's contents on a serial terminal
    Next                                                    ' |
    HRSOut 13                                               ' /
'
' Shift the second last element into the emply (overflow) last element if the value will overflow after a shift right
'
    bStore = bSourceArray[9]                                ' Read the last element that contains the values to shift into bStore
    If bStore <> 0 Then                                     ' Does the last element that is to be shifted actually contain a value?
        bTempLow = 0                                        ' \
        bTempHigh = bStore                                  ' / Yes. So place the element into a word variable's high byte
        wTemp = wTemp >> 2                                  ' Shift the element's value right by 2, so any overflow will be placed in the low byte
        bSourceArray[10] = bTempLow                         ' Load the shift overflow into the array's last element used for overflow
    EndIf
'
' Shift the values within the array's element limits
'
    For bIndex = Bound(bSourceArray) - 1 DownTo 1           ' Create a loop for the second last element to the second element
        bStore = bSourceArray[bIndex]                       ' Read an element and store it
        bStore = bStore >> 2                                ' Shift the element's value right by 2
        bTempLow = 0                                        ' \
        bTempHigh = bSourceArray[bIndex - 1]                ' / Read the element below the one that has been read into a word variable's high byte
        wTemp = wTemp >> 2                                  ' Shift the element's value right by 2
        bStore = bStore | bTempLow                          ' Or the shifted value into the stored value
        bSourceArray[bIndex] = bStore                       ' Load it back into the array
    Next
'
' Shift the very first element
'
    bStore = bSourceArray[0]                                ' Read an element and store it
    bStore = bStore >> 2                                    ' Shift the element's value right by 2
    bSourceArray[0] = bStore                                ' Load it back into the array

    HRSOut "After :"                                        ' \
    For bIndex = 0 To Bound(bSourceArray)                   ' |
        HRSOut Bin8 bSourceArray[bIndex], " | "             ' | Display the shifted array's contents on a serial terminal
    Next                                                    ' |
    HRSOut 13                                               ' /

I've tested the above code listing in a simulator and it seems to work well. On the serial terminal, the text displayed will be:

Before:10100101 | 10100111 | 10100111 | 10100101 | 10100110 | 10100111 | 10100111 | 10100111 | 10100111 | 10100111 | 00000000 |
After :00101001 | 01101001 | 11101001 | 11101001 | 01101001 | 10101001 | 11101001 | 11101001 | 11101001 | 11101001 | 11000000 |

The values seperated by the pipe (|), show each array element's value before and after the two bit right shift, and the very last element holds the overflow value. The program can also be easily adapted for more bit shifts right.

[trastikata]

How many bytes do you have to shift?
16-bit or 8-bit compiler?

The reason why I asked is because, as Stephen Moss said you can use bitwise shifts in larger variables, but instead of copying variables, I'd alias them.

In your particular example you have a byte array of 6 variables and you want right shift by 2. I'd alias them and move right, left and then right the shift to get the operation done.  Try this:

Code Select Expand

Dim baMyArray[6] As Byte
Dim dwTempVar0 As Dword At baMyArray#0
Dim dwTempVar1 As Word At baMyArray#3

Main:
    dwTempVar0 = dwTempVar0 >> 2   
    dwTempVar0.Byte3 = dwTempVar0.Byte3 << 2
    dwTempVar1 = dwTempVar1 >> 2
End