""" Thinking in Binary Computer science students must learn to think in base two. That means more than just knowing what number 01100101 represents. First, you will need to be comfortable using numbers that are powers of two (written 2**n in python). The numbers most people normally used are "decimal" or "base ten" numbers. The following while loop prints the first 11 powers of 2 as decimal numbers: """ n = 0 while n<=10: print(str(2**n) + "\t (2**"+str(n)+")") n = n+1 #while """The loop outputs the following: 1 (2**0) 2 (2**1) 4 (2**2) 8 (2**3) 16 (2**4) 32 (2**5) 64 (2**6) 128 (2**7) 256 (2**8) 512 (2**9) 1024 (2**10) YOU MUST MEMORIZE THESE FIRST POWERS OF TWO! Each number is double the previous number. We also call 2**10 "1K", because it's close to 1000, but it's actually 1024 in base-10. You might recall the following rule of powers: m**a * m**b == m**(a+b) For example, 2**3 * 2**5 == 2*2*2 * 2*2*2*2*2 == 2**8 == 8*32 == 256 Thus, 2**20 is 2**10 * 2**10, which is 1K * 1K (1K squared). We call 2**20 "1 Meg", because it approximates 1000*1000, which is one million. But it's actually 1048576 in base-10. Similarly, 2**30 is 2**10 * 2**10 * 2**10 (1K cubed) which approximates 1000 cubed, which is one billion. We call 2**30 "1 Gig". What is 2**27 then? Apply the same rule above: 2**27 == 2**7 * 2**20 == 128 * 1meg = 128 megs (or just 128M) 2**32 == 2**2 * 2**30 = 4 * 1gig = 4 gigs (4G) Similary, 2**40 = 1T (tera prefix), 2**50 = 1P (peta prefix) Did you ever buy a hard drive that's advertised as having something like "2 terabyte" capacity, but when you connect it to your computer, it shows up as having just 1.8 terabytes? Let's see why that is. Since most lowly earthlings can only think in base-10, "1 terabytes" means 1000**4, or 1 trillion bytes to them. But your computer's operating system uses base-2, and "1 terabyte" means 2**40, or 1024**4 bytes. Two terabytes should be 2*2**40 == 2**41. Divide 1 trillion by 2**40, and you get 0.909.. which is why the advertised "2 terabytes" is only 1.8 terabytes to the operating system. Quiz: What's 2**16 (please don't use a calculator - those are for earthlings) Answer: 64K (65536 in base-10, but you need to remember that it's 64K) What's 2**29? Answer: 512M It is crucially important you understand this numbering system. Now to understand what 01100101 represents, let's first break down a decimal number such as 5408: think of it as 5**1000 + 4**100 + 0*10 + 8*1, or 5*10**3 + 4*10**2 + 0*10**1 + 8*10**0. Starting at the rightmost digit as the 0th digit (also called the "least significant digit"), the nth digit of a decimal number has value 10**n multipled by the "coefficient", which in this case are 5, 4, 0 and 8 (the coefficient is always 0-9). A binary or base-two number has a similar structure, but there are two key differences: 1. The nth digit (starting with digit 0 on the right) has base value 2**n 2. The coefficient of each digit is always either 0 or 1. Thus to read a number such as 1101, it's better to start at the rightmost digit, which has value 2**0 ==1. This number is therefore 1*2**0 + 0*2**1 + 1*2**2 + 1*2**3 = 1 + 0 + 4 + 8 = 13. EXERCISE: What is 01100101 as a decimal (base-10) number? The following program finds and returns an array containing all the "binary factors" of a positive integer. That is, all the powers of 2 that adds up to the number: """ def binfactors(n): BF = [] # bin factors to be returned factor = 1 # intitial factor, 2**0 while n>0: if n%2==1: # look at least significant (rightmost) digit BF.append(factor) n = n//2 # shift over all digits to the right (n= n >> 1) factor = factor*2; # go to next factor # while return BF num = int(input("enter positive integer: ")) print(binfactors(num)) """To convert in the inverse direction, given a number such as 146, how do we represent it in binary? We similary need to break it down into perfect powers of 2: 147 = 128 + 16 + 2 + 1 = 2**7 + 2**4 + 2**1 + 2**0 Therefore 147 in binary is 10010011. Exercise: use the above program to find the binary representation of 5408. Challenge: What is the largest number that can be represented with 8 binary digits? 9 binary digits? Can you generalize this property? THE LOG FUNCTION The inverse of taking the power of some number is to take the log of a number: if m**n == x, then log base m of x == n. Thus log base 2 of 32 is 5 because 2**5 = 32, and log base 2 of 64K = 16, etc. The logarithm is one of the most important mathematical concepts to understand in computer science. Python has a built-in log function in its math library: math.log(n) computes the natural log of n and returns a floating point number. The natural log of n is the power of the constant math.e (2.71828..) so that math.e**p==n. Python also has a convenient math.log2(n) function that returns log_base_2. However, most programming languages will only give you the natural log. So it's helpful to remember the following formula: log_base_a of n == ln(n)/ln(a) where ln stands for natural log. In computer science we are typically interested in log_base_2 instead of the natural log. But it's also important to remeber that the logs of different bases are always different only by a constant factor. In fact, log_base_a of n = (log_base_b of n) * ln(b)/ln(a) """ from math import log print("log_base_2 of 256 is", log(256)/log(2)) # prints 8.0 ### we can also write our own version of the log2 function that works ### on positive integers as follows: def log_base_2(n): if n<1: raise Exception("undefined"); answer = 0 while n>1: answer = answer+1 n = n//2 return answer print(log_base_2(256)) ############## HEXADECIMAL ############### """ Looking at binary data one bit at a time is cumbersome for humans so they invented a notation for base-16 numbers called hexadecimal. Base-16 is closer to binary than base-10 because each hex digit corresponds to exactly four binary digits. Each digit can have value 0-15, represented by the numbers 0-9 and by the letters A-F: Hexadecimal numbers are usually prefexed with 0x. """ HEXDIGITS = "0123456789ABCDEF" HEXVALUES = {'A':10, 'B':11, 'C':12, 'D':13, 'E':14, 'F':15} for i in range(0,10): HEXVALUES[str(i)] = i # add digits '0' to '9' to dictionary. # can also add the values for the letters with: # for i in range(65,ord('F')+1): HEXVALUES[chr(i)] = i-55 """ A number such as 0x2AE is equivalent to (in base-10 notation): 2*16**2 + 10*16**1 + 14*16**0 = 512 + 160 + 14 = 686 The following is a routine that translates a hexadecimal string into an integer """ def decode_hex(hexstr): # returns non-negative integer if hexstr[0:2] != "0x": raise Exception("not in hex format") answer = 0 factor = 1 # corresponds to 16**0, to be multiplied by 16 after each loop iteration i = len(hexstr)-1 # start at right end (least significant digit) while i>=2: # stop at character 3, first 2 chars are '0x' # convert char to upper case: ascii_val = ord(hexstr[i]) if ascii_val>=97: ascii_val -= 32 # make it upper case, 97==ord('a') digit_value = HEXVALUES[ chr(ascii_val) ] # value 0-15 for ith digit # above line will result in error if char is not a hex digit answer += digit_value*factor factor = 16*factor # next power of 16 i = i-1 return answer #decode_hex print(decode_hex("0x7e5")) # lower case doesn't matter, prints 2021 decoded = decode_hex("0x2AE") """ You shouldn't think of this function as 'converting from base-16 to base-10'. All numbers are binary (base-2) to the computer. It is just a matter of how you want to see it. Most humans like to see it in base-10. What the above function does is take a base-16 string representation of a number and return the number itself. It returns a NUMBER, it is the SAME number expressed in any base: 12 == 0b1100 == 0xC The following function is the inverse of decode_hex: it converts a non-negative integer into a hex string in a certain number of bytes (each byte = 8 bits = 2 hex digits) """ # encode_hex returns hex string such as "0x07E6" in default 4 digits=2 bytes def encode_hex(n, numbytes=2): hexstr = "" numdigits = numbytes*2 # 2 hex digits per byte while n>0: digit_value = n%16 # value of last 4 bits/last hex digit, 0-15 hexstr = HEXDIGITS[digit_value]+hexstr # adds letter 0-9A-F to front of hexstr n = n//16 # same as n >> 4 : shifts n 4 bits to the right #end while loop, now pad with 0s so it's of right length: hexstr = ((len(hexstr)