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.
One really important intuiton that lets you derive everything else, is that each new digit in a binary number is a power of 2.
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.
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:
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" 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.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()