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:
0000 # zero
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 # ran out of symbols, so increment the symbol to the left, and restart
0011
0012 # 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:
0000 # zero
0001
0010 # ran out of symbols, so increment the symbol to the left, and restart
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100 # twelveClearly 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 # base 10
1 = 1 = 2^0
10 = 2 = 2^1
100 = 4 = 2^2
1000 = 8 = 2^3
10000 = 16 = 2^4
100000 = 32 = 2^5Binary 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.
11001 # number in binary
= 10000 + 01000 + 00001 # digits in binary
= 16 + 8 + 1 # digits in base ten
= 25 # number in base tenThis 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.
num =
+ a * 2^0
+ b * 2^1
+ c * 2^2
+ d * 2^3
+ ...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.
num = a + 2*b + 4*c + 8*d + ...This means if you mod number by 2, all of the terms vanish, except for a. This is how you find a:
a = num % 2You 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:
num = num // 2 # divide by 2 and round down
= b + c*2 + d*4 + ...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:
def binary(num):
binaryArr = []
while num > 0:
a = num % 2
binaryArr.append(a)
num = num // 2
return binaryArr[::-1] # reverse, since smallest digits come first
print(binary(6))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.
num = 0b101
print(num) # 5Bit 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.
# binary strings
print(bin(2)) # '0b10'
print(bin(42)) # '0b101010'
print(bin(42)[2:]) # '101010'
# numbers
a = 2 # 0010
b = 3 # 0011
c = 4 # 0100
# xor = ^
# returns 1 if digits are different
# returns 0 if digits are equal
print(a ^ c) # 6
# 0010
# ^ 0100
# = 0110
# shift left = <<
# equal to multiplying by 2, since every number doubles
print(a << 1) # 4
# 0010 << 1
# = 0100
# shift right = >>
# equal to dividing by 2 and rounding down, since every number halves
print(a >> 1) # 1
# 0010 >> 1
# = 0001
# and bits = &
print(a & b) # 2
# 0010
# & 0011
# = 0010
# or bits = |
print(a | b) # 3
# 0010
# | 0011
# = 0011
# negate bit
print(~b) # -4
# ~ 0011
# = 1100
# because of how two's complement works, effectively adds 1 and negates