As others have noted, they probably are interested in how you approach the problem, not whether or not you can actually solve it. Just fire off a few ideas and outlines of how they would work. Here's what comes to mind (I had not seen this problem before) (I'm assuming the target number we are trying to divide by 3 is a non-negative integer of N bits, where N is fixed...e.g., a C unsigned int or something like that):
1. Implement addition at the bit level. Here's an example for 16-bit numbers:
def badd(A, C):
while C != 0:
t = A & C
A = A ^ C
C = (t << 1) & 0xFFFF
return A
That's actually all I need, because I could no do something like make two counters in a loop, both starting at 0. The first counter goes up by 1 each iteration, the second by 3. Stop when the second counter exceeds the target number, and return the first counter.
2. The solution in #1 can be greatly speed up, while keeping the same basic idea. Hard code in a table that contains decreasing powers of two in the first column, and the second column is 3 times the first column.
Now the loop starts at 0, and has two counters, but also has an index into the table. The first counter goes up by the first column at the current table index, the second counter by the second column. When a step would take the second counter past the target number instead of terminating, increment the index into the table.
3. Do division similar to how we would do it by hand. Here is an example for 16-bit numbers:
def div3(A):
m = 0x8000
r = 0
d = 0
while m != 0:
r <<= 1
if A & m:
r |= 1
if r == 0:
q, r = 0, 0
elif r == 1:
q, r = 0, 1
elif r == 2:
q, r = 0, 2
elif r == 3:
q, r = 1, 0
elif r == 4:
q, r = 1, 1
elif r == 5:
q, r = 1, 2
d = (d<<1) | q
m >>= 1
return d
4. Similar to the above, but first replace the if/elif chain with something based on table lookup, and work on more than one bit at a time.
5. Dividing by 3 is the same as multiplying by 1/3. Multiplication can be done by shifting and adding, and I've got adding from #1.
6. Oracle can afford big machines. Just do the whole thing with a big table lookup.