Given a number, we need to divide it by 3, without using *, /, % operators. Well the question also mentions that itoa() function is available !!
13 7522
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
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
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
Stefaan,
Please read my algorithm more carefully.
Notice the line
- if sum > 10, repeat.
Thanks,
Sorry, the line should be:
- if sum > 9, repeat.
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.
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.
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.
- #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...
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.
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...
- cin >> num;
-
temp = num;
-
temp = temp>>2;
-
//here i have to add 1
-
temp += 1;
this is the easiest way
- 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
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Michael B. Trausch |
last post by:
I have a question regarding bitwise operators, I've been trying to
figure this out for about two days now, and I just can't seem to get it.
What I'm trying to do is use a variable to hold a bitmask...
|
by: Randell D. |
last post by:
Why would one use bitwise operators? I can program in various languages in
some shape or form (C++, PHP, some scripting) and I've heard/seen bitwise
operators before, but never understood why...
|
by: Mike Hodkin |
last post by:
As a beginning student of C++, books reference "bitwise operators" and give
brief examples, but I have not read a good explanation of what they are used
for. One reference mentioned that they are...
|
by: Christopher Benson-Manica |
last post by:
I'm trying to compute the absolute value of an integer using only bitwise
operators...
int x;
sscanf( "%d", &x );
printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
That works, but it...
|
by: jas_lx |
last post by:
The basic understanding of what bitwise operators (& ^ | >> << ) comes
fairly simple, as long as one has a fundamental understanding of bits,
bytes and binary.
Having done some Win32...
|
by: James Radke |
last post by:
Hello,
I found some code that I could use in my application on the web, but it is
written in C#, and I would like to convert it to VB. And I am having
problems with one section. Is there...
|
by: noridotjabi |
last post by:
I'm learning to program in C and any tutorial or book that I read likes
to briefly touch on birdies operators and then move on without giving
any sort of example application of them. Call me what...
|
by: Mark Rae |
last post by:
Hi,
This isn't *specifically* an ASP.NET question, so I've also posted it in the
ADO.NET group - however, it's not too far off-topic...
Imagine a SQL Server 2005 database with a table with an...
|
by: Santhosh |
last post by:
Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?
If we have n = 34
Result has to be 3,4.
Thanks a billion for...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |