• Please review our updated Terms and Rules here

16-bit X86 Trick to Multiply by a Number's Sign?

N

neilobremski

Experienced Member
Joined
Oct 9, 2016
Messages
55
Location
Seattle, USA
Yesterday I found a branch-less way to get an absolute value in assembler using CBW (for bytes) and CWD (for words). It wasn't a stretch from there to figure out how to determine the sign in a similar way which results in either -1 (~FFh) or 1. That led me to wonder if there is a branch-less way to [efficiently] multiply another number by this sign? The result would either be the number as is or negated.

And on this topic, is there a site/book/article that basically lists out these sorts of common tricks for ol' 16-bit X86 assembly?
 
The simplest solution I can think of with no branching or multiply instruction is as follows:
Code: 
	; Assuming the number to be multiplied is in AX and the derived sign is in BX
	sar bx, 1	; turns 1 into 0 but leaves 0xFFFF alone
	xor ax, bx	; ones-complement AX if the sign in BX is negative, leave it alone otherwise
	; this next instruction won't work as-is on 8086/88, we'd need to use CL for the shift count
	shr bx, 15	; turns BX into 1 if it was 0xFFFF, still 0 if it started out as 1
	add ax, bx	; make the ones-complement into a twos-complement by adding 1, or do nothing
	; AX should now be "multiplied" by the sign value
 
One nice place for tricks used to be http://www.df.lth.se/~john_e/fr_gems.html but it's gone now, but you can look it up with archive.org. http://www.mark.masmcode.com/ is another one.

There used to be various assembler forums around, but they all seem to be gone now :-( Stackoverflow might be the last place to ask. (Or here, as there are a lot of assembler people here.)

As for your "copy sign from one value to another", maybe this code for saturated subtraction can give you a hint:

Code: 
        add     [usercount],-1          ;saturated subtraction:
        sbb     bx,bx                   ;bx=FFFF if +val/0, 0000 if -val
        and     [usercount],bx          ;+val untouched, -val clipped to 0
 
Not guaranteeing that it's the shortest or fastest, but how about (signed number in AX) and (number to be multiplied by sign in BX):

CWD
XOR BX,DX
ADD DX,DX
ADC BX,0

I'm sure that this can be improved upon.
 
Code: 
shr bx, 15	; turns BX into 1 if it was 0xFFFF, still 0 if it started out as 1

This is going to hurt on an 8088, since it cannot do anything other than shr bx, 1. Either you'd repeat that 15 times, or you'd have to use the variant with shr bx, cl.
I think in this case a simpler solution would be:
and bx, 1

But I think in general Chuck(G)'s is the way to go:
You want to solve it in one go, rather than converting the value to a (-1,0,1) value first. The bitmask is easier to derive from the 2s complement value directly than it is from a (-1,0,1) value. Also, if you need to derive that (-1,0,1) value from the original value in the first place, that's only extra overhead.

I think his version can be refined though...
One needs to observe the following, in 2s complement:
neg x == (not x) + 1
not x == x ^ -1
Hence:
neg x == (x ^ -1) - (-1)

Now, we have two cases:
For positive X -> Y = Y
For negative X -> Y = -Y

If you take the above formula:
Y = (Y ^ Z) - Z
Then for Z = 0:
Y = (Y ^ 0) - 0 = Y
For Z = -1:
Y = (Y ^ -1) + 1 = -Y

Hence we can do this:
CWD (if (AX >= 0) DX = 0 else DX = -1)
XOR BX, DX
SUB BX, DX

Edit: Also, on older CPUs, branches aren't necessarily all that expensive... so this solution wouldn't even be that bad:
TEST AX, AX
JNS skip
NEG BX
skip:

And if you've just calculated ax beforehand, perhaps you can even do without the TEST, because the sign-flag may already be set by the previous instruction.
 
Last edited:
Scali said:
This is going to hurt on an 8088, since it cannot do anything other than shr bx, 1. Either you'd repeat that 15 times, or you'd have to use the variant with shr bx, cl.
I think in this case a simpler solution would be:
and bx, 1
Click to expand...
You're right - well-spotted. I initially figured I needed the shift to make sure that the add didn't increment AX if the sign was +1, but I didn't take into account that I'd already done that at the start of the routine.
 
Actually, though, I just realized there's no reason to finagle it that way in the first place when we can just do this:
Code: 
	; Assuming the number to be multiplied is in AX and the derived sign is in BX
	sar bx, 1	; turns 1 into 0 but leaves 0xFFFF alone
	xor ax, bx	; ones-complement AX if the sign in BX is negative, leave it alone otherwise
	sub ax, bx	; subtract -1 (add 1) if sign is negative, turning AX into the twos-complement
	; AX should now be "multiplied" by the sign value
 
@scali -- good on ya! I was wondering how long it would take someone to tumble to that. :)

I don't think there are any shorter solutions. The downside is that it does take an extra register (DX), but that's a small price to pay.
 
This is a fun little thread for a Thursday and I'm impressed at what you guys came up with. Well done!

@Trixter -- Many thanks for the links, the latter is definitely going on my Kindle for some light reading ...
 
For completeness, I'd like to point out that you can also reverse the order of the bitwise inverse and the addition:
neg x == (not x) + 1
But also:
neg x == not (x-1)

Which would lead to:
CWD
ADD BX, DX
XOR BX, DX

Sometimes one variation may be more useful, other times the other.

And related to that... sometimes you may want to calc X = -X - 1
Well, know you know that this is simply NOT X instead of (NEG X) - 1. Saves an instruction :)

In general, it's good to understand 2s complement notation, and how bitwise operations affect it.
 
This reminds me of a discussion I had with a co-worker a few decades ago. The subject was "Which is better for bit-tiwddling--one's or twos' complement?"

I know that I leaned toward one's complement at the time.
 
Scali said:
This is going to hurt on an 8088, since it cannot do anything other than shr bx, 1. Either you'd repeat that 15 times, or you'd have to use the variant with shr bx, cl.
Click to expand...
Or just:

ROL BX, 1
AND BX, 1

It often helps on 8088/8086 to remember you can go the other direction -- particularly when dealing with signed numbers. See my trick for calculating x * 2 + y * 160 in realtime when I can't spare the memory for a lookup table:

MOV DI, [BP + 6] ; x word
SHL DI, 1
XOR AX, AX
MOV AH, [BP + 8] ; y byte
SHR AX, 1 ; now == *128
ADD DI, AX
SHR AX, 1 ; now == *64
SHR AX, 1 ; now == *32
ADD DI, AX

Still not as good as MOV BX, [BP+8] ; ADD DI, [BX + lookupTable], but still... when you want to shift a value that fits in a byte width by more than 4 bits, it often helps to reverse the "problem".
 
You must log in or register to reply here.
Back
Top