Cheat Sheets
Bit Manipulation
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.
People care about binary because modern hardware is built on top of binary logic gates and binary storage. It turns out that binary is not fundamental to computer science. Instead, data structures are fundamental to computer science. Data structures have nothing to do with binary, and instead are represented best by using pointers.
Binary to Number
Each digit in a binary number is a power of 2. Here are the first few binary digits, and their value in base ten:
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.
Number to Binary
Here's how you convert any number to binary, like converting the number 25 to 11001. In binary, every number is written as a sum of powers of 2. This means the first step to converting a number to binary is writing it out like this:
If you can figure out a, b, c, d for your number, then you can write the number in binary.
For example, the number is 13 is written as 1101 in binary. This means that it has the coefficients a = 1, b = 0, c = 1, and d = 1.
It turns out that you can find very first coefficient a very easily. The trick is that all the terms are even, except for the very first term.
This means if you mod number by 2, all of the terms vanish, except for the very first term. This gives you the value of 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:
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.