Cheat Sheets

Bit Manipulation

Lesson

Binary Intuition

When you think about numbers, you usually use "base ten". This just means that you have ten symbols avaliable for you to write numbers with. Here they are:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

You can write any number using these symbols by starting with the number 0, and counting upwards. If you run out of symbols to use, you increment the symbol to the left of the current symbol. For example, here's how you count up to the number twelve:

"Binary" is the same thing as "base ten", but where you only have two symbols to count with.

0, 1

Here's how you count to the number twelve in binary:

Clearly every number can be represented in binary since you can just count up to it.

Important

One really important intuiton that lets you derive everything else, is that each new digit in a binary number is a power of 2.

Binary to Base 10

To convert a binary number to base ten, you have to add up all the powers of two in the number. For example, here's how you convert the binary number 11001 to base ten.

This means the binary number 11001 is equal to the number 25.

Base 10 to Binary

If you want to convert a base 10 number to binary, like converting the number 25 to binary, you just need to figure out what powers of 2 make up the number. In other words, you need to find what a, b, c are in the equation below. For example, for 25, a = 1, b = 0, c = 0, d = 1, and e = 1, which tells you that 25 is 11001 in binary.

It turns out that you can always find a very easily. The trick is that all the terms are even, except for the a term.

This means if you mod number by 2, all of the terms vanish, except for a. This is how you find a:

You can then find the value of b in a similar way. To do this, you divide the number by 2 and round down, which removes the first term:

Now you can find b the same way you found a. You can repeat this over and over again to find all the digits. Here's the algorithm:

Notation

People often use 0b as a prefix to binary numbers. For example, 0b101 means "101" in binary (the number 5) to avoid confusing it with what you'd normally read as the number one-hundred-and-one.

Bit Manipulation

"Bit Manipulation" is when you take advantage of the fact that the computer stores numbers in binary. Here are some operations you can use. Each of these operations takes O(1) time, because computer hardware is built to immediately do these operations.

Mark as Completed:
Submits:
test
Test your code to get an output here!