Puzzle 1

Let’s talk about bit shifting!

Now I’m sure we all know this already, but since I’m nice and want to give you all a chance to seem smart, let’s do some basic review.

We know what binary is - 0’s and 1’s. So in binary, 101 is? Yes, 5. Now we have a couple bit shift operators.

Name Description Example
| Bit-wise or 101 | 111 = 111
& Bit-wise and 101 & 000 = 000
>> Right shift 101 >> 1 = 10
<< Left shift 101 << 1 = 1010

Great! So, here’s the easy question to help defrost your frigid brains.

Let’s assume an integer is 4 bytes (32 bits). What happens when I shift any int left 32 times? Example int x; x <<= 32; What must the value of x be?

If you said 0, give yourself a manicure. Congratulations. Yes, we pad with 0’s, so it must be zero.

What if I shifted right 32 (or more) times?

If you said 0 once again, great! Your brain is now fully defrosted. Let’s go to the actual puzzle.

Here’s my sample C program, in file stuff.c:

#include <stdio.h>

int main() {
    int b = 100000;
    printf("%d\n", b >> b);
    b = b >> b;
    printf("%d\n", b);
    b >>= b;
    printf("%d\n", b);
    return 0;
}

What should the program print out?

Should be all 0’s, right? I’m shifting by one hundred thousand (to heck with 32!). How could it be anything else?

Well then, let’s try it out.

If we do gcc stuff.c, we produce an executable file called a.out. (Remember, if you don’t like the standard a.out you can always use gcc stuff.c -o <yourname>.)

We execute this with ./a.out. And here’s the output.

100000
100000
100000

What the heck!? What’s going on here?

How do you debug this?

Debugging strategies are important. I don’t expect any of you to know the answer to this particular puzzle right off the bat; there’s no way at this point in the course do you have enough knowledge for that. But that’s precisely the point. You will run into these kinds of situations plenty of times in the real world, and having a good debugging strategy is critical. So I really want you to pause for a moment and consider what you would do.

Hypothesis 1: You think to yourself, “Self, maybe we were wrong. Maybe we can’t just do arithmetic math inside a printf like we do with b >> b.” Hmm, okay. Let’s test that out.

#include <stdio.h>

int main() {
    int b = 0;
    printf("%d\n", b+1);
}

A short compilation again, we run the program and get the following output: 1. Hmm, okay. So that can’t be it. And that makes sense. Because the second printf doesn’t do any arithmetic operation inside the printf.

What about another hypothesis?

Hypothesis 2: Maybe >>= is some funky thing that doesn’t do anything at all? Well, that can’t be right either. We tried b >> b, b = b >> b, and b >>= b. None of them worked!

A useful strategy when it comes to debugging is trying other ways of writing the code, just to see if it makes a difference. Usually we do this with small toy problems. Breaking the problem down in size is very, very useful. So let’s do that.

#include <stdio.h>

int main() {
    int b = 100000;
    for (int i = 0; i < 100000; i++)
        b >>= 1;
    printf("%d\n", b);
    
    return 0;
}

Okay, great. We’ve written a smaller, possibly even stupider, program that shifts 1 bit at a time instead of all at once. Is this even useful?

Well, let’s try it out and see! gcc stuff2.c, and a short ./a.out later, voila! We get 0 as an output!

Now things are really starting to get weird. Why does it work when we do it 1 bit at a time but not all at once!?

Let’s try another program - this seems a little too weird.

#include <stdio.h>

int main() {
    int b = 7;
    printf("%d\n", b >> 2);
}

Some quick bit shifting mental arithmetic later, we decide we want the answer to be 1. Remember, 7 is 111 in binary. So if we shift twice, we still have a single 1. Okay, so let’s try that. gcc stuff3.c, ./a.out. Sure enough, we get the expected answer!

So we can do multiple bits! Then why doesn’t 100000 work?

Hmm. What’s the best way we can search through this? We’re pretty sure that at some point shifting breaks, but we’re not sure where. Well, this is an algorithm you already know from cs1! 50000? Still breaks. 25000? Still breaks. Hmm, frustrating to be sure.

12500? Nope. 6250? Nada. 3125? Zilch. 1500? Still no! Dammit… 700? Wrong again. Man this sucks. 350? No change yet… Phew! Debugging is hard work! But we’re almost there. 175? Wrong. 50? Nope. 25? YES!

Woah. Works with 25, eh? Okay, what about 40? Nope! Hmm, between 25 and 40. 31? Yes! 32? Yes! 33? Nope! It stops working after 32 bits at a time.

Aren’t you glad you persisted through that? Now you have a tangible observation you can report to the TA/ professor / Google rather than just complaining that your program doesn’t work!

At this point it’s fair to consult additional resources for why on earth this could be happening, as you don’t quite have enough knowledge (yet!) to make an educated guess.

Well, it turns out that most gcc commands actually use C++ compilers, not C compilers (who would’ve thought that the GNU C Compiler would be a C++ compiler…). In C++, shifting by more than the size of an int (in this case, more than 32 bits,) is actually an undefined operation! Which means the compiler said hey, this undefined operation is mysterious. I don’t know what to do with it! So to speed things up, I’m just going to skip it and not do anything at all!

Which is why b >> 100000 still just evaluated to b!