Write an -bit binary string as , where each and is most significant. Its unsigned interpretation and two's complement interpretation areEquivalently, . The ranges are through and through , respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.
A logical right shift by moves into position and fills the high positions with zero. Its unsigned interpretation isMeanwhile the original unsigned interpretation decomposes asBy integer division, , exactly the unsigned quotient. Thus the source instruction puts the required quotient into
r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to , with endpoint operations implemented as a copy or zero where appropriate.For a 32-bit machine word and , use a left bit shift followed by a logical right shift:The left shift discards all but the lowest bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence
lsls r1, r0, #(32-k)
lsrs r1, r1, #(32-k)r1 contains , the remainder identified in (b). For the remainder is zero; for it is , so these endpoints can be handled directly.On a reduced instruction set computer, a bit mask such as may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.[ref]
Thumb 16-bit instruction set quick reference by Arm. page 1, Logical and Shift/rotate tables
Let , let , and let denote the least nonnegative residue. Here is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into . The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of even if its two's complement interpretation is negative, because divides the word modulus . The adjusted value is representable for every input: positive inputs are unchanged, and negative inputs gain only .
rem1024:
asrs r3, r0, #31 // r3 = -s: all zero bits or all one bits
lsrs r3, r3, #22 // r3 = b = 1023*s
adds r0, r0, r3 // r0 = a+b
lsls r0, r0, #22 // r0 has word value (a+b)*2^22 modulo 2^32
lsrs r0, r0, #22 // r0 = u = (a+b) modulo 1024, in 0,...,1023
subs r0, r0, r3 // r0 = u-b
bx lr // return u-bFor , , so the return value is the usual nonnegative remainder . For , put as a mathematical integer, and write with . If , then and the return value is zero. If , thenThese are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below , and satisfies . The proof includes the smallest representable input: was used only in mathematical reasoning, not as an overflowing machine operation.[ref]
C11 committee draft N1570. section 6.5.5 paragraph 6, quotient truncation and the quotient–remainder identity
Use the same bias, then an arithmetic right shift by ten:An arithmetic right shift of a two's complement integer computes division rounded down. For , this already equals truncation towards zero. For , the signed power-of-two division by biasing identity isIndeed, writing with makes the adjusted numerator ; its quotient rounded down is for every , including zero. Thus the code returns the signed quotient in all cases and contains no data-dependent branch. The final
div1024:
asrs r3, r0, #31 // -1 when a<0, otherwise 0
lsrs r3, r3, #22 // b = 1023 when a<0, otherwise 0
adds r0, r0, r3 // a+b, representable for every signed input
asrs r0, r0, #10 // floor((a+b)/1024)
bx lrbx lr simply returns to the caller. Articles by others on the same topic
There are currently no matching articles.