Shifts

Context

Right or left bit shifts are operators in algorithmic, with a general syntax >> or <<.
These operators append B bits at the beginning or end of A, and therefore truncate the last or first B bits of A.
Example: 47 << 2 = 188, as 47 is 00101111, and 10111100 = 188 in base 10.
One useful application is the multiplication / division by powers of 2. Actually, X<<Y = X*2^Y, and X>>Y = X/2^Y.
Let's implement operations <<1 and >>1, namely multiplication / division by 2.

Initial state

• Memory: X 0 0
• Cursor: first cell
• Input: any

Process - left shift

• While first cell is not null
• Remove 1 to first cell
• Add 2 to second cell
• Loop invariant: first cell + (second cell) / 2 = X
• When first cell is null: second cell equals 2X

Code - try it

[->++<]

Final state - left shift

• Memory: 0 2X
• Cursor: first cell
• Input: unchanged
• Output: unchanged

Process - right shift

• Division by 2 can be implemented in a different way than regular division:
• While first cell if not null
• Remove 1 to first cell
• If possible, remove 1 again to first cell, increase third cell and stay on second
• Move right (i.e. on second cell if first is now null, third otherwise, and third is not null in this case)
• Move left if current is not null (i.e. fallback on second cell in all case)
• Loop invariant: first cell + 2*third cell = X or X-1
• When first cell is null: third is half X, rounded to floor

Code - try it

[-[->>+<]>[<]<]

 Final state - right shift

• Memory: 0 0 X/2
• Cursor: first cell
• Input: unchanged
• Output: unchanged