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.