Thoughts for the Holidays and perhaps more…

“They are Man’s and they cling to me, appealing from their fathers. This boy is Ignorance and this girl is Want. Beware them both, and all of their degree, but most of all beware this boy for on his brow I see that written which is Doom, unless the writing be erased.”
Charles Dickens, A Christmas Carol

“But you were always a good man of business, Jacob,’ faltered Scrooge, who now began to apply this to himself.

Business!’ cried the Ghost, wringing its hands again. “Mankind was my business; charity, mercy, forbearance, and benevolence, were, all, my business. The deals of my trade were but a drop of water in the comprehensive ocean of my business!”
Charles Dickens, A Christmas Carol

“Men’s courses will foreshadow certain ends, to which, if persevered in, they must lead,” said Scrooge. “But if the courses be departed from, the ends will change.”
Charles Dickens, A Christmas Carol

“If they would rather die, . . . they had better do it, and decrease the surplus population.”
Charles Dickens, A Christmas Carol

“Man,” said the Ghost, “if man you be in heart, not adamant, forbear that wicked cant until you have discovered What the surplus is, and Where it is. Will you decide what men shall live, what men shall die?”
Charles Dickens, A Christmas Carol

Advertisements

Multiplication Using Bitwise Operations C++

I recently gave a class of mine the challenge to write a function which accepts two 32bit ints as parameters and returns their product without using the multiplication operator.  Many came up with something like this:

int bitwiseMult(int num1, int num2)
{
	int product = 0;

	//go through each bit of num2
	for (int i = 0; i < 31; ++i)
	{
		if (num2 & (1 << i))
		{
			product += (num1 << i);
		}
	}
	return product;
}

The general approach is to go through each bit of num2 and if the bit is set then shift num1 that many positions to the left and add that to the product.  The trick is to realize that left shifting multiplies a number by the power of 2 of the number of bits shifted.  For example:

1 << 0 = 1
1 << 1 = 2
1 << 2 = 4

13 base 10 = 1101 base 2
1101 << 2 = 13 * 4 = 52

13 base 10 times 5
( 1101 << 2 ) + ( 1101 << 0 ) = 
     52 + 13 = 65

This works fine when num1 and num2 are positive.  It even works when num1 is negative, but if num2 is negative there are problems:

please enter two integers to multiply:
1 -1

the result is: 2147483647

Huh?

Well after doing some Googling, it turns out that 1 << 31 is undefined in C++ and each compiler is free to do what it pleases.  We really just want that 32nd bit to be a sign bit but C++ doesn’t define the shift.  So my second go at it is:

int bitwiseMult(int num1, int num2)
{
	int product = 0;

	//1 means positive, -1 means negative
	int sign1 = 1, sign2 = 1;
	if (num1 < 0)
	{
		sign1 = -1;//mark correct sign
		num1 = -num1;//make negative numbers positive
	}
	if (num2 < 0)
	{
		sign2 = -1;//mark correct sign
		num2 = -num2;//make negative numbers positive
	}

	//go through each bit of num2
	for (int i = 0; i < 30; ++i)
	{
		if (num2 & (1 << i))
		{
			product += (num1 << i);
		}
	}

	if (sign1 != sign2)
		product = -product;

	return product;
}

Not so short and sweet anymore but it should still be relatively efficient.  I now check for the signs of both nums, make them both positive if they are not already.  Then I sum up the product as before but stop on the 31st bit.  Then I negate the sign of the product if the signs of the parameters differ.  Now it works like a charm!

Only one more thing bugging me – most numbers are pretty small and it seems wasteful to check all 31 bits for the number 2 (for instance).  So here is my 3rd and final version:

int bitwiseMult(int num1, int num2)
{
	int product = 0;

	//1 means positive, -1 means negative
	int sign1 = 1, sign2 = 1;
	if (num1 < 0)
	{
		sign1 = -1;//mark correct sign
		num1 = -num1;//make negative numbers positive
	}
	if (num2 < 0)
	{
		sign2 = -1;//mark correct sign
		num2 = -num2;//make negative numbers positive
	}

	//go through each bit of num2
	for (int i = 0; i < 30; ++i)
	{
		if (num2 == 0)
			break;
		if (num2 & (1 << i))
		{
			product += (num1 << i);
			num2 -= (1 << i);
		}
	}

	if (sign1 != sign2)
		product = -product;

	return product;
}

There are just a couple changes from the last version: I subtract the value of the just checked bit from num2.  This will make num2 get smaller and smaller.  Once we get to the last bit that is a 1 then num2 will equal 0.  If num2 is ever 0 we simply break out of our loop.  Should save a bit of processing if we generally only use the first few bits.  Of course, optimization, needs to be bench-marked so I can’t be sure this will save any time (perhaps the additional if is more costly than continuing the iteration of the loop, or the compiler might be smart enough to optimize this for you).  That’s it for now.  Let me know if you have any questions.

 

UPDATE:

I did this exercise again with my class this year and decided to code the solution up from scratch without referring to this blog post.  To my surprise, and a bit of embarrassment, my solution worked perfectly for all signed 32-bit integers.  Here’s the new code I wrote:

int bitMult(int num1, int num2)
{
	int product = 0;

	for (unsigned int i = 0; i < 32; i++)
	{
		if (num1 & ( 0x1 << i))
		{
			product += (num2 << i);
		}
	}

	return product;
}

It seems that all I had to do was to shift all 32 bits and ignore comments from the internet. Of course, I’ve only tested this code on my Windows box with MSVC2013 so the original comments that 1 << 31 is undefined in C++ could be correct and this only works in MSVC2013. If anyone tries this code and gets different results with a different compiler, please let me know.

Job Hunting Advice for Game Programming Senior Job Hunters

If you are serious about landing a job before the end of the school year here is some advice.  As always, you should be working with Career Services as they are the experts in this.  Consider anything I say here as additional advice above and beyond what Career Services has already told you.

Preparation

Take some time to see what’s out there.  What studios’ work do you admire?  What kind of jobs are they typically hiring for?  Do you want to work in a big studio or a small one?  Do you want to specialize or be a generalist?  Where (geographically) do you want to work?  If you want to work in a particular location look up the local IGDA chapter.  Many list member studios with links.  You may turn up some previously unknown gem!

Once you’ve answered some of these questions identify a list of studios which would constitute your “wishlist”.

At the same time make sure you have a portfolio site.  Put a wide range of projects on the site along with short samples of code that help illustrate something special you are doing on each project.  Mix in school projects with your own personal ones.  Any code you make available, make sure it is clean and concise.  No one will want to dig through lots of code and a good consistent coding style will make your code much more impressive.  Readability is everything with code samples.  Videos and screen shots are nice but make sure they relate to the coding not on the game in general.

Oh yeah, you need a professional Resume – Career Services again!

Investigation

Do you know anyone that works for one of these studios?  Find out where recent alumni are working and use them aggressively.  Alumni may be your greatest allies in getting the job you really want.  Ask professors if they know anyone at one of these studios.  When asking professors for personal contacts make sure that you have already done your homework on the studio in question.  This is where those years of cultivating good relations with your professors will really pay off.

Interviewing

Career services can really help with this one.  There are many books on how to prepare for technical interviews and someone at Career Services will be able to point you towards a few.  Make sure you have done as much homework as possible on the studio, what they do and the position available.  Make sure the interviewer feels like you have prepared for them.  They don’t want to feel like a number any more than you do.

Always be truthful in interviews.  If you feel like you don’t know the answer to a question, ask for clarification.  It may be that you know the concept but know it by a different name.

Don’t ask or answer questions about salary expectations during phone or early rounds of interviews.  If you’ve done your homework you should have a fair idea of what you can expect to make and what they can afford to pay and these conversations can wait for later after you’ve got them hooked!

Tests

Some studios rely heavily on programming tests, other do not.  As an entry level programmer you are more likely to be required to take a test.  There are books on how to do well on programming tests and Career Se5rvices can point your towards them.

One important thing to note is that most of these tests are geared towards Computer Science majors so you are likely to see questions from Data Structures and Algorithms and similar “CSey” subjects.  Most will expect you to have a strong handle on 3D math even if you are not applying for a Graphics Programming position.  Review your 3D math!

Reach out to alumni and ask them about the tests they have taken.  Many of these questions circulate around many studios so you may find a question you’ve heard already!

Offers

Ideally you will have more than one offer at once.  If you can picture yourself working for either company then go for the one with the more interesting position over one paying the most money.  The real money is to be made after you have proven yourself so make sure you are considering a studio which will allow you to grow in ways you want to.  Don’t forget when thinking about money that Boston or San Francisco are much more expensive places to live then Madison, Wisconsin.  They publish comparative cost-of-living data on the internet.

It’s also important to remember that you are not signing up for your entire lifetime.  You will change jobs many times in your career, just make sure that each job is taking you closer to what you really want to do in a place you really want to be.  Do plan on staying for at least 2 years in your first job but just be sure you will be moving in a direction you want to go.

Have a good life!

Remember that you work and career are very important but they are only part of being a happy person.  Make sure that they enhance your happiness, not take away from it.  Keep learning, keep communicating, keep striving and it will all work out great.

Don’t forget to payback to the next round of Seniors once you’ve found your dream job.  They will really appreciate it! Good luck.

Update:

GameDevMap is a very useful resource for job searching geographically.

 

Summary of happenings as discussed in meeting with Game Programmers

HackVT – 10/11 http://hackvt.com/

Tech Jam – 10/24-10/25 http://www.techjamvt.com/

Champlain College Internship Fair – 10/27-10/28  http://www.champlain.edu/career-success/career-services/fall-internship-fair

Registration starts (check WebAdvisor for your particular start time) – ends 10/28 – $200 late fee  http://www.champlain.edu/current-students/academic-information/registrars-office/classes-and-registration

Last day to drop classes without academic penalty: 10/24

CSI140 Study Session run by Dean Lawson: Thursday 10/9 – MIC308 8:30-10pm