Shifting bits

[Lauri Alanko]

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]

[...] 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?

 

[Stanley Rice]

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

 

[Joe Pfeiffer]

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]

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]

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.

 

[Nick Keighley]

On Wednesday, November 30, 2011 1:53:31 PM UTC+8, arnuld wrote:




Does UB stands for undefined behavior?

yes

 

[Nick Keighley]

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.

 

[Ralf Damaschke]

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

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

 

[lawrence.jones]

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

 

[Seebs]

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

 

[Kaz Kylheku]

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.