432,028 Members | 1,092 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,028 IT Pros & Developers. It's quick & easy.

# division by 7 without using division operator

 P: n/a Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. Any comments ? Feb 1 '07 #1
94 Replies

 P: n/a

 P: n/a kr***********@gmail.com wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? Divide by and truncate to integral result? or See if a number is divisible by 7 with no remainder? Feb 1 '07 #3

 P: n/a kr***********@gmail.com wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. Any comments ? (num >3) + 1 seems to work? Feb 1 '07 #4

 P: n/a How ? For me it sometimes doesn't work. For example 26/7 should give us 3. 26 is 11010 in binary and a right shift of 3 would give us 3 (binary 11) and adding 1 changes the result. Correct me if I am wrong. Thanks (num >3) + 1 seems to work? Feb 1 '07 #5

 P: n/a kr***********@gmail.com wrote: > Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. If you are multiplying (not dividing) then: n = 8 * n - n; or n = (n << 3) - n; /* The latter only for unsigned n. */ otherwise he was asking you to build a division routine. -- "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 Feb 1 '07 #6

 P: n/a kr***********@gmail.com writes: How would you divide a number by 7 without using division operator ? I'd look up the appropriate section in _Hacker's Delight_, which not only gives the details of how to transform division by this particular constant into multiplication followed by a correction, but also explains how to figure out how to divide by any desired constant using the same method. With proofs. This same question came up, either here or in comp.programming, within the last month or so. Try Google Groups to find the earlier discussion. -- "Some people *are* arrogant, and others read the FAQ." --Chris Dollin Feb 1 '07 #7

 P: n/a kr***********@gmail.com wrote: How ? For me it sometimes doesn't work. For example 26/7 should give us 3. 26 is 11010 in binary and a right shift of 3 would give us 3 (binary 11) and adding 1 changes the result. Correct me if I am wrong. Thanks >(num >3) + 1 seems to work? I was going on the assumption that you knew the value to be a multiple of 7 to begin with... but as someone else pointed out already, the +1 will not be sufficient as the original number grows. I was only looking at "small" multiples of 7. 7, 14, 21, 28, 35, 42, 49... It also wasn't clear to me if he wanted exact results or approximations. Being that EA Sports is a 3d gaming house, I kinda figured approximation is what they were looking for. Jeff Feb 1 '07 #8

 P: n/a kr***********@gmail.com writes: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? [...] In a number system with wraparound semantics, such as C's unsigned integer types (or signed integer types on most two's complement implementations), you can often replace division by a constant with multiplication by a constant. I don't know the details of figuring out what constant to use, but some compilers are smart enough to do this. If you can write a small program that divides a number by 7 and examine the generated assembly listing, you might see a multiplication instruction rather than a division instruction. gcc does this; I haven't studied the assembly listing enough to understand what's going on, but you might want to. The fact that compilers can perform this optimization -- and, perhaps more important, can decide when it is and isn't necessary -- is a good reason *not* to bother doing this yourself. Just divide by 7; that's what the "/" operator is for. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Feb 1 '07 #9

 P: n/a On Jan 31, 8:03 pm, krypto.wiz...@gmail.com wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. Any comments ? For integers, here's a good way of doing it with 32 bit x86 assembly: ; uint32_t udiv_7 (uint32_t eax) cmp eax, 0ccccccd1h adc eax, 0ffffffffh mov edx, 092492493h mul edx shr edx, 2 ; value edx The problem is that it requires a widening multiply which the C standard does not have, so there is no easy way of translating this to C. For floating point, obviously you would want to multiply by the reciprocal of 7. You might then check nearby floating point numbers (some that is apparently possible in C99, or if you can assume IEEE-754) to see if they are better approximations by multiplying the 7 back. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ Feb 1 '07 #10

 P: n/a kr***********@gmail.com said: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? Easy: q = exp(log(d) - log(7)); I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. I'd have replied that, unless we have some criteria by which to judge, that's not better, merely different. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 1 '07 #11

 P: n/a kr***********@gmail.com wrote: > How ? For me it sometimes doesn't work. For example 26/7 should give us 3. 26 is 11010 in binary and a right shift of 3 would give us 3 (binary 11) and adding 1 changes the result. Correct me if I am wrong. (num >3) + 1 seems to work? "right shift of 3" is exactly equal to "division by 8" (7 >3 == 0) (8 >3 == 1) (15 >3 == 1) (16 >3 == 2) -- pete Feb 1 '07 #12

 P: n/a pete wrote: kr***********@gmail.com wrote: > How ? For me it sometimes doesn't work.For example 26/7 should give us 3.26 is 11010 in binary and a right shift of 3 would give us 3 (binary11) and adding 1 changes the result.Correct me if I am wrong. >>(num >3) + 1 seems to work? "right shift of 3" is exactly equal to "division by 8" (7 >3 == 0) (8 >3 == 1) (15 >3 == 1) (16 >3 == 2) I know - it was a "rough estimation" (and also hence the +1) anyways, this is a little better: (x >2) - (x >3) + (x >6) the first 2 terms are a /8, rounded up. (7 >2) - (7 >3) + (7 >6) == 1 - 0 + 0 == 1 (8 >2) - (8 >3) + (8 >6) == 2 - 1 + 0 == 1 (15 >2) - (15 >3) + (15 >6) == 3 - 1 + 0 == 2 (16 >2) - (16 >3) + (16 >6) == 4 - 2 + 0 == 2 (21 >2) - (21 >3) + (21 >6) == 5 - 2 + 0 == 3 (28 >2) - (28 >3) + (28 >6) == 7 - 3 + 0 == 4 (35 >2) - (35 >3) + (35 >6) == 8 - 4 + 0 == 4 :( .... (100 >2) - (100 >3) + (100 >6) == 25 - 12 + 1 = 14 Feb 1 '07 #13

 P: n/a In article , Richard Heathfield Last month I appeared for an interview with EA sports and they askedme this question.How would you divide a number by 7 without using division operator ? >Easy: q = exp(log(d) - log(7)); The interviewer might well have replied that the purpose of the interview was not merely to determine your logical skills, but your ability to solve problems that you would be given in the course of your job; and they might not always be expressed precisely, so an ability to infer what the questioner really wants would be an advantage. An insistence on treating questions literally is not always regarded as a virtue outside comp.lang.c. -- Richard -- "Consideration shall be given to the need for as many as 32 characters in some alphabets" - X3.4, 1963. Feb 1 '07 #14

 P: n/a kr***********@gmail.com wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. Pick your accuracy: a: the required multiplication b: the resulting factor from the operation + (a>>3) a=0.142857 b=0.125 error=1.7857% + (a>>3) + (a>>6) a=0.142857 b=0.140625 error=0.2232% + (a>>3) + (a>>6) + (a>>9) a=0.142857 b=0.142578 error=0.0279% + (a>>3) + (a>>6) + (a>>9) + (a>>12) a=0.142857 b=0.142822 error=0.0035% + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) a=0.142857 b=0.142853 error=0.0004% + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18) a=0.142857 b=0.142857 error=0.0001% + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18) + (a>>21) a=0.142857 b=0.142857 error=0.0000% -- :wq ^X^Cy^K^X^C^C^C^C Feb 1 '07 #15

 P: n/a On Wed, 31 Jan 2007 20:03:38 -0800, krypto.wizard wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? > If n >= 0 we can compute q>=0 and 0<=r<8 with n = 8*q + r using >and &. So n = 7*q + q+r hence n/7 = q + (q+r)/7. For n>7 we have q+r < n, so we can iterate. Duncan Feb 1 '07 #16

 P: n/a Jeffrey Stedfast

 P: n/a Richard Tobin said: In article , Richard Heathfield >Last month I appeared for an interview with EA sports and they askedme this question.How would you divide a number by 7 without using division operator ? >>Easy: q = exp(log(d) - log(7)); The interviewer might well have replied that the purpose of the interview was not merely to determine your logical skills, but your ability to solve problems that you would be given in the course of your job; Yup - and this solution works just fine. and they might not always be expressed precisely, so an ability to infer what the questioner really wants would be an advantage. An insistence on treating questions literally is not always regarded as a virtue outside comp.lang.c. I think you're arguing from prejudice - that is, I believe you've made an assumption about the interviewer's expectations. That isn't necessarily a wise strategy. To give you a different example, if the interviewer asked you what was wrong with this program: #include #include #include #include main(int c, char **v) { char *p = malloc(strlen(v)); char *q, *r; assert(p); strcpy(p, v); q = p; r = q + strlen(p) - 1; while(q < r) { char c = *q; *q++ = *r; *r-- = c; } puts(p); } how would you reply? What do you think the questioner really wants? -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 1 '07 #18

 P: n/a In article <87************@blp.benpfaff.org>, Ben Pfaff If x is a unsigned 32-bit integer that is a multiple of 7, thenyou can divide by 7 with simply: x *= 0xb6db6db7; .... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is y * 0x500000001, which is congruent to y mod 2^32. 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: /* Sleep for t milliseconds (resolution 1/15 second). Assumes 32-bit ints. */ void msleep(t) int t; { int s, f; f = (t * 15 + 500) / 1000; s = f / 15; f = f % 15; sleep(s + 787410671 * f); } -- Richard -- "Consideration shall be given to the need for as many as 32 characters in some alphabets" - X3.4, 1963. Feb 1 '07 #19

 P: n/a In article , Richard Heathfield and they might not always be expressed precisely, so anability to infer what the questioner really wants would be anadvantage. An insistence on treating questions literally is notalways regarded as a virtue outside comp.lang.c. >I think you're arguing from prejudice - that is, I believe you've made anassumption about the interviewer's expectations. That isn't necessarily awise strategy. Nonetheless, I think my assumption is likely to be right. Obviously the best thing to do would be to verify that assumption before answering the question. Just giving the answer you suggested does not seem like a good strategy. >To give you a different example, if the interviewer askedyou what was wrong with this program:#include #include #include #include main(int c, char **v){ char *p = malloc(strlen(v)); char *q, *r; assert(p); strcpy(p, v); q = p; r = q + strlen(p) - 1; while(q < r) { char c = *q; *q++ = *r; *r-- = c; } puts(p);}how would you reply? "You aren't Richard Heathfield by any chance, are you?" >What do you think the questioner really wants? I would assume that the interviewer realised that there were several errors of varying seriousness, and that he wanted me to list them. Of course, I might be wrong, but such is life. -- Richard -- "Consideration shall be given to the need for as many as 32 characters in some alphabets" - X3.4, 1963. Feb 1 '07 #20

 P: n/a Richard Heathfield =(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} Feb 1 '07 #21

 P: n/a Richard Heathfield #include #include No such standard header. #include main(int c, char **v) Needs a return type, especially in C99. It's kind to use the customary names argc and argv for the arguments. { char *p = malloc(strlen(v)); argc == 0 is permissible under the C standard, in which case argv is NULL, so this yields undefined behavior. char *q, *r; assert(p); An assertion is not an appropriate way to check for failures that can actually occur in practice. strcpy(p, v); Didn't allocate enough memory for this. q = p; r = q + strlen(p) - 1; If argv == '\0', this attempts to back up past the beginning of an allocated object, yielding undefined behavior. while(q < r) { char c = *q; *q++ = *r; *r-- = c; } I'm not going to bother to analyze this. Likely problems include stepping off the beginning or the end of the array. puts(p); } Should return a value, probably 0 or EXIT_SUCCESS. -- "...deficient support can be a virtue. It keeps the amateurs off." --Bjarne Stroustrup Feb 1 '07 #23

 P: n/a Ben Pfaff said: Richard Heathfield #include #include #include No such standard header. This was actually a genuine typo, which I spotted and was about to correct when I thought, blow it, why not leave it in? I should actually have fixed it, on reflection, as it would have left the program in a compilable state despite the errors, and that would have clued the candidate in to the fact that this is supposed to be C90 code (see below). > >#include main(int c, char **v) Needs a return type, especially in C99. Actually, that was a clue that this was C90, and this is relevant. > while(q < r) { char c = *q; *q++ = *r; *r-- = c; } I'm not going to bother to analyze this. Likely problems include stepping off the beginning or the end of the array. Actually, had you bothered to analyse it, you would have found that it's about the only part of the program that is actually correct. :-) Alas, you didn't spot the (admittedly C90-only, and there's a clue for you if ever there was one) subtlety. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 1 '07 #24

 P: n/a Richard Heathfield

 P: n/a In article , Richard Heathfield Most were obvious, of course, but there was a subtlety in there that I wouldexpect only an expert to spot. Go on, tell us. I assume it's that assert(pointer) is not allowed (but works on all known systems). -- Richard -- "Consideration shall be given to the need for as many as 32 characters in some alphabets" - X3.4, 1963. Feb 1 '07 #26

 P: n/a On Feb 1, 11:56 am, Ico >3) a=0.142857 b=0.125 error=1.7857% + (a>>3) + (a>>6) a=0.142857 b=0.140625 error=0.2232% + (a>>3) + (a>>6) + (a>>9) a=0.142857 b=0.142578 error=0.0279% + (a>>3) + (a>>6) + (a>>9) + (a>>12) a=0.142857 b=0.142822 error=0.0035%

 P: n/a "Richard Tobin" , Ben Pfaff >If x is a unsigned 32-bit integer that is a multiple of 7, thenyou can divide by 7 with simply: x *= 0xb6db6db7; ... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is y * 0x500000001, which is congruent to y mod 2^32. I suppose one of these days I should actually read the standards you guys cite so often ... but ... naive question ... does the standard actually guarantee that if you overflow a multiplication you get the modulo 2^32 result? All processors that I'm aware of work this way (in fact, on all processors I'm aware of MUL is sized so that overflow is impossible), but it seems somebody somewhere might have a processor with a 32 = 32 x 32 multiply and if you overflow you get an overflow flag and an undefined result ... and if this is the case it would be inconvenient to provide the modulo 2^32 result. Is this guaranteed on a multiplication overflow? -- David T. Ashley (dt*@e3ft.com) http://www.e3ft.com (Consulting Home Page) http://www.dtashley.com (Personal Home Page) http://gpl.e3ft.com (GPL Publications and Projects) Feb 1 '07 #28

 P: n/a "David T. Ashley"

 P: n/a In article , David T. Ashley does the standard actually guarantee that if you overflow a multiplicationyou get the modulo 2^32 result? We were assuming that unsigned ints are 32 bits, which is of course not guaranteed, but arithmetic on unsigned ints *is* guaranteed to work modulo 2^N, where N is the number of bits. For signed integers, anything may happen. -- Richard -- "Consideration shall be given to the need for as many as 32 characters in some alphabets" - X3.4, 1963. Feb 1 '07 #30

 P: n/a Richard Tobin said: In article , Richard Heathfield >Most were obvious, of course, but there was a subtlety in there that Iwould expect only an expert to spot. Go on, tell us. Ben beat us to it. I assume it's that assert(pointer) is not allowed in C90. (but works on all known systems). It's the systems that I doesn't know as makes me worry mostest. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 1 '07 #31

 P: n/a The correct answer as told to me by a person is (N>>3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 Feb 1 '07 #32

 P: n/a On 1 Feb 2007 09:13:37 -0800, mi****@gmail.com wrote: >On Feb 1, 11:56 am, Ico krypto.wiz...@gmail.com wrote: Last month I appeared for an interview with EA sports and they asked me this question. How would you divide a number by 7 without using division operator ? I did by doing a subtraction and keeping a counter that kept a tab on how many times I subtracted. Later, the EA sport guy told me that of course there are can be better technique by using bit operator. Since 7 has a binary representation 111, my guess is that a left shift operation of 3 bits should give the answer, but I couldn't get it to work. Pick your accuracy:a: the required multiplicationb: the resulting factor from the operation + (a>>3) a=0.142857 b=0.125 error=1.7857% + (a>>3) + (a>>6) a=0.142857 b=0.140625 error=0.2232% + (a>>3) + (a>>6) + (a>>9) a=0.142857 b=0.142578 error=0.0279% + (a>>3) + (a>>6) + (a>>9) + (a>>12) a=0.142857 b=0.142822 error=0.0035% and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )Stijn Feb 1 '07 #33

 P: n/a On Feb 1, 3:29 pm, c...@tiac.net (Richard Harter) wrote: On 1 Feb 2007 09:13:37 -0800, mic...@gmail.com wrote: On Feb 1, 11:56 am, Ico >3) a=0.142857 b=0.125 error=1.7857% + (a>>3) + (a>>6) a=0.142857 b=0.140625 error=0.2232% + (a>>3) + (a>>6) + (a>>9) a=0.142857 b=0.142578 error=0.0279% + (a>>3) + (a>>6) + (a>>9) + (a>>12) a=0.142857 b=0.142822 error=0.0035%

 P: n/a "Krypto" >3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 A person was mistaken. The lowest non-negative value for which it fails is 7. The highest non-negative value for which it succeeds is 384. (I didn't try it for negative values.) But the pattern of failures (difference between the result of the expression and N/7) is interesting, and may suggest that a correct answer would look similar to what you wrote. Here's my test program. WARNING: It will produce huge amounts of output. Run it as "./prog | more", or "./prog | head -100", or equivalent. #include #include #define DIV_BY_7(N) (((N)>>3) + (((N)-7*((N)>>3))>>3)) int main(void) { int i = 0; while (1) { int x = i / 7; int y = DIV_BY_7(i); printf("%6d ", i); if (x != y) { printf("%6d", x - y); } putchar('\n'); if (i == INT_MAX) { break; } i++; } return 0; } -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Feb 1 '07 #35

 P: n/a ri*****@cogsci.ed.ac.uk (Richard Tobin) writes: In article , David T. Ashley San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Feb 1 '07 #36

 P: n/a On 1 Feb 2007 12:42:23 -0800, da***************@gmail.com wrote: >On Feb 1, 3:29 pm, c...@tiac.net (Richard Harter) wrote: >On 1 Feb 2007 09:13:37 -0800, mic...@gmail.com wrote: >On Feb 1, 11:56 am, Ico Pick your accuracy: >a: the required multiplicationb: the resulting factor from the operation > + (a>>3) a=0.142857 b=0.125 error=1.7857% > + (a>>3) + (a>>6) a=0.142857 b=0.140625 error=0.2232% > + (a>>3) + (a>>6) + (a>>9) a=0.142857 b=0.142578 error=0.0279% > + (a>>3) + (a>>6) + (a>>9) + (a>>12) a=0.142857 b=0.142822 error=0.0035% >nice. >This uses the following relationship: >1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1) An alternative is1/(1-x) = (1+x)*(1+x**2)*(1+x**4)... >and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... ) >Stijn How will it work ? /* ans = x/7, accuracy up to 51 bits module corner cases, code untested and will probably fail within 3 bits of maximum int. The idea is to exploit the formula 1/(1-x) = (1+x)*(1+x^2)*(1+x^4)... */ ans = x + x>>3; ans += ans * (x>>6); ans += ans * (x>>12); ans += ans * (x>>24); ans = ans >>3; Feb 1 '07 #37

 P: n/a Krypto wrote, On 01/02/07 20:27: Subject: division by 7 without using division operator The correct answer as told to me by a person is (N>>3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 If we put in N=7 we get: (7>>3) + ((7 - 7*(7>>3)) >3) =0 + ((7 - 7*0) >3) =(7-0) >3 =7 >3 =0 I think you should not trust what that person tells you. Either that or take a lot more care in listening and noting down what they tell you. Or to put it in C: #include #include int main(int argc,char **argv) { unsigned long n; char *end; if (argc < 2) { fputs("Give me a number!\n", stderr); return EXIT_FAILURE; } n = strtoul(argv, &end, 10); if (end==argv || *end) { fputs("Give me a number!\n", stderr); return EXIT_FAILURE; } printf("%lu / 7 = %lu\n", n, (n>>3) + ((n-7*(n>>3))>>3)); return EXIT_SUCCESS; } markg@brenda:~\$ gcc t.c -ansi -pedantic -Wall -W -O3 markg@brenda:~\$ ./a.out 7 7 / 7 = 0 markg@brenda:~\$ -- Flash Gordon Feb 1 '07 #38

 P: n/a In article <11**********************@h3g2000cwc.googlegroups. com"Krypto" >3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 Except when N is a multiple of 7 and a large number of other cases. Try it with N == 7. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ Feb 2 '07 #39

 P: n/a In article , Ben Pfaff

 P: n/a Richard Heathfield wrote: Ben Pfaff said: .... snip ... > >> while(q < r) { char c = *q; *q++ = *r; *r-- = c; } I'm not going to bother to analyze this. Likely problems includestepping off the beginning or the end of the array. Actually, had you bothered to analyse it, you would have found that it's about the only part of the program that is actually correct. :-) It also has a bug. If strlen(p) == 0, then q is pointing outside any object, and the comparison q < r is illegal. Assuming the initialization of q could be done, which is also not guaranteed. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. Feb 2 '07 #41

 P: n/a Richard Heathfield wrote: how would you reply? What do you think the questioner really wants? char *p = malloc(strlen(v)); [...] ^^^^^^^^^ strcpy(p, v); ^^^^^^^ Feb 2 '07 #42

 P: n/a Richard Heathfield wrote: >I assume it's that assert(pointer) is not allowed in C90. >(but works on all known systems). 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. Feb 2 '07 #43

 P: n/a Richard Tobin wrote: 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. Feb 2 '07 #44

 P: n/a Christopher Layne said: Richard Heathfield wrote: >>I assume it's that assert(pointer) is not allowed in C90. >>(but works on all known systems). 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? 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 "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 2 '07 #45

 P: n/a CBFalconer said: Richard Heathfield wrote: >Ben Pfaff said: ... snip ... >> >>> while(q < r) { char c = *q; *q++ = *r; *r-- = c; }I'm not going to bother to analyze this. Likely problems includestepping off the beginning or the end of the array. Actually, had you bothered to analyse it, you would have found thatit's about the only part of the program that is actually correct. :-) 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 "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 2 '07 #46

 P: n/a Christopher Layne said: Richard Heathfield wrote: >how would you reply? What do you think the questioner really wants? > char *p = malloc(strlen(v)); [...] ^^^^^^^^^ > strcpy(p, v); ^^^^^^^ Yes, well done - but, whilst your observation is an important one, it lacks completeness. (Others have already provided more complete answers.) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 2 '07 #47

 P: n/a ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote: In article , Richard Heathfield

 P: n/a Richard Bos said: ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote: >In article ,Richard Heathfield Most were obvious, of course, but there was a subtlety in there that Iwould expect only an expert to spot. 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. 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". -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 2 '07 #49

 P: n/a On Feb 2, 7:03 am, Richard Heathfield I assume it's that assert(pointer) is not allowed in C90. >(but works on all known systems). 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? 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? 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 Feb 2 '07 #50

94 Replies

### This discussion thread is closed

Replies have been disabled for this discussion. 