Divide a number by 3 without using * / + - % operators

I don't usually sit on the side of fence that complains about "write a function that does X" style questions in interviews, but I can't see how this is useful at all.

This just seems like one of those things that you either know off the top of your head, or you don't. If you asked me to derive the addition operation using only bit level operators, I might be able to come up with it, but it'd probably take me much longer than an interview allows. But to come up with divide is just not going to happen.

So if you don't know the answer off the top of your head, what use is this question?

"Look at bit-shift operators, and how they work on unsigned integers. Then think & and ^ and how they relate to addition (adders, after all, have to be implemented in terms of elementary operations like those). It's all pretty straightforward from there. Go the whiteboard and walk you through it? Huh? Look, it's an interesting problem, but I've got some regression tests to get straightened out by the end of the day that are like, totally messed up. They were written by some guy we hired on the basis of his ability to solve puzzle problems, but just ended up totally slacking and never tying the ends off of anything he did."

Really now, why should one's response in an interview be any different?

Edit: I should add, the problem never said I didn't have infinite memory or computational resources.

Or a slide rule, though that's possibly cheating (technically you'd be dividing....)

http://stackoverflow.com/questions/11694546/divide-a-number-...

http://en.wikipedia.org/wiki/Setun

    u32 add(u32 x, u32 y)
    {
        u32 z = 0;
        for (u32 c = 0, m = 1; m; m <<= 1)
            z |= (x ^ y ^ c) & m, c = ((x & y) | (x & c) | (y & c)) << 1;
        return z;
    }

    u32 neg(u32 x) { return add(~x, 1); }
    u32 sub(u32 x, u32 y) { return add(x, neg(y)); }
    u32 lt(u32 x, u32 y) { return sub(x, y) >> 31; }

    u32 div3(u32 x)
    {
        u32 q = 0;
        assert(lt(-1, x)); // x >= 0 iff -1 < x
        while (!lt(x, 3)) x = sub(x, 3), q = add(q, 1);
        return q;
    }

    n = 12345                # your input
    s = ''.zfill(n)          # fill as many zeroes
    while len(s)>3: s=s[3:]  # trim 3 zeroes each time
    print 'divisible by 3' if len(s)==3 else 'nop'

1 dollar.

I get that a company wants to hire smart people who can problem solve and think outside the box, but it doesn't really represent reality. I think if you had someone who wrote code like that you would have a maintenance nightmare since most people don't write code like that.

Of course not all situations are like mine. I write a few layers of abstraction away from the hardware, and live mostly in the managed code world. A low level/embedded systems developer may need to know these things.

1/3 = 0.010101... base 2.

x = let x0,x1,...,xN-2,xN-1 (MSB is x0 and LSB is xN-1)

Now y = x/3 = x * 1/3, where y=(y0,y1,...), so a long multiplication will look something like (being sloppy about exact bit positions):

    x0,x1,...,xN-2,xN-1

  * 0.010101...

  -------------------------

    x0,x1,x2,x3,x4,x5...,xN-2,xN-1

          x0,x1,x2,x3,x4,x5...,xN-2,xN-1

                x0,x1,x2,x3,x4,x5...,xN-2,xN-1

  X0,X1,X2,X3

     X0,X1,X2,X3

        X0,X1,X2,X3

  Y0,Y1,Y2,Y3,Y4,Y5

  Y1=X1+X0+carry   =X1+Y0 or X1+Y0+1 (extra bits of carry are in Y0)

  Y2=X2+X1+X0+carry=X2+Y1 or X1+Y1+1 (extra bits of carry are in Y1)

Here's a partial solution, which only works fro a few trivial cases (eg 2^N) since I haven't accounted for the possability of a single bit carry. For a full solution, maybe a conditional is required and an additonal logic operation or two to perform an increment on a pair of bits?

div3(int x) { int y=0; while(x) y ^= (x>>=2) return(y) }

Can anyone complete it?

Edit: formatting. Beats me how to do fixed width properly. Edit: Oops. In the time it took me to write this qntm got there first!

OK my solution is connect to a postgres sql DB server and something very much like "SELECT WIDTH_BUCKET(389, 999, 0, 333);" and the result will be something like 129. width_bucket asks for a sample, the highest bucket, the lowest bucket, how many buckets, and tells you which bucket to dump the sample into. You know, for histograms and stuff like that. So you make the largest bucket max_int or 999 in this easy scenario, and the number of buckets precisely 1/3 the number of buckets or 333 in this easy case, and postgres database will figure out the number of the bucket to stick your sample into, which coincidentally happens to numerically match 1/3 the sample.

Its possible Oracle has a function similar to width_bucket from postgres, but I have no idea because a Oracle license costs about 10 times the value of my house so I can't afford it, probably because they pay people to reimplement /.

Another fun way to attack this problem would be to go all trig on them and try to convince them its impossible to divide by 3 because you can't trisect an angle using classical greek construction techniques. Then you hit them with galois theory as relates to solving cubic equations, until their brains bleed and/or you get the job and/or removed by security. This stuff is all 200 years old, or so, but you'll still find cranks who think they can trisect angles using classical greek construction techniques. Maybe being smart enough to understand that overqualifies the applicant from working at a place that things reimplementing / is a wise use of brain power.

Nearly spat out my coffee.

No bit twiddling. Small RAM footprint. Obviously correct. (This is really just an unoptimized version of the "clever" solution.)

For Oracle though -- create a database of numbers and their thirds and then lookup the answer.

#include <stdio.h> #include <stdlib.h> #include <string.h>

int main() { FILE * fp=fopen("temp.dat","w+b"); int number=12346; int divisor=3; char * buf = malloc(number); memset(buf,0,number); fwrite(buf,number,1,fp); rewind(fp); int result=fread(buf,divisor,number,fp); printf("%d / %d = %d", number, divisor, result); free(buf); fclose(fp); return 0; }

You would have to handle each of the bits individually.

https://gist.github.com/3206885

  new java.math.BigInteger("10").divide(new java.math.BigInteger("3"));

  new java.math.BigDecimal("10").divide(new java.math.BigDecimal("3"), java.math.RoundingMode.HALF_UP);