Subj : Re: faster approach to division
To   : comp.programming
From : Gerry Quinn
Date : Thu Jul 14 2005 11:50 am

In article <db4oo5$fq5$1@grapevine.lcs.mit.edu>, cbarber@curl.com 
says...

> These only work if 'value' is non-negative. (e.g., right-shifting -1 will 
> produce -1).
> 
> To divide a signed value by 2, you need to write something like:
> 
>   (value + ((unsigned)value >> 31)) >> 1
> 
> but I wouldn't bother w/ stuff like this unless profiling shows that you need to.

I think you could do much better in assembly than C.  I was thinking 
about doing this without branching the other day, and I couldn't find a 
way of doing it in C that wasn't clumsy.  But the main difficulty 
finding a quick non-branching method to give 1 or 0 (or vice versa) if 
the number is positive or negative.

In machine code for any plausible processor, this would be easy - just 
add an overflow flag to zero.  But it doesn't seem possible without a 
lot of shifting in pure C.

If you have 1 or 0, just subtract 1 to give 00000000 or ffffffff, 
complement as desired, and do an AND operation with a copy of the 
value.  Then add it to multiply by two (or not) and subtract it twice 
to change sign (or not).

The shortest non-branching method I could find in pure C was to add two 
to the divisor, making it 4, 3, 1 or 0.  Then add that many x's to -2x.  
This can be done with relatively few shifts, but still too many to make 
it worthwhile.

It may be that some C compilers use assembly tricks to make !x give 1 
for zero values without branching, in which case you could use !( d & 
0x80000000 ) to detect negative numbers.

- Gerry Quinn

.