«

In article <slrnjdddj9.l6p.usenet->,
Seebs <usenet-> wrote:
> You propose to create a "division library". What, exactly, would your
> division library do that's better than what the compilers do?

There is actually one division optimization case where compilers cannot
really help and a support library would be useful.

Now, compilers can well optimize a general division where run-time
operands are arbitrary, either with a dedicated hardware division
instruction or a subroutine.

Compilers can also optimize a division with a constant into a shift,
or a multiplication with a reciprocal, or whatever works best on that
architecture for that particular divisor.

But there's a middle case, where the divisor is not constant, but
doesn't change very often. For instance, a hash table needs to do a
modulo operation on every lookup, but the divisor remains the same
until the table is resized. In such a situation, it would be nice to
have some way of pre-calculating a division operation for a fixed
divisor so that it could be performed faster than the the wholly
general division. In practice this would mean finding the reciprocal
using the same algorithm the compiler uses for constants.


Lauri

On Wednesday, November 30, 2011 1:53:31 PM UTC+8, arnuld wrote:
> > On Tue, 29 Nov 2011 17:39:12 +0000, Ben Bacarisse wrote:
>
> > Ian Collins <ian-...@hotmail.com> writes: <snip>
> >> [...] I believe sifting a signed integer and this the code is
> >> undefined.
> >
> > That's a good shorthand, since it will encourage the use of unsigned
> > ints wherever possible, but it is not true as you have stated it. 1<<4
> > is a shift of a signed int and is well-defined. The exact rules can be
> > found in the C standard (search for n1256.pdf) or in any good C text,
> > but it's better to forget them! Use unsigned ints for bit operations.
>
> I have H&s5 here. Section 7.6.3 states "Applying the shift operator >> is
> not portable when the left operand is negative, signed value and the
> right operand is nonzero"
>
> What I noticed are two things:
>
> (1) My examlpes uses << rather than >>. Hence above rule does not apply
> (2) H&S5 is using word "and" rather than word "or", which directly means
> all three conditions in "negative, signed value and right operand is
> zero" must be satisfied.
>
>
> n1256.pdf in Section 6.5.7 (4) states:
>
> "The result of E1 << E2 is E1 left shifted E2 but positions; vacated
> bits are filled with zeroes. If E1 has unsigned type, the result is
> E1x2^E2, reduced modulo one more than the maximum value representable in
> the result type. If E1 has a signed type and nonnegative value, and
> E1x2^E2 is representable in the result type, then that is resulting
> value; otherwise , the behavior is undefined"
>
> It is proved that this interview code has undefined behavior.
> (unfortunately it was a MCQ (Multiple Choice Question) and undefined
> behavior was not one of the options).
>
>
>
> > The OP's code:
> >
> > printf("%x\n", -1<<4);
> >
> > is probably undefined for two reasons (the other being the technical
> > detail that %x expects an unsigned int argument) and writing
>
> hey.. I did not know this %x secret
>
>
>
> > printf("%x\n", (unsigned)-1<<4);
> >
> > would have fixed both. Who sets these interview questions?
>
> Yes, that casting fixes as per standard says. Thanks for that. Regarding
> interview questions, once I was asked the value of i after this operation:
>
> i = i++;
>
> I said its UB but the guy did not like my answer.
>

Does UB stands for undefined behavior?
>
>
>
> --
> arnuld
> http://LispMachine.Wordpress.com

Do you have to use >> operator to mimic the division if there is no divider operation in CPU?

Stanley Rice <> writes:

> Do you have to use >> operator to mimic the division if there is no divider operation in CPU?

No -- that would be equivalent to saying you had to supply your own
software division routine. If you use a / or % (and I'm sure there are
others I'm not thinking of) operator, the compiler will generate the
correct code to do a division. How good that code will be is determined
by the quality of the compiler: if you're dividing by 2, hopefully
it'll generate a bit-shift instruction rather than calling a general
purpose division routine.

But it will end up doing what amounts to a division.

On 2011-11-30, Seebs <usenet-> wrote:
> On 2011-11-30, 88888 Dihedral <> wrote:
> You propose to create a "division library". What, exactly, would your
> division library do that's better than what the compilers do?

Why, of course, it divides the programmer base into multiple camps whose code
does not interoperate.

Stanley Rice <> writes:
> Do you have to use >> operator to mimic the division if there is no
> divider operation in CPU?

No, division is not an optional language feature. The compiler
will do whatever it needs to do to generate code that produces the
correct answer.

The C division operator, like all C operators, is not defined in
terms of CPU instructions; it's defined in terms of the result it
must produce.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

On Dec 1, 2:11*am, Stanley Rice <hecong...@gmail.com> wrote:
> On Wednesday, November 30, 2011 1:53:31 PM UTC+8, arnuld wrote:


> > Yes, that casting fixes as per standard says. Thanks for that. Regarding
> > interview questions, once I was asked the value of i after this operation:
>
> > *i = i++;
>
> > I said its UB but the guy did not like my answer.
>
> Does UB stands for undefined behavior?

yes

On Nov 30, 4:23*pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> James Kuyper <jameskuy...@verizon.net> writes:
> > On 11/29/2011 11:42 PM, DDD wrote:
> > > On Nov 29, 1:02þÿÿýpm, arnuld <sunr...@invalid.address> wrote:
> > ...
> > >> What practical use is made of shifting bits ?
>
> > > * C language is used widely in embedded system. Bit operations are
> > > very common.
>
> > It would have been more responsive to explain what those bit operations
> > on embedded systems are actually used for.
>
> Shifting bits into the desired bit positions, normally.
> In that regard they're much like frying pans.
>
> Which are pans that are used for frying stuff in, FWIW.

yes but he's asking *why* would you want to bit shift.

Phil Carmody <> wrote:
> arnuld <> writes:

>> I have H&s5 here. Section 7.6.3 states "Applying the shift
>> operator >> is not portable when the left operand is negative,
>> signed value and the right operand is nonzero"

>> (1) My examlpes uses << rather than >>. Hence above rule does
>> not apply

Right. For the left shift operator negative left operands have
undefined behavior, not implementation-defined (don't ask me, why).

>> (2) H&S5 is using word "and" rather than word "or", which
>> directly means all three conditions in "negative, signed value
>> and right operand is zero" must be satisfied.

> The sentence was English prose, not in any formal logical
> notation. Different rules apply. The "and" implies that the
> statement is equally true for all of the things listed. "Or"
> would work at least as well, but there's a long tradition behind
> using "and" in such contexts.

There are only two conditions above (though the first is somewhat
redundant) and - moreover - using "or" would mean that a zero
shift count is not portable: in my copy of the standard it is
perfectly well defined (aside from negative left operands).

-- Ralf

Ralf Damaschke <> wrote:
>
> Right. For the left shift operator negative left operands have
> undefined behavior, not implementation-defined (don't ask me, why).

Because some CPUs have signed shift instructions that can generate
exceptions in that case (typically when the value shifted into the sign
bit doesn't match the value shifted out).
--
Larry Jones

These child psychology books we bought were such a waste of money.
-- Calvin's Mom