division by 7 without using division operator

[Dik T. Winter]

> In article <[email protected]>,

>
> ... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
> y * 0x500000001, which is congruent to y mod 2^32.

This works indeed works for multiples of 7. The same technique can
be used for all odd numbers.

 

[Christopher Layne]

how would you reply? What do you think the questioner really wants?

char *p = malloc(strlen(v[0]));

[...] ^^^^^^^^^

strcpy(p, v[0]);

^^^^^^^

 

[Christopher Layne]

in C90.


It's the systems that I doesn't know as makes me worry mostest.

And this is what answer you would expect to receive as your basis for what
determines the appropriate level of technicality for the candidate? Cmon.

If you state generally "what is wrong with this code?" you're not going to get
the prime answer as one focusing on the most subtle element in the first
place.

 

[Christopher Layne]

Even more off-topic:

I used a similar trick years ago in Minix, which had no function for
sleeping less than a second. Internally, it slept in units of 1/60
second, and carelessly multiplied the argument to sleep() by 60. By
passing a suitable large number, one could arrange for the overflow to
produce a desired fraction of a second:

This is such an awesomely unportable hack - I love it.

Richard 1, Minix 0.

 

[Richard Heathfield]

Christopher Layne said:

And this is what answer you would expect to receive as your basis for what
determines the appropriate level of technicality for the candidate?

I'd expect the successful candidate to be drawn from those who spotted it,
yes.

Cmon.

Hmm? If I'm hiring, I want someone who knows the language. Something wrong
with that?

If you state generally "what is wrong with this code?" you're not going to
get the prime answer as one focusing on the most subtle element in the
first place.

No, but the people I'd want to hire would at least mention it, possibly with
a little non-spoonfeedy prompting, like Ben did (although if I were hiring,
I wouldn't bother interviewing Ben - I'd just show him his reserved parking
spot and ask when he planned to start using it).

 

[Richard Heathfield]

CBFalconer said:

It also has a bug.

No, it doesn't.

If strlen(p) == 0, then q is pointing outside
any object,

....and that is a bug, yes. But the first assignment of q does not happen in
the while-loop under discussion. So the bug lies elsewhere.

and the comparison q < r is illegal.

The bug's already happened by then, because q already has an indeterminate
value. The loop itself is fine. Yes, you're right to point out that it can
break if code around it is broken, but that's true of just about all
working code, and so does not constitute a useful observation.

 

[Richard Heathfield]

Christopher Layne said:

how would you reply? What do you think the questioner really wants?

char *p = malloc(strlen(v[0]));

[...] ^^^^^^^^^

strcpy(p, v[0]);

^^^^^^^

Yes, well done - but, whilst your observation is an important one, it lacks
completeness. (Others have already provided more complete answers.)

 

[Richard Bos]

Go on, tell us. I assume it's that assert(pointer) is not allowed
(but works on all known systems).

If it is, it's a wrong gotcha. I would have disallowed the assertion on
the result of a runtime problem wholesale, and not have bothered to
check whether it would have been theoretically correct had it not been
an abomination.

Richard

 

[Richard Heathfield]

Richard Bos said:

If it is, it's a wrong gotcha.

No, it isn't.

I would have disallowed the assertion on
the result of a runtime problem wholesale, and not have bothered to
check whether it would have been theoretically correct had it not been
an abomination.

But you would have re-examined the assertion if prompted to do so. And then
you would have spotted what you call the "gotcha".

 

[micans]

Christopher Layne said:



I'd expect the successful candidate to be drawn from those who spotted it,
yes.


Hmm? If I'm hiring, I want someone who knows the language. Something wrong
with that?

Presumably you test something that is related to understanding
algorithms and
data structures as well.

Now what if the intersection of candidates that get the assert thingy
right with
those that have suitable knowledge of algorithms and data structures
is empty,
and both set differences are non-empty. Whom do you pick?

Of course there are still many more dimensions.

Stijn

 

[Richard Heathfield]

(e-mail address removed) said:

Presumably you test something that is related to understanding
algorithms and data structures as well.
Yes.

Now what if the intersection of candidates that get the assert thingy
right with those that have suitable knowledge of algorithms and data
structures is empty, and both set differences are non-empty. Whom do you
pick?

If no suitable candidate is forthcoming, what can you do? Either you look
for more candidates, or you make do with an unsuitable candidate, or you
leave the post vacant.

 

[Charlton Wilbur]

RH> (e-mail address removed) said:

RH> If no suitable candidate is forthcoming, what can you do?
RH> Either you look for more candidates, or you make do with an
RH> unsuitable candidate, or you leave the post vacant.

Or you consider which of the candidates can learn what you need them
to learn most easily -- the *degree* of suitability. The assert thing
is a small detail, that I myself didn't know because I've never run
into it. But Mr Heathfield's entire exercise will demonstrate whether
the candidate understands and values conforming code, and that's a lot
more important than whether the candidate knows the minutiae of the
Standard as regards functions he may never use.

Of course, quite a bit of this can be dealt with by asking for code
samples in advance.

Charlton

 

[Ike Naar]

If n >= 0 we can compute q>=0 and 0<=r<8 with n = 8*q + r using
we have q+r < n, so we can iterate.

Yes, that should work. Let's turn that into C code:

int divide_by_7(int x)
/*
precondition: 0 <= x
returns x / 7
*/
{
int q = 0, r = x + 1; /* invariant: x == 7 * q + r - 1 and 1 <= r */
while (8 <= r)
{
/* x == 7 * q + r - 1 and 8 <= r */
int u = r / 8, v = r % 8; /* use bit twiddling instead, if desired */
/* x == 7 * q + (8 * u + v) - 1
== 7 * (q + u) + (u + v) - 1 and 1 <= u and 0 <= v */
q += u;
r = u + v;
/* x == 7 * q + r - 1 and 1 <= r */
}
/* x == 7 * q + r - 1 and 0 <= r - 1 < 7 */
return q;
}

Cheers,
Ike

 

[Richard Heathfield]

Charlton Wilbur said:

RH> If no suitable candidate is forthcoming, what can you do?
RH> Either you look for more candidates, or you make do with an
RH> unsuitable candidate, or you leave the post vacant.

Or you consider which of the candidates can learn what you need them
to learn most easily -- the *degree* of suitability.

Yes. If you're prepared to take an unsuitable candidate, obviously you'll
want to take the /least/ unsuitable candidate.

 

[CBFalconer]

Charlton Wilbur said:

Yes. If you're prepared to take an unsuitable candidate, obviously
you'll want to take the /least/ unsuitable candidate.

Which brings up a very common C task - write a compare function.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Serve Laurijssen]

I'd expect the successful candidate to be drawn from those who spotted it,
yes.


Hmm? If I'm hiring, I want someone who knows the language. Something wrong
with that?


No, but the people I'd want to hire would at least mention it, possibly
with
a little non-spoonfeedy prompting, like Ben did (although if I were
hiring,
I wouldn't bother interviewing Ben - I'd just show him his reserved
parking
spot and ask when he planned to start using it).

I do think its taking it a bit too far.
I remember getting an interview question which showed this code:

enum E
{
X,
Y,
};
(and more ofcourse)

The question wasnt about that, but I happened to know that the last comma is
actually allowed so I decided to mention this. And there we went, the
interviewer was a C coder with 20 years of cranking out working code
experience under his belt and he kept insisting that this is not allowed.
You know how programmers can be I bet I'll get the same type of situation
if I'd tell about the assert.
Hmm might be interesting test, I work in a place with 15 or so C programmers
from beginner to very experienced. I wonder how many will spot the "error"

 

[Serve Laurijssen]

Richard Bos said:


No, it isn't.

well, using assert for things that can happen in production code too is also
not correct

 

[boa sema]

I do think its taking it a bit too far.
I remember getting an interview question which showed this code:

enum E
{
X,
Y,
};
(and more ofcourse)

The question wasnt about that, but I happened to know that the last comma is
actually allowed so I decided to mention this. And there we went, the
interviewer was a C coder with 20 years of cranking out working code
experience under his belt and he kept insisting that this is not allowed.
You know how programmers can be

I believe that he's right, not allowed in C89 but allowed in C99. My
authorative source for this is google and gcc ;-)
http://groups.google.com/group/comp...enumerator+list&rnum=1&hl=en#59940657c313d97a

Boa
[snip]

 

[Serve Laurijssen]

I believe that he's right, not allowed in C89 but allowed in C99. My
authorative source for this is google and gcc ;-)
http://groups.google.com/group/comp...enumerator+list&rnum=1&hl=en#59940657c313d97a

Yes so it is allowed....but here we go already. standard this year standard
that year and all about stuff that doesnt make you a better C coder. Like
with the assert(p)

 

[Richard Heathfield]

Serve Laurijssen said:

well, using assert for things that can happen in production code too is
also not correct

Right; as I have said dozens of times in this newsgroup, assert is for
validating code, not data.