Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #14026 > unrolled thread

Shifting bits

Back to article view | Back to comp.lang.c

Contents

  Shifting bits arnuld <sunrise@invalid.address> - 2011-11-29 05:02 +0000
    Re: Shifting bits Ian Collins <ian-news@hotmail.com> - 2011-11-29 18:20 +1300
      Re: Shifting bits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-11-29 17:39 +0000
        Re: Shifting bits arnuld <sunrise@invalid.address> - 2011-11-30 05:53 +0000
          Re: Shifting bits James Kuyper <jameskuyper@verizon.net> - 2011-11-30 06:57 -0500
          Re: Shifting bits Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-11-30 18:31 +0200
            Re: Shifting bits Ralf Damaschke <rwspam@gmx.de> - 2011-12-01 14:41 +0000
              Re: Shifting bits lawrence.jones@siemens.com - 2011-12-01 13:58 -0500
          Re: Shifting bits Stanley Rice <heconghui@gmail.com> - 2011-11-30 18:11 -0800
            Re: Shifting bits Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-01 02:21 -0800
    Re: Shifting bits Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-11-29 03:03 -0800
    Re: Shifting bits "BartC" <bc@freeuk.com> - 2011-11-29 12:04 +0000
      Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-29 05:44 -0800
      Re: Shifting bits arnuld <sunrise@invalid.address> - 2011-11-30 05:58 +0000
    Re: Shifting bits gwowen <gwowen@gmail.com> - 2011-11-29 08:21 -0800
    Re: Shifting bits DDD <1983ddd@gmail.com> - 2011-11-29 20:42 -0800
      Re: Shifting bits James Kuyper <jameskuyper@verizon.net> - 2011-11-30 00:11 -0500
        Re: Shifting bits Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-11-30 18:23 +0200
          Re: Shifting bits Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-01 02:23 -0800
    Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 05:35 -0800
      Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 18:43 +0000
        Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 13:33 -0800
          Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 21:41 +0000
            Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 14:40 -0800
              Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 22:36 +0000
                Re: Shifting bits Lauri Alanko <la@iki.fi> - 2011-12-01 02:02 +0000
                  Re: Shifting bits Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-12-01 09:30 -0500
                Re: Shifting bits Kaz Kylheku <kaz@kylheku.com> - 2011-12-01 02:50 +0000
                  Re: Shifting bits Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-12-01 09:00 -0500
        Re: Shifting bits Robert Wessel <robertwessel2@yahoo.com> - 2011-11-30 17:09 -0600
      Re: Shifting bits Stanley Rice <heconghui@gmail.com> - 2011-11-30 18:13 -0800
        Re: Shifting bits Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-11-30 19:44 -0700
        Re: Shifting bits Keith Thompson <kst-u@mib.org> - 2011-11-30 19:20 -0800
        Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-12-01 20:08 +0000
        Re: Shifting bits Kaz Kylheku <kaz@kylheku.com> - 2011-12-01 21:34 +0000
    Re: Shifting bits gordonb.slo24@burditt.org (Gordon Burditt) - 2011-12-01 01:24 -0600

Page 2 of 2 — ← Prev page 1 [2]

#14090

On 2011-11-30, 88888 Dihedral <dihedral88888@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-nospam@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.

[toc] | [prev] | [next] | [standalone]

#14095

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 ?

[toc] | [prev] | [next] | [standalone]

#14099

On 2011-11-30, 88888 Dihedral <dihedral88888@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.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@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.

[toc] | [prev] | [next] | [standalone]

#14104

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?

  

[toc] | [prev] | [next] | [standalone]

#14105

On 2011-11-30, 88888 Dihedral <dihedral88888@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?

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@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.

[toc] | [prev] | [next] | [standalone]

#14117

In article <slrnjdddj9.l6p.usenet-nospam@guild.seebs.net>,
Seebs  <usenet-nospam@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

[toc] | [prev] | [next] | [standalone]

#14159

Lauri Alanko <la@iki.fi> writes:

> In article <slrnjdddj9.l6p.usenet-nospam@guild.seebs.net>,
> Seebs  <usenet-nospam@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.

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.

-- 
Lowell Gilbert, embedded/networking software engineer
	 http://be-well.ilk.org/~lowell/

[toc] | [prev] | [next] | [standalone]

#14121

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

[toc] | [prev] | [next] | [standalone]

#14158

Kaz Kylheku <kaz@kylheku.com> writes:

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

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/

[toc] | [prev] | [next] | [standalone]

#14106

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

>On 2011-11-30, 88888 Dihedral <dihedral88888@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.

[toc] | [prev] | [next] | [standalone]

#14119

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

[toc] | [prev] | [next] | [standalone]

#14120

Stanley Rice <heconghui@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.

[toc] | [prev] | [next] | [standalone]

#14127

Stanley Rice <heconghui@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) kst-u@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"

[toc] | [prev] | [next] | [standalone]

#14182

On 2011-12-01, Stanley Rice <heconghui@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.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@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.

[toc] | [prev] | [next] | [standalone]

#14187

On 2011-12-01, Stanley Rice <heconghui@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.

[toc] | [prev] | [next] | [standalone]

#14134

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

  

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web