Binary Recap and Notes

In the bullet points below, record 5 things that you already knew about binary before this lecture

  • Contains of 1s and 0s
  • Is base 2
  • Computers run on binary
  • Decimal numbers can be converted into binary
  • Similarly, strings can be represented with binary.

Binary is can be applied in many ways to store, access, and manipulate information. Think of three applications that rely on binary.

  • Computers
  • VS Code
  • Slack

Why is binary such an effective system for storing information? Why don't computers use the decimal system instead?

  • It is easier to represent information with on/off or 0s and 1s. Computers use electrical signals which rely on on and off.

Bitwise Opperations

Fill in the blank spots below during the lecture

Opearator Name Action
& AND Returns 1 if both inputs are 1, otherwise return 0
OR Returns 0 if both inputs are 0, otherwise return 1
^ XOR Returns true if 1 true and 1 false, returns false if 2 false or 2 true
~ NOT Inverse
<< Left Shift Integer bits are moved to the left
>> Right Shift Integer bits are moved to the right
>>> Zero-fill Right Shift Bits are shifted to the right. Excess bits are removed, zero bits are shifted in from the left.

In this program, the __bitwise operators__ & (AND), | (OR), ^ (XOR), and ~ (NOT) are used to perform the binary operations on the input numbers. The results are stored in separate variables as __decimal numbers__. Then, the _bin()__ function is used to convert each decimal result to binary, and the binary strings are stored in separate variables. Finally, the program returns a tuple of tuples, with each inner tuple containing both the decimal and binary result for each operation. The outer tuple is unpacked__ into separate variables for printing, and the results are displayed as both decimal and binary.

def binary_operations(num1, num2):
    # Perform the binary operations
    and_result_decimal = num1 & num2
    or_result_decimal = num1 | num2
    xor_result_decimal = num1 ^ num2
    not_result_decimal = ~num1

    # Convert results to binary
    and_result_binary = bin(and_result_decimal)[2:]
    or_result_binary = bin(or_result_decimal)[2:]
    xor_result_binary = bin(xor_result_decimal)[2:]
    not_result_binary = bin(not_result_decimal)[2:]

    # Return the results as a tuple of tuples
    return ((and_result_decimal, and_result_binary),
            (or_result_decimal, or_result_binary),
            (xor_result_decimal, xor_result_binary),
            (not_result_decimal, not_result_binary))

# Ask the user for input
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

# Call the binary_operations function and print the results
and_result, or_result, xor_result, not_result = binary_operations(num1, num2)
print("AND result: decimal =", and_result[0], ", binary =", and_result[1])
print("OR result: decimal =", or_result[0], ", binary =", or_result[1])
print("XOR result: decimal =", xor_result[0], ", binary =", xor_result[1])
print("NOT result: decimal =", not_result[0], ", binary =", not_result[1])
AND result: decimal = 1 , binary = 1
OR result: decimal = 5 , binary = 101
XOR result: decimal = 4 , binary = 100
NOT result: decimal = -2 , binary = b10

Bitwise operations are used in a variety of applications, particularly in low-level programming and computer science. Some common used of bitwise operations include:> - Flag Management: Flags are used to keep track of the state of a system or program__. Bitwise operations can be used to set, clear, and toggle flags.> - Bit Manipulation:Bitwise operations can be used to __manipulate individual bits__ in a binary number. This is often used to extract__ specific bits from a number, set specific bits to a particular value, or flip the value of specific bits.> - Masking:Masking is used to extract a _specific subset of bits __ from a binary number. Bitwise operations are commonly used for masking, particularly in low-level programming.> - Encryption:Bitwise operations can be used in cryptographic applications to scramble and unscramble data. One common application of bitwise operations in encryption is the XOR operation.> - Graphics:Bitwise operations can be used in computer graphics to manipulate individual pixels__ on a screen. This can be used to draw shapes, change colors, and create special effects.> - Networking:Bitwise operations are used extensively in networking__ applications, particularly in the handling of IP addresses and port numbers.

Binary to String Conversion

This program defines a string_to_binary function that takes a string as input and returns the binary representation of the string. The function uses a for loop to iterate over each character in the string. For each character, the ord function is used to get its ASCII code, which is then converted to binary using the format function with the '08b' format specifier to ensure that each binary number is 8 digits long. The resulting binary numbers are concatenated to form the final binary string.

# Function to convert a string to binary
def string_to_binary(string):
    binary = ''
    for char in string:
        binary += format(ord(char), '08b')  # Convert the character to binary and append to the binary string
    return binary

# Example usage
word = input("Enter a word to convert to binary: ")
binary_word = string_to_binary(word)
print(f"The binary representation of '{word}' is {binary_word}")
The binary representation of 'a' is 01100001

Many programs use binary conversion, particularly those related to computer science, electrical engineering, and mathematics. Programs that rely on binary conversion include:> - Networking: Programs that deal with network addresses, such as IP addresses and subnet masks, use binary conversion to represent and manipulate the addresses.> - Cryptography:Programs that deal with encryption and decryption use binary conversion to encode and decode data.> - Computer Hardware:Programs that interface with computer hardware, such as drivers and firmware, often use binary conversion to communicate with the hardware at the binary level.> - Mathematical Applications:Programs that deal with complex calculations and mathematical analysis, such as statistical analysis or machine learning algorithms, may use binary conversion to represent large numbers or complex data sets.> - Finance:Programs that deal with financial calculations and accounting may use binary conversion to represent fractional amounts or complex financial data.

  • An algorithm made to find an item__ from a list of items__
  • Works by dividing the list repeatedly to narrow down which half (the low or high half) that contains the item
  • Lists of integers__ are often used with binary search
  • Binary search makes searching more efficient, as it ensures the program won't have to search through an entire list of items one by one
  • List must be sorted

What are some situations in which binary search could be used?

  • Locating a number in a sorted list
  • Searching for a string in a sorted list
  • Search for the height of a person with people ordered from shortest to tallest
  • Guessing for a number with feedback on whether the guess is higher/lower.

Binary search operates a lot like a "guess the number" game. Try the game and explain how the two are similar.

import random 

hid = random.randint(0,100)
gues = 0
def game():
    global gues
    gues += 1
    num = int(input('Pick a number'))
    if num < hid:
        print('higher')
        game()
    if num > hid:
        print('lower')
        game()
    if num == hid:
        print(hid)
        print('You Win !!!')
        print('guesses: ', gues)
game()
lower
lower
12
You Win !!!
guesses:  3

Logic Gates

Accepts inputs and then outputs a result based on what the inputs were

  1. NOT Gate (aka inverter)
  • Accepts a single input and outputs the opposite value.
  • Ex: If the input is 0, the output is 1
  1. AND Gates
  • Multiple inputs
  • Accepts two inputs.
  • If both inputs "true," it returns "true."
  • If both inputs are "false," it returns "false."
  • What would it return if one input was "true" and the other was "false"? Discuss and record below.

  • It would return false.

  1. OR Gates
  • Accepts two inputs.
  • As long as one of the two inputs is "true," it returns "true."
  • If both inputs are "false," what would the OR gate return? Discuss and record below.

  • It would return false.

Universal Logic Gates

  1. NAND Gate
  • Accepts two inputs.
  • Outputs "false" ONLY when both of its inputs are "true." At all other times, the gate produces an output of "true."
  1. NOR Gate
  • Accepts two inputs.
  • Outputs "true" only when both of its inputs are "false." At all other times, the gate produces an output of "false."

Collegeboard Practice

Noor's Video

Hacks

  • Take notes and answer the questions above. Make sure you understand the purpose and function of the xample programs. (0.9)

  • Complete this quiz and attach a screen shot of your score below. If you missed any questions, explain why you got it wrong and write a short summary of your understanding of the content. (0.9)

  • As your tangible, create a program that allows a user to input two numbers and an operation, converts the numbers to binary and performs the given operation, and returns the value in decimal values. (0.9)

Applying Binary Math - Calculator Hack

Calculators use binary math to perform arithmetic operations such as addition, subtraction, multiplication, and division.In a calculator, the binary digits are represented by electronic switches that can be either on or off, corresponding to 1 or 0 respectively. These switches are arranged in groups of eight to form bytes, which are used to represent larger numbers. When a user enters a number into a calculator, the number is converted into binary form and stored in the calculator's memory.To perform an arithmetic operation, the calculator retrieves the numbers from its memory and performs the operation using binary math.

For example, to add the binary numbers 1010 and 1101, the calculator would perform the following steps:> 1. Add the rightmost digits, 0 and 1, which gives a sum of 1.> 2. Move to the next digit to the left and add the digits along with any carry from the previous step. In this case, we have 1 + 0 + 1, which gives a sum of 10. The carry of 1 is then carried over to the next digit.

  1. Repeat step 2 for the remaining digits until all digits have been added.
  2. The result of the addition in this example is the binary number 10111, which is equivalent to the decimal number 23.

Similarly, subtraction, multiplication, and division are performed using binary math. The algorithms for these operations are based on the same principles as those used in decimal arithmetic, but with binary digits and powers of 2 instead of decimal digits and powers of 10.

def binary_math(num1, num2, operator):
    # Write your calculator function here
    if operator == "+":
        result = add(num1, num2, operator)
        return result 
    if operator == "-":
        result = subtract(num1, num2, operator)
        return result 
    if operator == "*":
        result = multiply(num1, num2, operator)
        return result 
    if operator == "/":
        result = divide(num1, num2, operator)
        return result

def add(num1, num2, operator):
    #convert num1 and num2 to binary
    num1Str = binary(num1, num2, operator)[0]
    num2Str = binary(num1, num2, operator)[1]

    binaryString = "" #binary sum 
    total = [] #stores digits after each individual binary addition operation
    carry = False #carry over a 1 if 1+1
    for i in range(len(num1Str) - 1, -1, -1):
        #start from end of both binary numbers and add
        num1Digit = num1Str[i]
        num2Digit = num2Str[i]

        #add each individual digit's sum to list total
        if num1Digit == "0" and num2Digit == "0":
            if carry:
                total.append("1")
                carry = False
            else:
                total.append("0")
                carry = False
        elif num1Digit == "1" and num2Digit == "1":
            if carry:
                total.append("1")
                carry = True
            else:
                total.append("0")
                carry = True 
        else:
            if carry:
                total.append("0")
                carry = True
            else:
                total.append("1")
                carry = False

    #add a final 1 to list total if carry = true
    if carry:
        total.append("1")
        
    #go through list total backwards and append each element to binaryString 
    for i in range(len(total) - 1, -1, -1):
        binaryString += total[i]    

    #return result in decimal
    return int(binaryString, 2)


def subtract(num1, num2, operator):
    #convert num1 and num2 to binary
    num1Str = binary(num1, num2, "+")[0]
    num2Str = binary(num1, num2, "+")[1]
    

    binaryString = "" #binary sum 
    total = [] #stores digits after each individual binary addition operation
    borrow = False #carry over a 1 if 1+1
    for i in range(len(num1Str) - 1, -1, -1):
        #start from end of both binary numbers and add
        num1Digit = num1Str[i]
        num2Digit = num2Str[i]

        #add each individual digit's sum to list total
        if num1Digit == "0" and num2Digit == "0":
            if borrow:
                total.append("1")
                borrow = True 
            else:
                total.append("0")
                borrow = False
        elif num1Digit == "1" and num2Digit == "1":
            if borrow:
                total.append("1")
                borrow = True
            else:
                total.append("0")
                borrow = False 
        elif num1Digit == "0" and num2Digit == "1":
            if borrow:
                total.append("0")
                borrow = True
            else:
                total.append("1")
                borrow = True 
        elif num1Digit == "1" and num2Digit == "0":
            if borrow:
                total.append("0")
                borrow = False
            else:
                total.append("1")
                borrow = False 
       
    #go through list total backwards and append each element to binaryString 
    for i in range(len(total) - 1, -1, -1):
        binaryString += total[i]    

    
    i = 0
    while i < len(binaryString):
        if binaryString[i] == "1":
            break
        else: 
            binaryString = binaryString[1::]
    

    #return result in decimal
    return int(binaryString, 2)

def multiply(num1, num2, operator):
    #convert num1 and num2 to binary
    num1Str = binary(num1, num2, operator)[0]
    num2Str = binary(num1, num2, operator)[1]


    num2List = []
    for i in range(len(num2Str) - 1, -1, -1):
        num2List.append(num2Str[i])
    
    products = []
    for i in range(len(num2List)):
        for j in range(len(num1Str)):
            if num1Str[j] == "0" or num2List[i] == "0":
                products.append("0")
            else:
                products.append("1") 
        products.append("new")

    productsDict = {}
    productNum = None
    afterNew = True
    count = 0
    for i in range(len(products)):
        if afterNew == True and products[i] != "new":
            productNum = products[i]
            afterNew = False
        elif products[i] != "new":
            productNum += products[i]
        elif products[i] == "new":
            productsDict[count] = productNum
            count += 1
            productNum = None 
            afterNew = True
            
    for i in range(len(productsDict)):
        for j in range(i):
            productsDict[i] = productsDict[i] + "0"
    
    
    while len(productsDict) > 1:
        count = 0
        if len(productsDict) % 2 == 0:
            for i in range(0, len(productsDict), 2):
                sum = add(productsDict[i], productsDict[i + 1], "*")       
                productsDict.pop(i)
                productsDict.pop(i + 1)
                productsDict[count] = sum 
                count += 1
        if len(productsDict) % 2 == 1:
            for i in range(0, len(productsDict) - 1, 2):
                sum = add(productsDict[i], productsDict[i + 1], "*", True)       
                productsDict.pop(i)
                productsDict.pop(i + 1)
                productsDict[count] = sum 
                count += 1
    
    
    return int(str(productsDict[0]), 2)


def divide(num1, num2, operator):
    num = num1 
    divisor = num2

    numBinary = binary(num, divisor, "+")[0]

    currentDividend = 0
    result = 0
    for i in range(len(numBinary)):
        currentDividend = 2 * currentDividend + int(numBinary[i])
        if currentDividend > divisor: 
            currentDividend -= divisor
            result = 2 * result + 1
        else:
            result *= 2

    return result


def binary(num1, num2, operator):
    if operator == "+":
        num1 = bin(num1)[2::]
        num2 = bin(num2)[2::]
    if operator == "*":
        num1 = bin(int(num1))[2::]
        num2 = bin(int(num2))[2::]

    #format string so that both binary numbers have same number of digits
    if (len(num2) > len(num1)): 
        for i in range(len(num2) - len(num1)):
            num1 = "0" + num1
        return num2, num1
    elif (len(num1) > len(num2)): 
        for i in range(len(num1) - len(num2)):
            num2 = "0" + num2
        return num1, num2


# Ask the user for input
print("Enter \"exit\" to exit: ")
num1 = int(input("Enter the first number: "))
print("Enter the first number: " + str(num1))
while num1 != "exit":
    num1 = int(num1)
    num2 = int(input("Enter the second number: "))
    print("Enter the second number: " + str(num2))
    operator = input("Enter the operator (+, -, *, /): ")
    print("Enter the operator: " + operator)

    # Call the binary_math function and print the result
    result = binary_math(num1, num2, operator)
    print("Result:", result)


    num1 = input("Enter the first number: ")
    print("Enter the first number: " + str(num1))
Enter "exit" to exit: 
Enter the first number: 5
Enter the second number: 8
Enter the operator: +
Result: 13
Enter the first number: 8
Enter the second number: 5
Enter the operator: -
Result: 3
Enter the first number: 5
Enter the second number: 8
Enter the operator: *
Result: 40
Enter the first number: 100
Enter the second number: 7
Enter the operator: /
Result: 14
Enter the first number: exit