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

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

The number may be signed or unsigned.

This is a simple function which performs the desired operation. But it requires the + operator, so all you have left to do is to add the values with bit-operators:

// replaces the + operator
int add(int x, int y)
{
    while (x) {
        int t = (x & y) << 1;
        y ^= x;
        x = t;
    }
    return y;
}

int divideby3(int num)
{
    int sum = 0;
    while (num > 3) {
        sum = add(num >> 2, sum);
        num = add(num >> 2, num & 3);
    }
    if (num == 3)
        sum = add(sum, 1);
    return sum; 
}

As Jim commented this works, because:

• n = 4 * a + b

• n / 3 = a + (a + b) / 3

• So sum += a, n = a + b, and iterate

• When a == 0 (n < 4), sum += floor(n / 3); i.e. 1, if n == 3, else 0

Idiotic conditions call for an idiotic solution:

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

int main()
{
    FILE * fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char * buf = calloc(number,1);
    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;
}

If also the decimal part is needed, just declare result as double and add to it the result of fmod(number,divisor).

Explanation of how it works

1. The fwrite writes number bytes (number being 123456 in the example above).
2. rewind resets the file pointer to the front of the file.
3. fread reads a maximum of number "records" that are divisor in length from the file, and returns the number of elements it read.

If you write 30 bytes then read back the file in units of 3, you get 10 "units". 30 / 3 = 10

log(pow(exp(number),0.33333333333333333333)) /* :-) */

#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;
}

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;
}

Use itoa to convert to a base 3 string. Drop the last trit and convert back to base 10.

// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
    char str[42];
    sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
    if (i>0)                     // Remove sign if positive
        str[0] = ' ';
    itoa(abs(i), &str[1], 3);    // Put ternary absolute value starting at str[1]
    str[strlen(&str[1])] = '\0'; // Drop last digit
    return strtol(str, NULL, 3); // Read back result
}

(note: see Edit 2 below for a better version!)

This is not as tricky as it sounds, because you said "without using the [..] + [..] operators". See below, if you want to forbid using the + character all together.

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    for (unsigned i = 0; i < by; i++)
      cmp++; // that's not the + operator!
    floor = r;
    r++; // neither is this.
  }
  return floor;
}

then just say div_by(100,3) to divide 100 by 3.

---

Edit: You can go on and replace the ++ operator as well:

unsigned inc(unsigned x) {
  for (unsigned mask = 1; mask; mask <<= 1) {
    if (mask & x)
      x &= ~mask;
    else
      return x & mask;
  }
  return 0; // overflow (note that both x and mask are 0 here)
}

---

Edit 2: Slightly faster version without using any operator that contains the +,-,*,/,% characters.

unsigned add(char const zero[], unsigned const x, unsigned const y) {
  // this exploits that &foo[bar] == foo+bar if foo is of type char*
  return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    cmp = add(0,cmp,by);
    floor = r;
    r = add(0,r,1);
  }
  return floor;
}

We use the first argument of the add function because we cannot denote the type of pointers without using the * character, except in function parameter lists, where the syntax type[] is identical to type* const.

FWIW, you can easily implement a multiplication function using a similar trick to use the 0x55555556 trick proposed by AndreyT:

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

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".

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.

To divide a 32-bit number by 3 one can multiply it by 0x55555556 and then take the upper 32 bits of the 64 bit result.

Now all that's left to do is to implement multiplication using bit operations and shifts...

Yet another solution. This should handle all ints (including negative ints) except the min value of an int, which would need to be handled as a hard coded exception. This basically does division by subtraction but only using bit operators (shifts, xor, & and complement). For faster speed, it subtracts 3 * (decreasing powers of 2). In c#, it executes around 444 of these DivideBy3 calls per millisecond (2.2 seconds for 1,000,000 divides), so not horrendously slow, but no where near as fast as a simple x/3. By comparison, Coodey's nice solution is about 5 times faster than this one.

public static int DivideBy3(int a) {
	bool negative = a < 0;
	if (negative) a = Negate(a);
	int result;
	int sub = 3 << 29;
	int threes = 1 << 29;
	result = 0;
	while (threes > 0) {
		if (a >= sub) {
			a = Add(a, Negate(sub));
			result = Add(result, threes);
		}
		sub >>= 1;
		threes >>= 1;
	}
	if (negative) result = Negate(result);
	return result;
}
public static int Negate(int a) {
	return Add(~a, 1);
}
public static int Add(int a, int b) {
	int x = 0;
	x = a ^ b;
	while ((a & b) != 0) {
		b = (a & b) << 1;
		a = x;
		x = a ^ b;
	}
	return x;
}

This is c# because that's what I had handy, but differences from c should be minor.

It's really quite easy.

if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;

(I have of course omitted some of the program for the sake of brevity.) If the programmer gets tired of typing this all out, I'm sure that he or she could write a separate program to generate it for him. I happen to be aware of a certain operator, /, that would simplify his job immensely.

Using counters is a basic solution:

int DivBy3(int num) {
    int result = 0;
    int counter = 0;
    while (1) {
        if (num == counter)       //Modulus 0
            return result;
        counter = abs(~counter);  //++counter

        if (num == counter)       //Modulus 1
            return result;
        counter = abs(~counter);  //++counter

        if (num == counter)       //Modulus 2
            return result;
        counter = abs(~counter);  //++counter

        result = abs(~result);    //++result
    }
}

It is also easy to perform a modulus function, check the comments.

This one is the classical division algorithm in base 2:

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint32_t mod3[6] = { 0,1,2,0,1,2 };
  uint32_t x = 1234567; // number to divide, and remainder at the end
  uint32_t y = 0; // result
  int bit = 31; // current bit
  printf("X=%u   X/3=%u\n",x,x/3); // the '/3' is for testing
  
  while (bit>0)
  {
    printf("BIT=%d  X=%u  Y=%u\n",bit,x,y);
    // decrement bit
    int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
    uint32_t r = x>>bit;  // current remainder in 0..5
    x ^= r<<bit;          // remove R bits from X
    if (r >= 3) y |= 1<<bit; // new output bit
    x |= mod3[r]<<bit;    // new remainder inserted in X
  }
  printf("Y=%u\n",y);
}

Write the program in Pascal and use the DIV operator.

Since the question is tagged [tag: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

int div3(int x)
{
  int reminder = abs(x);
  int result = 0;
  while(reminder >= 3)
  {
     result++;

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}

Didn't cross-check if this answer is already published. If the program need to be extended to floating numbers, the numbers can be multiplied by 10*number of precision needed and then the following code can be again applied.

#include <stdio.h>

int main()
{
    int aNumber = 500;
    int gResult = 0;

    int aLoop = 0;

    int i = 0;
    for(i = 0; i < aNumber; i++)
    {
        if(aLoop == 3)
        {
           gResult++;
           aLoop = 0;
        }  
        aLoop++;
    }

    printf("Reulst of %d / 3 = %d", aNumber, gResult);

    return 0;
}

This should work for any divisor, not only three. Currently only for unsigned, but extending it to signed should not be that difficult.

#include <stdio.h>

unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do      {
        one = ~two & bor;
        two ^= bor;
        bor = one<<1;
        } while (one);
return two;
}

unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;

if (!bot || top < bot) return 0;

for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;

for (result=0; shift--; bot >>= 1 ) {
        result <<=1;
        if (top >= bot) {
                top = sub(top,bot);
                result |= 1;
                }
        }
return result;
}

int main(void)
{
unsigned arg,val;

for (arg=2; arg < 40; arg++) {
        val = bitdiv(arg,3);
        printf("Arg=%u Val=%u\n", arg, val);
        }
return 0;
}

Would it be cheating to use the / operator "behind the scenes" by using eval and string concatenation?

For example, in Javacript, you can do

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}

First that I've come up with.

irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub('   ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222

EDIT: Sorry, I didn't notice the tag C. But you can use the idea about string formatting, I guess...

Using BC Math in PHP:

<?php
    $a = 12345;
    $b = bcdiv($a, 3);   
?>

---

MySQL (it's an interview from Oracle)

> SELECT 12345 DIV 3;

---

Pascal:

a:= 12345;
b:= a div 3;

---

x86-64 assembly language:

mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8

Using Hacker's Delight Magic number calculator

int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}

Where fma is a standard library function defined in math.h header.

The following script generates a C program that solves the problem without using the operators * / + - %:

#!/usr/bin/env python3

print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')

for i in range(-2**31, 2**31):
    print('    if(input == %d) return %d;' % (i, i / 3))


print(r'''
    return 42; // impossible
}
int main()
{
    const int32_t number = 8;
    printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')

Solution using fma() library function, works for any positive number:

#include <stdio.h>
#include <math.h>

int main()
{
	int number = 8;//Any +ve no.
	int temp = 3, result = 0;
	while(temp <= number){
		temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
		result = fma(result, 1, 1);
	} 
	printf("\n\n%d divided by 3 = %d\n", number, result);
}

See my another answer.

How about this approach (c#)?

private int dividedBy3(int n) {
        List<Object> a = new Object[n].ToList();
        List<Object> b = new List<object>();
        while (a.Count > 2) {
            a.RemoveRange(0, 3);
            b.Add(new Object());
        }
        return b.Count;
    }

I think the right answer is:

Why would I not use a basic operator to do a basic operation?

First:

x/3 = (x/4) / (1-1/4)

Then figure out how to solve x/(1 - y):

x/(1-1/y)
  = x * (1+y) / (1-y^2)
  = x * (1+y) * (1+y^2) / (1-y^4)
  = ...
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
  = x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))

with y = 1/4:

int div3(int x) {
    x <<= 6;    // need more precise
    x += x>>2;  // x = x * (1+(1/2)^2)
    x += x>>4;  // x = x * (1+(1/2)^4)
    x += x>>8;  // x = x * (1+(1/2)^8)
    x += x>>16; // x = x * (1+(1/2)^16)
    return (x+1)>>8; // as (1-(1/2)^32) very near 1,
                     // we plus 1 instead of div (1-(1/2)^32)
}

Although it uses +, but somebody already implements add by bitwise op.

Use cblas, included as part of OS X's Accelerate framework.

[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>

int main() {
    float multiplicand = 123456.0;
    float multiplier = 0.333333;
    printf("%f * %f == ", multiplicand, multiplier);
    cblas_sscal(1, multiplier, &multiplicand, 1);
    printf("%f\n", multiplicand);
}

[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031

Generally, a solution to this would be:

log(pow(exp(numerator),pow(denominator,-1)))

Okay I think we all agree that this isn't a real world problem. So just for fun, here's how to do it with Ada and multithreading:

with Ada.Text_IO;

procedure Divide_By_3 is
   
   protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;
   
   protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;
   
   task type Input is
   end Input;
   task type Output is
   end Output;
   
   protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;
   
   protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;
   
   Collector : Collector_Type;
   Divisor : Divisor_Type;
      
   task body Input is
   begin
      Divisor.Poke;
   end Input;
   
   task body Output is
   begin
      Collector.Poke;
   end Output;

   Cur_Input : access Input;
   
   -- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;

Quite amused none answered with a generic division:

/* For the given integer find the position of MSB */
int find_msb_loc(unsigned int n)
{
    if (n == 0)
	    return 0;

    int loc = sizeof(n)  * 8 - 1;
    while (!(n & (1 << loc)))
	    loc--;
    return loc;
}


/* Assume both a and b to be positive, return a/b */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
    int int_size = sizeof(unsigned int) * 8;
    int b_msb_loc = find_msb_loc(b);

    int d = 0; // dividend
    int r = 0; // reminder
    int t_a = a;
    int t_a_msb_loc = find_msb_loc(t_a);
    int t_b = b << (t_a_msb_loc - b_msb_loc);

    int i;
    for(i = t_a_msb_loc; i >= b_msb_loc; i--)  {
        if (t_a > t_b) {
            d = (d << 1) | 0x1;
	        t_a -= t_b; // Not a bitwise operatiion
	        t_b = t_b >> 1;
	     }
	    else if (t_a == t_b) {
	        d = (d << 1) | 0x1;
	        t_a = 0;
	    }
	    else { // t_a < t_b
	        d = d << 1;
	        t_b = t_b >> 1;
	    }
    }

    r = t_a;
    printf("==> %d %d\n", d, r);
    return d;
}

The bitwise addition has already been given in one of the answers so skipping it.

All answers are probably not that what the interviewer liked to hear:

My answer:

> "I would never do that, who will me pay for such silly things. Nobody > will have an advantage on that, its not faster, its only silly. > Prozessor designers have to know that, but this must then work for all numbers, not only for division by 3"

#include <stdio.h>

typedef struct { char a,b,c; } Triple;

unsigned long div3(Triple *v, char *r) {
  if ((long)v <= 2)  
    return (unsigned long)r;
  return div3(&v[-1], &r[1]);
}

int main() {
  unsigned long v = 21; 
  int r = div3((Triple*)v, 0); 
  printf("%ld / 3 = %d\n", v, r); 
  return 0;
}

Why don't we just apply the definition studied at College? The result maybe inefficient but clear, as the multiplication is just a recursive subtraction and subtraction is an addition, then the addition can be performed by a recursive xor/and logic port combination.

#include <stdio.h>

int add(int a, int b){
   int rc;
   int carry;
   rc = a ^ b; 
   carry = (a & b) << 1;
   if (rc & carry) 
      return add(rc, carry);
   else
      return rc ^ carry; 
}

int sub(int a, int b){
   return add(a, add(~b, 1)); 
}

int div( int D, int Q )
{
/* lets do only positive and then
 * add the sign at the end
 * inversion needs to be performed only for +Q/-D or -Q/+D
 */
   int result=0;
   int sign=0;
   if( D < 0 ) {
      D=sub(0,D);
      if( Q<0 )
         Q=sub(0,Q);
      else
         sign=1;
   } else {
      if( Q<0 ) {
         Q=sub(0,Q);
         sign=1;
      }	
   }
   while(D>=Q) {
      D = sub( D, Q );
      result++;
   }
/*
* Apply sign
*/
   if( sign )
      result = sub(0,result);
   return result;
}

int main( int argc, char ** argv ) 
{
    printf( "2 plus 3=%d\n", add(2,3) );
    printf( "22 div 3=%d\n", div(22,3) );
    printf( "-22 div 3=%d\n", div(-22,3) );
    printf( "-22 div -3=%d\n", div(-22,-3) );
    printf( "22 div 03=%d\n", div(22,-3) );
    return 0;
}

As someone says... first make this work. Note that algorithm should work for negative Q...

If you remind yourself standard school method of division and do it in binary, you will discover that in case of 3 you only divide and subtract a limited set of values (from 0 to 5 in this case). These can be treated with a switch statement to get rid of arithmetic operators.

static unsigned lamediv3(unsigned n)
{
  unsigned result = 0, remainder = 0, mask = 0x80000000;

  // Go through all bits of n from MSB to LSB.
  for (int i = 0; i < 32; i++, mask >>= 1)
  {
    result <<= 1;
    // Shift in the next bit of n into remainder.
    remainder = remainder << 1 | !!(n & mask);

    // Divide remainder by 3, update result and remainer.
    // If remainder is less than 3, it remains intact.
    switch (remainder)
    {
    case 3:
      result |= 1;
      remainder = 0;
      break;

    case 4:
      result |= 1;
      remainder = 1;
      break;

    case 5:
      result |= 1;
      remainder = 2;
      break;
    }
  }

  return result;
}

#include <cstdio>

int main()
{
  // Verify for all possible values of a 32-bit unsigned integer.
  unsigned i = 0;

  do
  {
    unsigned d = lamediv3(i);

    if (i / 3 != d)
    {
      printf("failed for %u: %u != %u\n", i, d, i / 3);
      return 1;
    }
  }
  while (++i != 0);
}

#!/bin/ruby

def div_by_3(i)
  i.div 3        # always return int http://www.ruby-doc.org/core-1.9.3/Numeric.html#method-i-div
end

if we consider __div__ is not orthographically /

def divBy3(n):
	return n.__div__(3)
	
print divBy3(9), 'or', 9//3

3 in base 2 is 11.

So just do long division (like in middle school) in base 2 by 11. It is even easier in base 2 than base 10.

For each bit position starting with most significant:

Decide if prefix is less than 11.

If it is output 0.

If it is not output 1, and then substitute prefix bits for appropriate change. There are only three cases:

 11xxx ->    xxx    (ie 3 - 3 = 0)
100xxx ->   1xxx    (ie 4 - 3 = 1)
101xxx ->  10xxx    (ie 5 - 3 = 2)

All other prefixes are unreachable.

Repeat until lowest bit position and you're done.

It seems no one mentioned the division criterion for 3 represented in binary - sum of even digits should equal the sum of odd digits (similar to criterion of 11 in decimal). There are solutions using this trick under https://stackoverflow.com/questions/844867/check-if-a-number-is-divisible-by-3.

I suppose that this is the possible duplicate that Michael Burr's edit mentioned.

Where InputValue is the number to divide by 3

SELECT AVG(NUM) 
  FROM (SELECT InputValue NUM from sys.dual
         UNION ALL SELECT 0 from sys.dual
         UNION ALL SELECT 0 from sys.dual) divby3

I would use this code to divide all positive, non float numbers. Basically you want to align the divisor bits to the left to match the dividend bits. For each segment of the dividend (size of divisor) you want to check to make sure if the the segment of dividend is greater than the divisor then you want to Shift Left and then OR in the first registrar. This concept was originally created in 2004 (standford I believe), Here is a C version which uses that concept. Note: (I modified it a bit)

int divide(int a, int b)
{
	int c = 0, r = 32, i = 32, p = a + 1;
	unsigned long int d = 0x80000000;

	while ((b & d) == 0)
	{
		d >>= 1;
		r--;
	}
			
	while (p > a)
	{
		c <<= 1;
		p = (b >> i--) & ((1 << r) - 1);
		if (p >= a)
			c |= 1;
	}
	return c; //p is remainder (for modulus)
}

Example Usage:

int n = divide( 3, 6); //outputs 2

Here it is in Python with, basically, string comparisons and a state machine.

def divide_by_3(input):
  to_do = {}
  enque_index = 0
  zero_to_9 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  leave_over = 0
  for left_over in (0, 1, 2):
    for digit in zero_to_9:
      # left_over, digit => enque, leave_over
      to_do[(left_over, digit)] = (zero_to_9[enque_index], leave_over)
      if leave_over == 0:
        leave_over = 1
      elif leave_over == 1:
        leave_over = 2
      elif leave_over == 2 and enque_index != 9:
        leave_over = 0
        enque_index = (1, 2, 3, 4, 5, 6, 7, 8, 9)[enque_index]
  answer_q = []
  left_over = 0
  digits = list(str(input))
  if digits[0] == "-":
    answer_q.append("-")
  digits = digits[1:]
  for digit in digits:
    enque, left_over = to_do[(left_over, int(digit))]
    if enque or len(answer_q):
      answer_q.append(enque)
  answer = 0
  if len(answer_q):
    answer = int("".join([str(a) for a in answer_q]))
  return answer

Well you could think of using a graph/tree like structure to solve the problem. Basically generate as many vertices as the number that is to be divided by 3. Then keep pairing each un-paired vertex with two other vertices.

Rough pseudocode:

function divide(int num)
    while(num!=0)
        Add a new vertice to vertiexList.
        num--
    quotient = 0
    for each in vertexList(lets call this vertex A)
        if vertexList not empty
            Add an edge between A and another vertex(say B)
        else
            your Remainder is 1 and Quotient is quotient
        if vertexList not empty
            Add an edge between A and another vertex(say C)
        else
            your remainder is 2 and Quotient is quotient
        quotient++
        remove A, B, C from vertexList
    Remainder is 0 and Quotient is quotient

This can obviously be optimized and the complexity depends on how big you number is, but it shoud work providing you can do ++ and --. It's as good as counting only cooler.

This will work:

smegma$ curl http://www.wolframalpha.com/input/?i=14+divided+by+3 2>/dev/null | gawk 'match($0, /link to /input/\?i=([0-9.+-]+)/, ary) { print substr( $0, ary[1, "start"], ary[1, "length"] )}' 4.6666666666666666666666666666666666666666666666666666

Just substitute '14' and '3' with your numbers.

Using a Linux shell script:

#include <stdio.h>
int main()
{
	int number = 30;
	char command[25];
	snprintf(command, 25, "echo $((%d %c 3)) ", number, 47);
	system( command );
	return 0;
}

See my another answer.

Good 'ol bc:

$ num=1337; printf "scale=5;${num}\x2F3;\n" | bc
445.66666

Here's a method my Grandfather taught me when I was a child. It requires + and / operators but it makes calculations easy.

Add the individual digits together and then see if its a multiple of 3.

But this method works for numbers above 12.

Example: 36,

3+6=9 which is a multiple of 3.

42,

4+2=6 which is a multiple of 3.