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.
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
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 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]);
}
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.
(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.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:As Jim commented this works, because:
n = 4 * a + b
n / 3 = a + (a + b) / 3
So
sum += a
,n = a + b
, and iterateWhen
a == 0 (n < 4)
,sum += floor(n / 3);
i.e. 1,if n == 3, else 0
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...
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.
(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.then just say
div_by(100,3)
to divide100
by3
.Edit: You can go on and replace the
++
operator as well:Edit 2: Slightly faster version without using any operator that contains the
+
,-
,*
,/
,%
characters.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 syntaxtype[]
is identical totype* const
.FWIW, you can easily implement a multiplication function using a similar trick to use the
0x55555556
trick proposed by AndreyT: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.
This is c# because that's what I had handy, but differences from c should be minor.