More bit shifting issues

Boltar <boltar2003@yahoo.co.uk> writes:
> On Apr 1, 4:43 pm, "Bartc" <b...@freeuk.com> wrote: 
>
> But not any longer , any modern CPU has a div or mul type instruction.

Yes, but the div or mul instruction might still be slower than an
equivalent shift.  More to the point, modern compilers are capable of
generating a shift instruction for multiplication or division by a
power of 2, *if* it makes the code faster and *if* it can prove that
the result is equivalent.

--
Keith Thompson (The_Other_Keith) <kst-u@mib.org>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Boltar wrote:
> On Apr 1, 4:43 pm, "Bartc" <b...@freeuk.com> wrote: 
>
> But not any longer , any modern CPU has a div or mul type instruction.

Not in the embedded world. The processor I work with most frequently has
only optional support for mul and div.

Boltar <boltar2003@yahoo.co.uk> wrote:
>
> I always assumed bit shifting was just a shift of the register bits
> left or right and whether the value was being treated as signed or
> unsigned was completely irrelevant. Obviously not. :o(

There are two different forms of right shift that most processors
support: in logical shift, which is what you expected, the new bits
shifted in are always zero; in arithmetic shift, which is what you got,
the new bits are copies of the sign bit.  Both have their uses, which is
why most processors provide both.  Which one the C implementation
chooses to use for >> is up to the implementor.

-Larry Jones

If I get a bad grade, it'll be YOUR fault for not doing the work for me!
-- Calvin

Boltar wrote:
> ...
> Thats what I would have expected. Its a shift , not a mathematic
> operation, the sign should be irrelevant and the value should just be
> treated as 32 seperate bits to be moved as appropriate. Why would
> anyone design this operation to preserve the sign? I don't understand.
> ...

In C89/90 it is recommended (and in C99 it is required) that the
integral division '/' rounds its results towards '0'. In many cases it
is useful to have a modulo-correct version of integral division
operator, i.e. operator that always rounds towards negative infinity.
This is what sign-preserving shift does for power-of-2 division on 2's
complement platforms.

(Doesn't look like much of a rationale, but for what it's worth...)

Of course, since the behavior is implementation-defined, one cannot rely
on this behavior as being portable.

--
Best regards,
Andrey Tarasevich

Boltar wrote:
>
> I seem to be having yet more wierd issue with bit shifting.  It
> seems the following code doesnt do anything under gcc (ie it
> returns -1 as both results).  Anyone know why?  Is it another
> language definition or CPU issue?
>
> main() {
>         printf("%d\n",(int)0xFFFFFFFF >> 1);
>         printf("%d\n",(int)-1 >> 1);
> }

I suspect this covers it:

6.5  Expressions

... snip ...

[#4]  Some  operators  (the unary operator ~, and the binary
operators <<, >>, &, ^, and  |,  collectively  described  as
bitwise  operators)  are required to have operands that have
integer type.  These operators return values that depend  on
the   internal   representations   of   integers,  and  have
implementation-defined  and  undefined  aspects  for  signed
types.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

On Apr 1, 11:08=A0am, Boltar <boltar2...@yahoo.co.uk> wrote:
> On Apr 1, 4:43 pm, "Bartc" <b...@freeuk.com> wrote:
> 
 
>
> But not any longer , any modern CPU has a div or mul type instruction.


Not at all.  IPF, and many RISCs, for example, do not have an integer
divide (or often an FP one either).  They often support a divide
approximation instruction, which you then need to follow with a few
iterations of Newton-Raphson to actually generate a quotient.

In any event, left shifts are typically a fair bit faster than
multiplies (often several times), although there are CPUs with
exceptional fast multiplies and exceptionally slow shifters where
that's not true, and right shifts are invariably *much* faster than
actual divisions (often 20-50 times).

On Apr 1, 11:58 pm, "robertwess...@yahoo.com"
<robertwess...@yahoo.com> wrote:
> In any event, left shifts are typically a fair bit faster than
> multiplies (often several times), although there are CPUs with
> exceptional fast multiplies and exceptionally slow shifters where
> that's not true, and right shifts are invariably *much* faster than
> actual divisions (often 20-50 times).

Well that begs the question of why the cpu integer div instruction
doesn't simply check the divisors least significant bit to see if its
set to zero (even) and if it is then use bit shifting to get the
result. Same for multiply.

B2003

"Boltar" <boltar2003@yahoo.co.uk> wrote in message
news:863943e8-19c6-4fa5-9c4d-6ff04b747d7d@s13g2000prd.googlegroups.com...
> On Apr 1, 11:58 pm, "robertwess...@yahoo.com"
> <robertwess...@yahoo.com> wrote: 
>
> Well that begs the question of why the cpu integer div instruction
> doesn't simply check the divisors least significant bit to see if its
> set to zero (even) and if it is then use bit shifting to get the
> result. Same for multiply.

Probably because it's a *lot* easier to have separate instructions for
shift, which are essential anyway. And it would have to check there is only
one bit set.

Anyway most cpus must have a shift-right-logical which does exactly what you
want. It's up to your C implementation whether that is invoked by
right-shifting an unsigned value.

--
Bart

>Well that begs the question of why the cpu integer div instruction
>doesn't simply check the divisors least significant bit to see if its
>set to zero (even) and if it is then use bit shifting to get the
>result. Same for multiply.

Bit shifting can't replace division unless the divisor is a power
of two, not just even.

"Simply check" is likely to take extra time.  Also, it may be a
low-percentage optimization that just doesn't get used that much,
in the opinion of the CPU designer, probably backed up by a bunch
of statistics on code in real programs.

On Apr 2, 11:50=A0am, gordonb.53...@burditt.org (Gordon Burditt) wrote: 
>
> Bit shifting can't replace division unless the divisor is a power
> of two, not just even.
>
> "Simply check" is likely to take extra time. =A0Also, it may be a
> low-percentage optimization that just doesn't get used that much,
> in the opinion of the CPU designer, probably backed up by a bunch
> of statistics on code in real programs.


Even worse, it will screw up the pipeline on modern/large CPUs.  At
least for multipliers, these tend to be very fixed - IOW, it's five
cycles through the multiplier, no matter the operands.  Making that
variable length requires a whole bunch of other stuff to be added, and
may make it much more difficult to pipeline several sequential
multiplications (IOW, the multiplier may take five cycles, but it can
start a new multiplication every cycle).

Now older/smaller CPUs often implement mulch smaller multipliers
(often the hardware equivalent of shift-and-add), and on those, early
out is often implemented (IOW, when you run out of one bits in the
multiplier, you can stop), and the shift cycle is sometimes faster for
zero bits in the multiplier).  But those take many cycles in any
event, and making them take a variable number is often not a big deal.

General purpose dividers are a huge pain, and while some variability
is not uncommon in full hardware divider implementations, for the many
CPUs where there is no hardware divide (just approximate plus Newton-
Raphson), I doubt there's a useful way you could implement such a
thing without requiring a conditional branch in the divide routine
(which would be horrible).  Again, iterative dividers on small
implementations often do have some sorts of optimizations, and some do
fast shift past low zero bit in the divisor (basically the division
equivalent of early-out).

But in short, at least for multipliers on large implementations, this
would likely slow general multiplications down far more than you'd
gain from a few special cases going faster.  And dividers are going to
be an even bigger mess.

Probably a better optimization is to provide short multiplier/divisor
operations.  Say up to eight bits.  Those would cover a lot of actual
operations, and a 32x8 multiplier could be made to run rather faster
than a full 32x32 one.