Archived

This topic is now archived and is closed to further replies.

Adding 1 without using =, -, *, /

This topic is 4948 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

how would you do this function. I know what to do if its even thats easy. unsigned int AddOne(unsigned int x) { ... } that returns x + 1. The function must not contain the following symbols: +,-,*,/ also Imagine you are doing integer arithmatic and multiplication is computationally expensive. What''s a really quick way to multiply by the number 7?

Share this post


Link to post
Share on other sites
These sound very much like homework problems, and the rules here say answers to homework problems may not be given. Though it is allowed to give hints when the person asking shows they are trying, you did not do so.

Share this post


Link to post
Share on other sites
I actually got the question, "how do you multiply by 7 without using the multiply operator?" during an interview at EA. The answer to that one was easy, it was the follow up, "divide a number by 7 without using the divide operator" that I couldn''t figure out. No wonder I screwed up the interview.

--Wendy

Share this post


Link to post
Share on other sites
Not homework. I have tried a couple of things. But none have seemed to work I dont use alot of bit operators. I know how they work but I cant seem to solve this one.

For even you just flip the first bit. Hmm im going to keep trying if I get it ill repost

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Where I could research this would help. I dont need the answer. I just dont know where to begin looking for help.

Share this post


Link to post
Share on other sites
I could have sworn I''ve seen the answer to both of these right here on GameDev. Tried a search, though, and it was futile.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
yea there are other bitwise posts with these types of questions. But not on this one.

Share this post


Link to post
Share on other sites
quote:
Original post by wendy
I actually got the question, "how do you multiply by 7 without using the multiply operator?" during an interview at EA. The answer to that one was easy, it was the follow up, "divide a number by 7 without using the divide operator" that I couldn''t figure out. No wonder I screwed up the interview.

--Wendy


Division by seven is just as easy, you just have to basically go the other way with it (well not exactly, but if you play with it, you''ll get it).

Share this post


Link to post
Share on other sites
There may be more efficient ways of doing it but one way is to add the way you were probably taught in school. Start with the least significant digit, if it''s 0 make it 1 and you''re done. If it''s 1, make it 0 and carry one to the next position. Repeat until done.

Share this post


Link to post
Share on other sites
This (kind of) question is very common on a Programmer''s Test
during a job interview, before it for screening purpose.

I have seen this exact example in more than one of them.

Hint: It has to do with bitwise operators.



Kami no Itte ga ore ni zettai naru!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Matt thanks for the help. Took me a while to get what you were saying but that worked.

unsigned int add(unsigned int a)
{
unsigned int i = 1;
while(a & i)
{
a = a & ~i;
i = 1 << i;
}
return a | i;
}

Sweet. I was trying all kinds of shifts then masks. sigh thanks again.

Share this post


Link to post
Share on other sites
I plugged 31 into your add function and got 65544 out...

I''m not entirely clear on how it''s supposed to work so I won''t critque it. Anyway, my first thought was to use a lookup table.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
oops thanks. change it to i = i << 1; should work

Share this post


Link to post
Share on other sites
im curious as to the answers to these questions, i know bit shifting to the right (i think it was) can effectively multiply by 2 if i remember right, but how the heck do the division by 7 and the multiplication by 7 work? oh and the add one... lol, seriously though im immensley curious
-Dan

Share this post


Link to post
Share on other sites
quote:
Original post by mmmmm
how would you do this function.
I know what to do if its even thats easy.
unsigned int AddOne(unsigned int x)
{
...
}
that returns x + 1. The function must not contain
the following symbols: +,-,*,/

also

Imagine you are doing integer arithmatic and
multiplication is computationally expensive.
What''s a really quick way to multiply by the
number 7?


simple

if(!x&1)
x&=1; else
{
test for some other bits, quite simple really but to much labor for me
}

multiply by 7? isnt that: (x<<3)-x

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I knew how to multiply with any value, but divide is another thing ? ( apart from subtracting the value till the result is < 0 )

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Anonymous Poster
I knew how to multiply with any value, but divide is another thing ? ( apart from subtracting the value till the result is &lt; 0 )


(n>>3)+1

Share this post


Link to post
Share on other sites
quote:
Original post by Ademan555
im curious as to the answers to these questions, i know bit shifting to the right (i think it was) can effectively multiply by 2 if i remember right, but how the heck do the division by 7 and the multiplication by 7 work? oh and the add one... lol, seriously though im immensley curious
-Dan


x << 3 is like x*(23), which is like x*8, which is like x+x+x+x+x+x+x+x. We want one less x (x*7), so we subtract x, and get (x << 3) - x.

Share this post


Link to post
Share on other sites
// No addition! omg!

int add_one(int num)
{
std::vector<int> myvec(num);
myvec.push_back(0);
return myvec.size();
}

// No multiplication! omg!

int times_seven(int num)
{
std::valarray<int> myarr(num, 7);
return myarr.sum();
}

Share this post


Link to post
Share on other sites