CSE 202 Project

Our first assignment for Computer Organization and architecture was to make a bunch of functions using only bit-wise (and a few logical) operators. At first, most of the functions we were asked to make sounded pretty easy. Like count and return the number of 1’s in a 32-bit int. Just a simple problem of making a counter variable and incrementing it by x&1 (this will look at just the rightmost bit of x, and give 1 if it is 1 and 0 if it is 0), then shifting x to the right. The biggest problem with that was that we were given a maximum of 40 operations to solve this. And for that solution with 32 bits, you needed a +,&, and >> for each one, making it take way more than 40 operations. I eventually thought to do it in chunks (when my professor hinted at it during class), so that I was looking at 2 positions in x at a time. But even that would take too many operations. So I cut it down to 4 at a time with a mask of 0x01010101 (this is in hex. In binary it would look like 00000001….00000001), and that got me just at 40 operations. After working on some of the other problems for a while, I came back to this one to optimize it and used a mask of 0x11111111 (this looks like 00010001….0001 in binary) to look at 8 positions at a time. Then I found a cool way to more efficiently add them all to the ones spot in my counter variable. This problem alone took me at least an hour, and there were 14 others that were a lot like this one.

But as I got the hang of working with bits, and learning some cool tricks about them along the way, each problem became easier to handle as I had a wider base to work with. Some were very easy, like return the absolute minimum value possible for a signed 32-bit int, which only took one operation. Others became very complicated, like computing the log base 2 of the input. Overall, this project was really fun but also really challenging. 

Advertisements

About lutyler15

I'm a Lehigh student planning on majoring in Computer Science and minoring in Japanese. I am the community coordinator for Lehigh's "Technology in Society" housing. I really enjoy video games and programming, so technology suits me!
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s