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

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

(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]);
}

Answer 6

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.