Is there a way to perform arithmetic right shift using only xorq, andq, addq, iaddq, & subq?

Question

I'm in a hypothetical architecture that only has those operations (Y86). No arithmetic right shift exists. I'm essentially trying to capture the upmost bit to determine if the number is negative and if so add it to the result register, rax.

Edit:

Sorry all, I forgot to specify, I'm trying to avoid conditional branches to see if it improves the efficiency. No cmov exists in the version I'm in.

The furthest I've gotten is:

andq $0x10000000, elem
subq $0x01111111, elem
addq elem, %rax

However, for a result of 0 this doesn't work.

Answer 1

If Y86 allows MOVQ to access memory that is not QWORD-aligned, then it can be done. But I doubt if it will perform better than a conditional branch.

The trick is to write the number to memory, then read it again from an address that is slightly 'off'. This effectively shifts bits across a multiple of 8. Combine this with addq to shift the bits 1 position to the left.

Please note that this highly relies on the endianness of the processor architecture. The following example is based on little endian (Intel-style). On big endian, the offsets will have to be adjusted.

(If you prefer AT&T syntax, then please reverse the operands and remove the brackets.)

movq rbx,number         ; sign bit is bit 63 of rbx
movq [address],rbx      ; sign bit is most significant bit of the byte at [address+7]
movq rbx,[address+4]    ; sign bit is bit 31 of rbx
addq rbx,rbx            ; sign bit is bit 32 of rbx
movq [address],bx       ; sign bit is least significant bit of the byte at [address+4]
movq rbx,[address+4]    ; sign bit is bit 0 of rbx
andq rbx,1              ; rbx = 0 for positive number, rbx = 1 for negative number
addq ax,bx

Answer 2

Assuming you can use a loop and conditional branch:

    mov result, 0
    mov lead, 2
    mov follow, 1
1:
    mov tmp, n
    and tmp, lead
    jz 2f
    add result, follow
2:
    add follow, follow
    add lead, lead
    jnz 1b

The tmp, lead, and follow variables must be in registers. result can be either in a register or in memory.