# Binary Factorization.

# Every integer can be represented precisely in binary.  Each non-negative
# (absolute) value can be converted to base-2 by finding all the powers of
# 2 that adds up to the value.  For example, 86=64+16+4+2, 11=8+2+1, etc.
# The algorithm will look at each binary digit (bit) that make up the number,
# starting with the LEAST SIGNIFICANT (rightmost) bit, and move to the
# MOST SIGNIFICANT (leftmost) bit.

# The following program finds all the binary factors of a number and adds
# them to an array.  For example, for 86, it will construct [2,4,16,64].

n = abs(int(input("Enter Integer: ")))
n0 = n  # store copy of original for output
Factors = [] # start with empty array of factors
factor = 1   # the smallest factor is 1, which is 2**0
while n>0:
    bit = n%2  # this bit will be 1 or 0
    if bit==1: Factors.append(factor)
    n = n//2    # shift to next bit
    factor = factor*2  # value of next bit
# while
print("The binary factors of",n0,"are",Factors)

## Sample run:
# Enter Integer: 86
# The binary factors of 86 are [2, 4, 16, 64]

## Closely related to the binary factors of a number is its representation
# as a binary number.  First we have to decide how many bits to use: 8, 16,
# 32 or 64.  As an 8-bit value, for example, 86 is 01010110.

# The following program is very similar to the above, except it constructs
# a STRING of 1's and 0's so we can print the binary form of a number.

n = n0  # restore original input from above program
Binstr = ""  # start with empty binary string
while n>0:
    bit = n%2  # this bit is 1 or 0
    Binstr = str(bit) + Binstr  # concatenate bit to FRONT of string
    n = n//2   # shift to next bit
#while
print("The binary representation of",n0,"is",Binstr)

## Sample run:
#Enter Integer: 147
#The binary factors of 147 are [1, 2, 16, 128]
#The binary representation of 147 is 10010011


### Now let's go backwards: given a binary string such as "01001110", we 
# want to convert it to a (positive) integer.  Again it's best to start 
# at the rightmost (least significant) bit.

bi = len(Binstr)-1  # index of last char of binary string
num = 0 # number to convert to
factor = 1  # value of each bit, starting with 2**0
while bi>=0:  # stop at the most significant bit
    bit = int(Binstr[bi])  # value of current bit, 0 or 1
    num = num + bit*factor # add value of bit to number
    bi = bi-1              # index of next bit
    factor = factor*2      # value of next bit
#while
print(Binstr,"represents",num)

#Enter Integer: 29
#The binary factors of 29 are [1, 4, 8, 16]
#The binary representation of 29 is 11101
#11101 represents 29
    
# The representation of negative numbers (two's complement) is a bit more
# complicated ...