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

Question

How would you divide a number by 3 without using *, /, +, -, %, operators?

The number may be signed or unsigned.

Answer 1

You can use (platform dependent) inline assembly, e.g., for x86: (also works for negative numbers)

#include <stdio.h>

int main() {
  int dividend = -42, divisor = 5, quotient, remainder;

  __asm__ ( "cdq; idivl %%ebx;"
          : "=a" (quotient), "=d" (remainder)
          : "a"  (dividend), "b"  (divisor)
          : );

  printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
  return 0;
}

Answer 2

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

int main(int argc, char *argv[])
{

    int num = 1234567;
    int den = 3;
    div_t r = div(num,den); // div() is a standard C function.
    printf("%d\n", r.quot);

    return 0;
}

Answer 3

Here's my solution:

public static int div_by_3(long a) {
    a <<= 30;
    for(int i = 2; i <= 32 ; i <<= 1) {
        a = add(a, a >> i);
    }
    return (int) (a >> 32);
}

public static long add(long a, long b) {
    long carry = (a & b) << 1;
    long sum = (a ^ b);
    return carry == 0 ? sum : add(carry, sum);
}

First, note that

1/3 = 1/4 + 1/16 + 1/64 + ...

Now, the rest is simple!

a/3 = a * 1/3  
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...

Now all we have to do is add together these bit shifted values of a! Oops! We can't add though, so instead, we'll have to write an add function using bit-wise operators! If you're familiar with bit-wise operators, my solution should look fairly simple... but just in-case you aren't, I'll walk through an example at the end.

Another thing to note is that first I shift left by 30! This is to make sure that the fractions don't get rounded off.

11 + 6

1011 + 0110  
sum = 1011 ^ 0110 = 1101  
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100  
Now you recurse!

1101 + 0100  
sum = 1101 ^ 0100 = 1001  
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000  
Again!

1001 + 1000  
sum = 1001 ^ 1000 = 0001  
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000  
One last time!

0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17  
carry = (0001 & 10000) << 1 = 0

Done!

It's simply carry addition that you learned as a child!

111
 1011
+0110
-----
10001

This implementation failed because we can not add all terms of the equation:

a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i

Suppose the reslut of div_by_3(a) = x, then x <= floor(f(a, i)) < a / 3. When a = 3k, we get wrong answer.

Answer 4

It is easily possible on the Setun computer.

To divide an integer by 3, shift right by 1 place.

I'm not sure whether it's strictly possible to implement a conforming C compiler on such a platform though. We might have to stretch the rules a bit, like interpreting "at least 8 bits" as "capable of holding at least integers from -128 to +127".

Answer 5

Write the program in Pascal and use the DIV operator.

Since the question is tagged c, you can probably write a function in Pascal and call it from your C program; the method for doing so is system-specific.

But here's an example that works on my Ubuntu system with the Free Pascal fp-compiler package installed. (I'm doing this out of sheer misplaced stubbornness; I make no claim that this is useful.)

divide_by_3.pas :

unit Divide_By_3;
interface
    function div_by_3(n: integer): integer; cdecl; export;
implementation
    function div_by_3(n: integer): integer; cdecl;
    begin
        div_by_3 := n div 3;
    end;
end.

main.c :

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

extern int div_by_3(int n);

int main(void) {
    int n;
    fputs("Enter a number: ", stdout);
    fflush(stdout);
    scanf("%d", &n);
    printf("%d / 3 = %d\n", n, div_by_3(n));
    return 0;
}

To build:

fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main

Sample execution:

$ ./main
Enter a number: 100
100 / 3 = 33

Answer 6

Since it's from Oracle, how about a lookup table of pre calculated answers. :-D