Advanced

Bit Manipulation

Advanced bit tricks with only AND, NOT, and ADD.

Bitwise Operations in LC-3

With only AND, NOT, and ADD, we can still perform all common bit operations.

OR (using De Morgan's Law)

A OR B = NOT(NOT(A) AND NOT(B))

; R2 = R0 OR R1
NOT R3, R0        ; R3 = ~R0
NOT R4, R1        ; R4 = ~R1
AND R2, R3, R4    ; R2 = ~R0 & ~R1
NOT R2, R2        ; R2 = ~(~R0 & ~R1) = R0 | R1

XOR

A XOR B = (A AND NOT(B)) OR (NOT(A) AND B)

; R2 = R0 XOR R1
NOT R3, R1        ; R3 = ~R1
AND R3, R0, R3    ; R3 = R0 & ~R1
NOT R4, R0        ; R4 = ~R0
AND R4, R4, R1    ; R4 = ~R0 & R1
; Now OR them: R2 = R3 | R4
NOT R3, R3
NOT R4, R4
AND R2, R3, R4
NOT R2, R2        ; R2 = R0 XOR R1

Shift Left (Multiply by 2)

LC-3 has no shift instruction, but ADD R0, R0, R0 effectively doubles the value — which is a left shift by 1 bit.

; Shift R0 left by 3 positions (multiply by 8)
ADD R0, R0, R0    ; R0 << 1
ADD R0, R0, R0    ; R0 << 2
ADD R0, R0, R0    ; R0 << 3

Testing a Specific Bit

To check if bit N of R0 is set, AND with a mask that has only bit N set:

; Test if bit 0 (LSB) of R0 is set
AND R1, R0, #1    ; R1 = R0 & 1
BRp BIT_IS_SET    ; If result > 0, bit was set

; Test if bit 4 is set — need value 16 = 0x10
AND R2, R2, #0
ADD R2, R2, #1
ADD R2, R2, R2    ; 2
ADD R2, R2, R2    ; 4
ADD R2, R2, R2    ; 8
ADD R2, R2, R2    ; 16
AND R1, R0, R2    ; R1 = R0 & 16
BRp BIT4_SET

Exercise

Write a program that counts the number of 1-bits in a value. Load the value from memory (use x00FF = 255 which has 8 set bits), count the bits, and print the count as a digit.

.ORIG x3000
LD R0, VALUE      ; Load the value
AND R1, R1, #0    ; R1 = bit counter
 
; Hint: check the LSB with AND R2, R0, #1
; If set, increment counter
; Then shift R0 right... but there's no shift right!
; Alternative: loop 16 times, checking each bit
; Use ADD R0, R0, #0 won't work for shift right
; Try: ADD R0, R0, R0 shifts LEFT, putting the MSB into the sign bit area
; Better approach: AND with 1 to check LSB, then
; we need to "shift right" -- one way is to count all 16 bits
; by checking MSB: ADD R0, R0, #0 sets N if bit 15 is set
; then ADD R0, R0, R0 shifts left
 
AND R2, R2, #0
ADD R2, R2, #15
ADD R2, R2, #1    ; R2 = 16 (loop counter)
 
COUNT_LOOP
ADD R2, R2, #0
BRz COUNT_DONE
 
; Check if MSB (bit 15) is set
ADD R0, R0, #0
BRzp SKIP_INC
ADD R1, R1, #1    ; count++
SKIP_INC
 
ADD R0, R0, R0    ; Shift left (moves next bit to MSB position)
ADD R2, R2, #-1
BR COUNT_LOOP
 
COUNT_DONE
; Print R1 as ASCII
ADD R0, R1, #0
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #3
OUT
HALT
 
VALUE .FILL x00FF
.END

.ORIG x3000
LD R0, VALUE      ; Load the value
AND R1, R1, #0    ; R1 = bit counter

; Hint: check the LSB with AND R2, R0, #1
; If set, increment counter
; Then shift R0 right... but there's no shift right!
; Alternative: loop 16 times, checking each bit
; Use ADD R0, R0, #0 won't work for shift right
; Try: ADD R0, R0, R0 shifts LEFT, putting the MSB into the sign bit area
; Better approach: AND with 1 to check LSB, then
; we need to "shift right" -- one way is to count all 16 bits
; by checking MSB: ADD R0, R0, #0 sets N if bit 15 is set
; then ADD R0, R0, R0 shifts left

AND R2, R2, #0
ADD R2, R2, #15
ADD R2, R2, #1    ; R2 = 16 (loop counter)

COUNT_LOOP
ADD R2, R2, #0
BRz COUNT_DONE

; Check if MSB (bit 15) is set
ADD R0, R0, #0
BRzp SKIP_INC
ADD R1, R1, #1    ; count++
SKIP_INC

ADD R0, R0, R0    ; Shift left (moves next bit to MSB position)
ADD R2, R2, #-1
BR COUNT_LOOP

COUNT_DONE
; Print R1 as ASCII
ADD R0, R1, #0
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #3
OUT
HALT

VALUE .FILL x00FF
.END

x00000

PCx3000

NZP

← Data Structures Sorting Algorithms →