Shifting bits

[arnuld]

Here is another C interview question, what this C program does. I see it
compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
escape character for hexadecimal notation. Section 7.6.3 says << is
shift-op which shifts bits to left. Type of result after shift-op
returns is the converted left operand and result is not an lvalue.

I never really understood how shifting bits works. I mean, how will I
know -1 will return -16 after shifting 4 bits (if you replace %x with
with %d, you get -16). Is it possible to know in advance e.g what
shifting 8 bits to left on 100 will result.

What practical use is made of shifting bits ?


#include <stdio.h>

int main(void)
{
printf("%x\n", -1<<4);

return 0;
}

=============== OUTPUT ====================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra interview-2.c
/home/arnuld/programs/C $ ./a.out
fffffff0
/home/arnuld/programs/C $






--
arnuld
http://LispMachine.Wordpress.com

[Ian Collins]

On 11/29/11 06:02 PM, arnuld wrote:
> Here is another C interview question, what this C program does. I see it
> compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
> escape character for hexadecimal notation.

The term is "format specifier", not escape character. An escape
character is something completely different.

> Section 7.6.3 says<< is
> shift-op which shifts bits to left. Type of result after shift-op
> returns is the converted left operand and result is not an lvalue.
>
> I never really understood how shifting bits works. I mean, how will I
> know -1 will return -16 after shifting 4 bits (if you replace %x with
> with %d, you get -16). Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.

You won't. I believe sifting a signed integer and this the code is
undefined.

> What practical use is made of shifting bits ?

It's very common when you want to extract bits form a longer type, or
assign a value to high order bits. It used to be used in place of
multiplication or division by a power of two (shift instructions were
typically faster).

--
Ian Collins

[Malcolm McLean]

On Nov 29, 7:02 am, arnuld <sunr...@invalid.address> wrote:
>
> What practical use is made of shifting bits ?
>

They were used as a cheap divide or multiply by a power of two. It's
the binary equivalent of adding or deleting a nought to muliply by
ten. This is now obsolete on all but the simplest compilers for small
systems.

However shifts are still used if you want to treat a variable as an
array of bits rather than a number. An example is a stream of
compressed data using Huffman codes. No Huffman code may be a prefix
of another Huffman code. By extracting data one bit at a time, you
can build up the code until you come to a leaf, and thus decompress
the data.

Another example is packing 24 bit rgb values into a 32 bit int. That
means that you can pass a 24 bit colour in one argument, which is
often clearer. circle(x, y, r, color) is more convenient than
circle(x, y, r, red, green, blue).

[BartC]

"arnuld" <sun...@invalid.address> wrote in message
news:4ed46774$0$295$1472...@news.sunsite.dk...

>Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.

Since they are both constants, then yes. And the result will be 25600
(effectively 100 * 2**8).

#include <stdio.h>

int main(void) {
int i;

for (i=0; i<=16; ++i)
printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s", 100<<i);
}

Notice each extra shift multiplies by 2.

> What practical use is made of shifting bits ?

Just look for "<<" or ">>" in any large body of code, and see what people
use it for. Sometimes they can be replaced by multiply and divide, but
shifts are usually more to the point, because they use N rather than 2**N.

--
Bartc

[88888 Dihedral]

Didn't you ever implement cordic before in C?

That was the homework not difficult in C who had to learn how to write
an assembler and a restricted compiler of some fat standard.

[gwowen]

On Nov 29, 5:02 am, arnuld <sunr...@invalid.address> wrote:

> What practical use is made of shifting bits ?

Besides the other answers here - CRC32 and the like are usually
defined/implemented in terms of bitshifts.

Also they're good in the abstract for explaining the concept of
sensitive-dependence-on-initial-conditions.

[Ben Bacarisse]

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.

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

printf("%x\n", (unsigned)-1<<4);

would have fixed both. Who sets these interview questions?

<snip>
--
Ben.

[DDD]

On Nov 29, 1:02 pm, arnuld <sunr...@invalid.address> wrote:
> Here is another C interview question, what this C program does. I see it
> compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
> escape character for hexadecimal notation. Section 7.6.3 says << is
> shift-op which shifts  bits to left. Type of result after shift-op
> returns is the converted left operand and result is not an lvalue.
>
> I never really understood how shifting bits works. I mean, how will I
> know -1 will return -16 after shifting 4 bits (if you replace %x with
> with %d, you get -16). Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.
>
> What practical use is made of shifting bits ?
>

C language is used widely in embedded system. Bit operations are
very common.

[James Kuyper]

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.
--
James Kuyper

[arnuld]

> 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.




--
arnuld
http://LispMachine.Wordpress.com

[arnuld]

> On Tue, 29 Nov 2011 12:04:16 +0000, BartC wrote:

> Since they are both constants, then yes. And the result will be 25600
> (effectively 100 * 2**8).
>
> #include <stdio.h>
>
> int main(void) {
> int i;
>
> for (i=0; i<=16; ++i)
> printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s",
> 100<<i);
> }
>
> Notice each extra shift multiplies by 2.

great. I even modified the example to use right shifting and came to see
value was going down as if divided by 2 each time, till it becomes zero
and no longer decreases. It fits to what exactly n156 says:

Section 6.5.7: right bit-shifting results in integral part of the
quotient Left-Operand/2^Right-Operand, unless Left-Operand is negative.






--
arnuld
http://LispMachine.Wordpress.com

[James Kuyper]

On 11/30/2011 12:53 AM, arnuld wrote:
...

> 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

It should say something similar, but slightly different, for <<. See
below for details.

> (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.

H&SS is using the word portable to cover two different concepts from the
C standard: undefined behavior, and an implementation-defined value for
the result. Both get in the way of portability, but the latter is far
less dangerous of a problem than the former.

An operand can't be negative without being signed, so that part is
correct, but as far as the standard is concerned, the value is
implementation-defined even if the right operand is zero, so that part
is technically wrong. However, they may be right in describing the
actual behavior of most implementations.

Here's what the standard says about those issues:

For both << and >>, it is undefined behavior if the right operand is
negative or greater than the width of the promoted left operand.

For E1 << E2, the behavior is also undefined if E1 is negative, or if E1
* 2^E2 is not representable in the result type.

For E1 >> E2, the value of the result is implementation defined if E1 is
negative.

...

>> 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 :)

It's not much of a secret: 7.19.6.3 defines the behavior of
printf(format, ...) as equivalent to fprintf(stdout, format, ...).
7.19.6.1p8 describes the requirements for using fprintf() with a format
string that contains the '%x' specifier. So should any decent standard
library reference. This isn't a particularly new feature either; I think
it's older than the C standard.
--
James Kuyper

[88888 Dihedral]

I think I am not the only one interested in using arm family riscs that do
not have multipliers and dividers. Billions of cpus could run linux even
without a divider available in circuits every year. A division library is required. Of course, this kind of jobs are not for inexperienced c programmers.

[Phil Carmody]

James Kuyper <james...@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.

Phil
--
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[Phil Carmody]

arnuld <sun...@invalid.address> writes:
> > 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.

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.

...

> 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.

You're better off not working for such a company.

[Seebs]

On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> I think I am not the only one interested in using arm family riscs that do
> not have multipliers and dividers.

I am not sure I've yet seen one without a multiplier, although certainly
there's some without dividers.

> Billions of cpus could run linux even
> without a divider available in circuits every year.

They do.

> A division library is required.

Boy, sure would be nice if compiler writers had solved this a decade or
two back.

> Of course, this kind of jobs are not for inexperienced c programmers.

It's long since been done.

-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

[88888 Dihedral]

On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:
> On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> > I think I am not the only one interested in using arm family riscs that do
> > not have multipliers and dividers.
>
> I am not sure I've yet seen one without a multiplier, although certainly
> there's some without dividers.
>
> > Billions of cpus could run linux even
> > without a divider available in circuits every year.
>
> They do.
>
> > A division library is required.
>
> Boy, sure would be nice if compiler writers had solved this a decade or
> two back.
>
> > Of course, this kind of jobs are not for inexperienced c programmers.
>
> It's long since been done.
>

Did you profile those so slow ?

[Seebs]

On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:
>> On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
>> > I think I am not the only one interested in using arm family riscs that do
>> > not have multipliers and dividers.

>> Boy, sure would be nice if compiler writers had solved this a decade or
>> two back.

>> It's long since been done.

> Did you profile those so slow ?

No, I didn't, because in all the thousands of ARM builds I've run, it's
never, once, been an issue. To put it in perspective, while I am vaguely
aware that some ARM hardware lacks hardware divide, I couldn't even tell
you which of the couple dozen ARM chips we actively support are affected,
because it has never, ever, been a measurable issue.

Compilers are already well aware of the need for efficient division, and if
I had to bet on a competition between the gcc ARM port maintainers and you
for producing an efficient divider, I would bet on the gcc folks.

[88888 Dihedral]

On Thursday, December 1, 2011 5:41:10 AM UTC+8, Seebs wrote:
> On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> > On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:

> >> On 2011-11-30, 88888 Dihedral <dihe...@googlemail.com> wrote:
> >> > I think I am not the only one interested in using arm family riscs that do
> >> > not have multipliers and dividers.
>
> >> Boy, sure would be nice if compiler writers had solved this a decade or
> >> two back.
>
> >> It's long since been done.
>
> > Did you profile those so slow ?
>
> No, I didn't, because in all the thousands of ARM builds I've run, it's
> never, once, been an issue. To put it in perspective, while I am vaguely
> aware that some ARM hardware lacks hardware divide, I couldn't even tell
> you which of the couple dozen ARM chips we actively support are affected,
> because it has never, ever, been a measurable issue.
>
> Compilers are already well aware of the need for efficient division, and if
> I had to bet on a competition between the gcc ARM port maintainers and you
> for producing an efficient divider, I would bet on the gcc folks.
>
> -s
> --
> Copyright 2011, all wrongs reversed. Peter Seebach / usenet...@seebs.net
> http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
> http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
> I am not speaking for my employer, although they do rent some of my opinions.

Ok, you or your boss paid the tax to the compiler writers.

How about a new cpu without a divider or a multiplier, e.g. ARM7?

[Seebs]

On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
> Ok, you or your boss paid the tax to the compiler writers.

This doesn't mean anything.

> How about a new cpu without a divider or a multiplier, e.g. ARM7?

What about it?

Seriously, I can't comprehend the issue here. Obviously, compilers have
been implementing multiplication and division successfully on these chips
for decades, same as with many other chips which omit some operations, same
as many compilers have implemented 64-bit integer support on chips with no
64-bit hardware.

It's a pretty well-understood problem.

You propose to create a "division library". What, exactly, would your
division library do that's better than what the compilers do? Are you a
much more skilled optimizer than any of the people who have ever worked
on this? Do you even know what they've done already?

Let's start from the top:

What do you think the problem is? Is division slow? How slow is it? How
did you measure it? What is your reason for believing you can do better?

[Robert Wessel]

On 30 Nov 2011 18:43:57 GMT, Seebs <usenet...@seebs.net> wrote:

>On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> wrote:
>> I think I am not the only one interested in using arm family riscs that do
>> not have multipliers and dividers.
>
>I am not sure I've yet seen one without a multiplier, although certainly
>there's some without dividers.

Not sure if any of the current ones do, maybe some of the smallest
embedded ones, but a couple of the early RISCs had "multiply step",
which you needed several iterations of to get a complete multiply.

Both SPARC and MIPS did that (although both have long since added
proper multiply instructions), perhaps others as well.

[Lauri Alanko]

In article <slrnjdddj9.l6p...@guild.seebs.net>,

Seebs <usenet...@seebs.net> 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

[Stanley Rice]

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

[Stanley Rice]

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

[Joe Pfeiffer]

Stanley Rice <heco...@gmail.com> 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.

[Kaz Kylheku]

On 2011-11-30, Seebs <usenet...@seebs.net> wrote:
> On 2011-11-30, 88888 Dihedral <dihedr...@googlemail.com> 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.

[Keith Thompson]

Stanley Rice <heco...@gmail.com> 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) ks...@mib.org <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"

[Gordon Burditt]

> I never really understood how shifting bits works. I mean, how will I
> know -1 will return -16 after shifting 4 bits (if you replace %x with
> with %d, you get -16). Is it possible to know in advance e.g what
> shifting 8 bits to left on 100 will result.

If you understand how two's complement binary numbers are represented,
it's not that difficult. 100 << 8 equals 25600, assuming you are
calculating with variables sufficiently wide to hold the numbers
(and int is guaranteed to hold those numbers).

Note: C doesn't guarantee that your machine uses two's complement.
It could use one's complement or sign/magnitude. You should know
what those are but pretty much all of the machines you'll actually
run into use two's complement.

> What practical use is made of shifting bits ?

Shifting has a number of uses:

- It's sometimes an optimization for multiplication (left shifts)
or division (right shifts). You have to be careful with this:
some optimizations work only for non-negative numbers that don't
overflow. If you write multiplication and division (especially
by power-of-two constants), the compiler may generate shifts
instead, or do the math at compile time.

- Some data (particularly i/o registers for peripherals on embedded
systems, and some fields in network packet headers) is defined
as a bunch of separate fields stored within an integer. Packing
and unpacking this data may easily be done with shifting and
masking. (Why not use bit fields? Because there's no portable
way to ensure that a given C bit field declaration actually matches
the hardware, and if it actually does, that the next version of
the compiler will agree.)

- Serial data transmission inherently involves shifting data and
sending one bit at a time, and receiving it involves picking up
that data and packing it into characters. Often this is done by
hardware, but some embedded machines don't have the hardware and
use a "software UART" replacement.

- Some algorithms, especially in cryptography and data compression,
are defined in terms of bit shifts or packing a bunch of
variable-bit-length data elements together. This also includes
'uuencode' and the process of converting from Unicode code points
to UTF-8.

- Certain conversion algorithms, like taking a printable octal or
hex number and putting its value into an int, just involve it
naturally. You just convert the printable characters to 3-bit
or 4-bit fields and pack them together.

- You can combine a bunch of miscellaneous flags into one integer
value, and access them independently. The common octal representation
of UNIX file permissions is one example of this.

- Sometimes one is short on storage and wants to make a big bit array.
You pick some unit of storage, say, unsigned short, and assume it
has at least 16 bits. Then you can access any individual bit N in
"bigarray", an array of unsigned shorts, like this:
(bigarray[(N)/16] & (1 << ((N)%16)))
which is zero or nonzero depending on the given bit.
This can be rewritten:
(bigarray[(N)>>4] & (1 << ((N) & 0x0f)))

[Nick Keighley]

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.

[Nick Keighley]

yes

[Lowell Gilbert]

Not even that, because a fairly trivial (and automatable) precompilation
step translates back and forth. I'm with Seebs: I can't see anything
useful *or* *otherwise* that is actually accomplished.
--
Lowell Gilbert, embedded/networking software engineer
http://be-well.ilk.org/~lowell/

[Lowell Gilbert]

Maybe it's just the myopia of my custom-hardware-centric experience, but
I don't see cases where that works; what kind of hash function intended
for software-only implementation uses a division but not a remainder?

Assuming it does work (and I'm far enough out of my area that it
wouldn't surprise me), I still don't think the library approach is all
that useful for general division. The library has no knowledge that the
compiler wouldn't, so the programmer needs to provide a priori knowledge
to allow the optimization. You end up with two implementations of the
division operation, and whether the implementations of each are hidden
away in a library or not, the programmer is still coding an explicit
choice between them at the point of use.

[Ralf Damaschke]

Phil Carmody <thefatphi...@yahoo.co.uk> wrote:

> arnuld <sun...@invalid.address> 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

[lawrenc...@siemens.com]

Ralf Damaschke <rws...@gmx.de> 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

[Seebs]

On 2011-12-01, Stanley Rice <heco...@gmail.com> wrote:
> Do you have to use >> operator to mimic the division if there is
> no divider operation in CPU?

No. The compiler will generate code to handle division, however this needs
to be done.

[Kaz Kylheku]

On 2011-12-01, Stanley Rice <heco...@gmail.com> wrote:

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

That won't help you since the >> operator doesn't mimic division, except for
the special case of positive integers being divided by powers of two.

You do not have to work around missing CPU instructions in C. You're not
working in assembly language, after all.

You do have to work around missing or broken C language features.

If you have to work with some compiler with a broken or missing division, and
you require division, you will have to work around that. (Before rolling
your own division, the first thing to look for in such a situation is whether
the standard div function is present in the implementation's standard library).

But it is not expected that an arithmetic operator be broken or missing, even
if the target CPU doesn't have a division instruction. Any reasonably mature C
implementation should have division (and it has to in order to be called
standard-conforming).

So, don't worry about it. Should you encounter this situation (likely never),
you can "cross that bridge when you get to it", as the saying goes.