Another bitwise operators puzzle

[ajaygargnsit]

Given a number, we need to divide it by 3, without using *, /, % operators. Well the question also mentions that itoa() function is available !!

[Meetee]

Given a number, we need to divide it by 3, without using *, /, % operators. Well the question also mentions that itoa() function is available !!

I have not tried with itoa but it is something like following, hope it helps:

 int n = given number;
         int i=0;
         while(i < n)
         {
                for(int j = 0; j < 3; j++)
                {
                        i++;
                }
         }
Now check whether i == n then number is divisible by 3

Regards

[ravenspoint]

zodilla58's solution will work, I think. However, counting upwards by the divisor checking all the time if you have reached the numerator must be called a brute force algorithm: workable for small values, or if you only want to do this once.

Let's see if we can't come up with something a little more scalable.

The mention of itoa, suggests that we might want to look at the base 10 digits.

Let's look at a few multiples of 3: 27, 33, 102, 300, 402

Ah!

It looks like if you add the base 10 digits together, then they will sum to 3, 6 or 9 when there is an exact multiple of 3.

Is this true? Can anyone find a counter-example? Can anyone provide a mathematical proof that this has to be so?

It might be easier to write a quick program to test if this is true on the first million multiples of 3. Would that be proof? Maybe not, but I would be convinced.

Assuming it is true, the algorithm is straight-forward.

- convert to ascii character in base 10 ( itoa )
- extract individual characters
- convert each character to a small integer ( 0:9 )
- sum integers
- if sum > 9, repeat.
- compare final, single digit sum with 3, 6 & 9

[stefaan]

It looks like if you add the base 10 digits together, then they will sum to 3, 6 or 9 when there is an exact multiple of 3.

Is this true? Can anyone find a counter-example? Can anyone provide a mathematical proof that this has to be so?

this is obviously not the case take 3333. this is divisable by 3 but sums to 12. unless you sum 12 again ... then you would get 3 and you are correct. however if not there you have a counter example.
Now if I remember correct form school you can check if a number is divisable by 3 if the sum of the base 10 digits returns a number divisable by 3.

I don't have proof for this, it's just something they tought us at math :)

hope this helps
cheers,
stefaan

[ravenspoint]

Stefaan,

Please read my algorithm more carefully.

Notice the line

- if sum > 10, repeat.

Thanks,

[ravenspoint]

Sorry, the line should be:

- if sum > 9, repeat.

[ravenspoint]

Stefaan,

They did not teach you how to prove it? Not much of a math class, then.

Well, let's see how far we can get, without the benefit of a mathematician.

if x < 100

x -> ab

a = x / 10 ( integer division )

b = x - a * 10

a + b = x / 10 + x - ( x / 10 ) * 10 ( add base 10 digits )

= x - ( x / 10 ) * 9

If x = 3 * m ( m is whole integer )

a + b = 3 * m - ( 3 * m / 10) / 9

= 3 * m - m / 30

= x - m / 30

I do not see that this proves anything. It does suggest strongly that 3 and 9 will be "special" when you add the digits.

[improvcornartist]

This might help:

Let x be an n-digit number.

Then x, shown by digits, can be written as abc...n.

This in turn can be written as a sum of powers of 10:
a(10^n-1) + b(10^n-2) + c(10^n-3) + ... + n.

So now, 10 = 9 + 1 and 10^2 = 100 = 99 + 1 and 10^3 = 1000 = 999 + 1 etc. Each can be written as a sum of 1 and a string of nines. The string of nines is divisible by 3 and 9. Our previous formula can then be written like:
a(9...) + b(9...) + c(9...) + ... + [a + b + c + ... + n].

The first n terms are divisible by 3 and 9, so x/9 = y + [a + b + c + ... + n]/9, where y is an integer. Then the division of x by 3 or 9 will be exact when [a + b + c + ... + n] is divisible by 3 or 9. 

Thus, if the sum of the digits of x is divisible by 3, then x is divisible by 3 (likewise for 9).

So, if you continue to sum the digits until you get down to a single digit number, then you can check if that number is 3, 6, or 9. If so, your starting number is divisible by 3.

[ravenspoint]

This might help:

Let x be an n-digit number.

Then x, shown by digits, can be written as abc...n.

This in turn can be written as a sum of powers of 10:
a(10^n-1) + b(10^n-2) + c(10^n-3) + ... + n.

So now, 10 = 9 + 1 and 10^2 = 100 = 99 + 1 and 10^3 = 1000 = 999 + 1 etc. Each can be written as a sum of 1 and a string of nines. The string of nines is divisible by 3 and 9. Our previous formula can then be written like:
a(9...) + b(9...) + c(9...) + ... + [a + b + c + ... + n].

The first n terms are divisible by 3 and 9, so x/9 = y + [a + b + c + ... + n]/9, where y is an integer. Then the division of x by 3 or 9 will be exact when [a + b + c + ... + n] is divisible by 3 or 9. 

Thus, if the sum of the digits of x is divisible by 3, then x is divisible by 3 (likewise for 9).

So, if you continue to sum the digits until you get down to a single digit number, then you can check if that number is 3, 6, or 9. If so, your starting number is divisible by 3.

Bravo! A very nice proof, with a lovely insight that 10 = 9 + 1.

[epyk]

#include<iostream>
using namespace std;
#define LARGEST_UINT_BIT (1 << 31)
bool add_carry_bit = true;
unsigned int add(unsigned int in1, unsigned int in2){
	unsigned int bit, carry, tmp;
	carry = in1 & in2;
	bit = in1 ^ in2;
	add_carry_bit = false;
	while(carry){
		if(carry & LARGEST_UINT_BIT) add_carry_bit = 1;
		carry <<= 1;
		tmp = bit ^ carry;
		carry &= bit;
		bit = tmp;}
	return bit;}
unsigned long addwithcarry(unsigned long in1, unsigned long in2){
	unsigned long bit, carry, tmp;
	if(add_carry_bit){
		add_carry_bit = false;
		carry = add((in1 & in2), 1);}
	else carry = in1 & in2;
	bit = in1 ^ in2;
	while(carry){
		if(carry & LARGEST_UINT_BIT) add_carry_bit = 1;
		carry <<= 1;
		tmp = bit ^ carry;
		carry &= bit;
		bit = tmp;}
	return bit;}
int main(){
	unsigned int num;
	unsigned int temp;
	unsigned int result=0;
cout << "Enter an number, and i will divide it by 3." << endl;
cin >> num;
temp = num;
temp = temp>>2;
cout << endl << num << " devided by 3 is " << add(temp,1);
system("pause");
return 0;}

there integer devision by 3 using only bitwise operators
and itoa() can be used to output the binary to the console...

[ravenspoint]

Wow!

A lot of code, but I guess it does answer the OP.

Somehow we got deflected into answering the question, divisible by 3, yes or no.

[epyk]

the code i posted actually only works sometimes.... it happens in the adding section, i have to check it out some. i only started doing bitwise yesterday... so bear with me... this post started me on the topic.. if anyone else can fix the carry method let me know...

[epyk]

cin >> num;
temp = num;
temp = temp>>2;
//here i have to add 1
temp += 1;

this is the easiest way

[JosAH]

cin >> num;
temp = num;
temp = temp>>2;
//here i have to add 1
temp += 1;

this is the easiest way

That doesn't divide a number by three; take 24 for a counter example:
(24 >> 2)+1 doesn't equal eight which it should. Binary division is identical to
long division, i.e. shift the divisor to the left and align the topmost bits with the
divident. If you can subtract the divisor from the divident, shift a one left into the
quotient register. Otherwise shift a zero in. Shift the divisor to the right and repeat.
That's the way ALUs (Arithmetic and Logic Units) do it inside your CPU.

kind regards,

Jos