[stayscrisp]

After some feedback from the previous question I thought it might be interesting to split this post into two questions. One is more technical to broaden or test your knowledge and the other is a more general interview question.

The second question is just something that might possibly pop up in an interview and you don't need to post the answer here. If you have tips for answering the question then post them.

So post your answer to question one in spoiler tags and have a good think about question two

Question 1 : Technical Question

Using bitwise (or bit shift) operators, can you optimise the following examples?

1. int a = b * 4; 
2. int a = b * 72;
3. int a = (b + c) / 2;
4. int a = (b * 3) / 8;
5. int a = (b % 8) * 4;

Question 2 : General Interview Question

What's the best game of all time and why?

I look forward to seeing your answers

This post has been edited by stayscrisp: 11 February 2011 - 02:27 PM

[ButchDean]

For question 1 do you mean 'bit shift'?

[xTorvos]

1. I suck with bit twiddling and I may even be doing this completely wrong, but I'll post one anyway.

Spoiler

1. int a = b << 2; 
2. int a = (b << 3) * 9;
3. int a = (b + c) >> 1;
4. int a = (b * 3) >> 3;
5. int a = (b % 8) << 2;

Criticism and a better answer is appreciated.

2. Pacman. It's not my favorite game (that's Legend of Zelda: Ocarina of Time), but I think it's the best game of all time because it has enchanted the hearts of millions. You would be hard-pressed to find a person in the United States that has never heard of, seen, or played a game of Pacman.

This post has been edited by xTorvos: 11 February 2011 - 11:41 AM

[Fib]

I'm definitely a noob at this, but i'm going to try anyway.

Spoiler

1. int a = b << 2;
2. int a = b << (6 | 3);
3. int a = (b | c) >> 1;
4. int a = (b * 3) >> 3;
5. int a = (b % 8) << 2;

How much would this speed up your code? Would anyone notice a difference in the speed if all operations were done bitwise? Also, would one be expected to learn this in school? I'm a junior in a computer science program and I have never learned this before.

Let me know if I did it correct, if not then let me know what I did wrong please.

I think my favorite game of all time is The Legend Of Zelda: A Link to the Past. Just wanted to throw that in there

This post has been edited by Fib: 11 February 2011 - 12:30 PM

[ghillieLEAD]

Can't see what other people have done on my phone, the show spoiler button doesn't seem to work on the iPhone. I hope I'm not just adding the same stuff other people have done. Some of these I'm not sure if they're even much faster. I gave it a shot at least.

Spoiler

int a = b << 2;
int a = (b << 6) + (b << 3);
int a = (b + c) >> 1;
int a = ((b << 2) - B)/> >> 3;
int a = (b & (8 - 1)) << 2;

[stayscrisp]

ButchDean, on 11 February 2011 - 06:09 PM, said:

For question 1 do you mean 'bit shift'?

I would think that bit shift could be encompassed into bitwise. I know that they aren't due to the fact that bit shift does not operate on pairs of bits, but hey!

[ButchDean]

stayscrisp, on 11 February 2011 - 07:30 PM, said:

ButchDean, on 11 February 2011 - 06:09 PM, said:

For question 1 do you mean 'bit shift'?

I would think that bit shift could be encompassed into bitwise. I know that they aren't due to the fact that bit shift does not operate on pairs of bits, but hey!

It's just a bit more specific.

[ghillieLEAD]

ButchDean, on 11 February 2011 - 12:38 PM, said:

stayscrisp, on 11 February 2011 - 07:30 PM, said:

ButchDean, on 11 February 2011 - 06:09 PM, said:

For question 1 do you mean 'bit shift'?

I would think that bit shift could be encompassed into bitwise. I know that they aren't due to the fact that bit shift does not operate on pairs of bits, but hey!

It's just a bit more specific.

I used an AND in one of mine.

[ButchDean]

One of your answers I'm liking guys... the rest I'm not.

[stayscrisp]

The first person to spot a pretty small optimisation in number 4 gets a prize

[stayscrisp]

Some tips

Spoiler

The << operator shifts bits to the left.
The >> operator shifts bits to the right.

Shifting a bit 1 to the left is the same as multiplying by 2 and shifting by 2 is like multiplying by 4 etc.
Shifting to the right is the same as division.

[stayscrisp]

ghillieLEAD's answers are looking almost spot on

This post has been edited by stayscrisp: 13 February 2011 - 09:01 AM

[Filox]

I don't know if its the best optimization but here its my solution:

Spoiler

1. int a = b << 2;
2. int a = b << 6 + b << 3;
3. int a = (b+c) >> 1;
4. int a = (b << 1 + B)/> >> 3;
5. int a = ((b << 3) >> 3) << 2;

This post has been edited by Filox: 12 February 2011 - 12:54 PM

[e_i_pi]

Hmm, I've never done bitshift operations, but I have a fair amount of maths behind me, so I'll have a go:

Spoiler

1. int a = b << 2;
2. int a = (b << 6) + (b << 3);
3. int a = (b + c) >> 2;
4. int a = ((b << 2) + B)/> >> 3;
5. int a = (b - ((b >> 3) << 3)) << 2  (Assuming unsigned int)
...but I think it can also be done like this (in PHP at least)...
5. int a = (b & 7) << 2

As for the best game of all time (assuming you're talking about electronic games) I'd say Dwarf Fortress would have to be up there. The interface may be clunky, the graphics just ASCII, and the learning curve steep, but the gameplay factors are absolutely astonishing. The diversity and complexity of the game are pretty much unrivalled by any other game ever made, and the possibilities in it are endless (it's an open-ended game). Not to mention the amount of cross-disciplinary tertiary level knowledge the developer has put into it, such as Geology, Meteorology, History, and Sociology.

This post has been edited by e_i_pi: 13 February 2011 - 09:08 AM

[stayscrisp]

I'm surprised no-one has done this yet

Spoiler

4. int a = ( b + b + b ) >> 3;