Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Shifting bits

Reply
Thread Tools

Shifting bits

 
 
Lauri Alanko
Guest
Posts: n/a
 
      12-01-2011
In article <(E-Mail Removed)>,
Seebs <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Stanley Rice
Guest
Posts: n/a
 
      12-01-2011
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 <(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
 
Stanley Rice
Guest
Posts: n/a
 
      12-01-2011
Do you have to use >> operator to mimic the division if there is no divider operation in CPU?
 
Reply With Quote
 
Joe Pfeiffer
Guest
Posts: n/a
 
      12-01-2011
Stanley Rice <(E-Mail Removed)> 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.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      12-01-2011
On 2011-11-30, Seebs <(E-Mail Removed)> wrote:
> On 2011-11-30, 88888 Dihedral <(E-Mail Removed)> 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.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      12-01-2011
Stanley Rice <(E-Mail Removed)> 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) http://www.velocityreviews.com/forums/(E-Mail Removed) <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"
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      12-01-2011
On Dec 1, 2:11*am, Stanley Rice <(E-Mail Removed)> 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
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      12-01-2011
On Nov 30, 4:23*pm, Phil Carmody <(E-Mail Removed)>
wrote:
> James Kuyper <(E-Mail Removed)> writes:
> > On 11/29/2011 11:42 PM, DDD wrote:
> > > On Nov 29, 1:02pm, arnuld <(E-Mail Removed)> 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.


 
Reply With Quote
 
Ralf Damaschke
Guest
Posts: n/a
 
      12-01-2011
Phil Carmody <(E-Mail Removed)> wrote:
> arnuld <(E-Mail Removed)> 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
 
Reply With Quote
 
lawrence.jones@siemens.com
Guest
Posts: n/a
 
      12-01-2011
Ralf Damaschke <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Shifting bits jacob navia C Programming 6 10-28-2009 08:45 AM
Shifting unsigned long long values by 64 bits krunalb C Programming 10 01-23-2007 02:47 PM
shifting bits, shift 32 bits on 32 bit int GGG C++ 10 07-06-2006 06:09 AM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM
win XP 32 bits on a 64 bits processor.. Abbyss Computer Support 3 11-13-2003 12:39 AM



Advertisments