How do i do a bitshift right in binary?

5.9k views Asked by At

Hopefully this is a simple question but I cannot for the life of me figure out how to do a bitshift in binary. This is being done in the LC3 environemnt. I just need to know how to arithmetical divide by two and shift to the right. I know going left is simple by just adding the binary value to itself, but I have tried the opposite for bitshift right(subtracting from itself, NOTing and then subtracting etc etc.) Would be much appreciated.

Or if you have a better way to move x00A0 to x000A that would also be fantastic. Thanks!

5

There are 5 answers

0
UL7AAjr On
.ORIG x3000
        BR      main
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
;       UL7AAjr
;       shift right register R0
;       used rigisters R1, R2, R3, R4, R5
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
shift_right
        AND     R4, R4, #0      ; R4 - counter = 15 times
        ADD     R4, R4, #15
        AND     R1, R1, #0      ; R1 - temp result
        LEA     R2, _sr_masks   ; R2 - masks pointer
_sr_loop
        LDR     R3, R2, #0      ; load mask into R3
        AND     R5, R0, R3      ; check bit in R0
        BRZ     _sr_zero        ; go sr_zero if bit is zero
        LDR     R3, R2, #1      ; R3 next mask index
        ADD     R1, R1, R3      ; add mask to temp result
_sr_zero
        ADD     R2, R2, #1      ; next mask address
        ADD     R4, R4, #-1     ; all bits done?
        BRNP    _sr_loop

        AND     R0, R0, #0      ; R0 = R1
        ADD     R0, R0, R1
        RET

_sr_masks
        .FILL   x8000
        .FILL   x4000
        .FILL   x2000
        .FILL   x1000
        .FILL   x0800
        .FILL   x0400
        .FILL   x0200
        .FILL   x0100
        .FILL   x0080
        .FILL   x0040
        .FILL   x0020
        .FILL   x0010
        .FILL   x0008
        .FILL   x0004
        .FILL   x0002
        .FILL   x0001
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
main
        LD      R0, data
        JSR     shift_right
        HALT

data   .FILL   xFFFF


.END
0
user12458240 On
; right shift R0 1-bit with sign-extention
; Algorithm:    look-uo table and auto-stop
.ORIG   x3000
        AND     R1, R1, #0  ; r1 = 0
        LEA     R2, TABLE   ; r2 = table[]
        AND     R0, R0, #-2
LOOP    BRzp    MSB0
        LDR     R3, R2, #0  ; r3 = table[r2]
        ADD     R1, R1, R3  ; r1 += r3
MSB0    ADD     R2, R2, #1  ; r2++
        ADD     R0, R0, R0  ; r0 << 1
        BRnp    LOOP
        ADD     R0, R1, #0  ; r0 = r1
        HALT
TABLE
        .FILL   xC000
        .FILL   x2000
        .FILL   x1000
        .FILL   x0800
        .FILL   x0400
        .FILL   x0200
        .FILL   x0100
        .FILL   x0080
        .FILL   x0040
        .FILL   x0020
        .FILL   x0010
        .FILL   x0008
        .FILL   x0004
        .FILL   x0002
        .FILL   x0001
.END
0
user12458240 On
; right shift R0 1-bit with sign-extention
; Algorithm:    build bit form msb one by one
.ORIG   x3000
        AND     R1, R1, #0  ; r1 = 0
        ADD     R2, R1, #14 ; r2 = 14
        ADD     R0, R0, #0  ; r0 = r0
        BRzp    LOOP
        ADD     R1, R1, #-1 ; r1 = xffff
LOOP    ADD     R1, R1, R1  ; r1 << 1
        ADD     R0, R0, R0  ; r0 << 1
        BRzp    MSB0
        ADD     R1, R1, #1  ; r1++
MSB0    ADD     R2, R2, #-1 ; cnt--
        BRp     LOOP
        ADD     R0, R1, #0  ; r0 = r1
        HALT
.END
0
user12458240 On
; right shift R0 1-bit with sign-extention
; Algorithm:    left-rotate 14 times with proper sign
.ORIG   x3000
        LD      R1, CNT
        ADD     R2, R0, #0
LOOP    ADD     R0, R0, R0  ; r0 << 1
        BRzp    NEXTBIT
        ADD     R0, R0, #1
NEXTBIT ADD     R1, R1, #-1
        BRp     LOOP
        LD      R3, MASK
        AND     R0, R0, R3
        ADD     R2, R2, #0
        BRzp    DONE
        NOT     R3, R3
        ADD     R0, R0, R3
DONE    HALT
MASK    .FILL   x3FFF
CNT     .FILL   14
.END
0
Chris M On

This is an older post, but I ran into the same issue so I figured I would post what I've found.

When you have to do a bit-shift to the right you're normally halving the the binary number (divide by 2) but that can be a challenge in the LC-3. This is the code I wrote to preform a bit-shift to the right.

; Bit shift to the right
.ORIG x3000

MAIN
    LD R3, VALUE

    AND R5, R5, #0      ; Reseting our bit counter

    B_RIGHT_LOOP
        ADD R3, R3, #-2     ; Subtract 2 from the value stored in R3
        BRn BR_END      ; Exit the loop as soon as the number in R3 has gone negative 
        ADD R5, R5, #1      ; Add 1 to the bit counter
        BR B_RIGHT_LOOP     ; Start the loop over again 
    BR_END

    ST R5, ANSWER       ; Store the shifted value into the ANSWER variable

    HALT            ; Stop the program

; Variables
VALUE   .FILL x3BBC     ; Value is the number we want to do a bit-shift to the right
ANSWER  .FILL x0000

.END

Keep in mind that with this code the left most bit B[0] is lost. Also this code doesn't work if the number we are trying to shift to the right is negative. So if bit [15] is set this code won't work. Example:

VALUE .FILL x8000    ; binary value = 1000 0000 0000 0000
                     ; and values higher than x8000
                     ; won't work because their 15th
                     ; bit is set

This should at least get you going on the right track.