#### Testing if the right most bit is equal to 1 (or 0)

The number 1 when converted to binary has **leading **zeroes. When a number is **AND**-ed with 1, it will **only **produce 1 if the right most bit of the number is equal to 1. By itself, this information if not very useful as it only operates on position 0 of a binary number. It is however possible to "*traverse*" a binary number as seen in the next section

**AND**-ed with another "

*test*" number, which has only one bit set, it will produce the test number. This can be use to infer whether a bit at a particular position of number is either set to 1 or 0.

#### Traversing the digits in a binary number

The **shift **operator moves a binary number's bits to the *right *or the *left*. This effectively halves or doubles a number.

#### Setting the right most bit to 1

And finally, we can set the right most bit using **OR **and the number **1 **

# Solving the probem

Both parts of the problem require determining how many One or Zero bits are present in each position. The function below accepts a list of binary numbers -

- Tests the right most bit of the numbers, and increments a counter stored in an array.
- The counter array is indexed by the positions of the bit in the numbers.
- Each bit in the number is traversed by shifting right.
- The position is incremented to reflect the current position.

def getPositionsOfAboveAverageOneBits(binaryLines, lineLen): counter = [ 0 for i in range(lineLen) ] for num in binaryLines: pos = 0 while num != 0: counter[pos] += num & 1 num >>= 1 pos += 1 print(counter) return [ True if i >= len(binaryLines)/2 else False for i in counter ]

#### Part A

In order to determine the gamma and epsilon values, we need to rebuild a binary number based on the number of occurrences of the 1 and 0 bits in the various positions.

- We can start from the left most counter
- If there are above average one bits, the right most bit of gamma is set to one
- If there are above average zero bits, the right most bit of epsilon is set to one
- In either case, both gamma and epsilon are shifted left so that we can move on to the next left most position
- At the end of the iteration we have both gamma and epsilon values

def getGammaAndEpsilonFromOneBitCounter(positionsOfAboveAverageOneBits): gamma = 0 epsilon = 0 for i,aboveAverageOneBits in enumerate(reversed(positionsOfAboveAverageOneBits)): if aboveAverageOneBits: # common 1 bit gamma |= 1 else: epsilon |= 1 # don't want to shift if this is the last one if i < len(positionsOfAboveAverageOneBits)-1: epsilon <<= 1 gamma <<= 1 return gamma,epsilon

#### Part B

*filtered values*and

**NOT**the original set of values.

- The common counter function defined earlier is useful here as it can be called to determine the counts of 1 or 0 bits in the current position of the filtered values
- The
**AND**operator is used to tests each bit position. Unlike part 1 however, we create a test value - The
**XOR**operator serves to toggle whether we are searching for 1 or 0 in a particular position - The
**XOR**operator is also used to toggle whether we are looking for the O2 or C02 values

def getO2CO2Numbers(candidates, lineLen ,o2Toggle=True): position = lineLen - 1 # start with the left most bit # keep filtering the candidates until we have only one number while len(candidates) != 1: oneBitToggle = getPositionsOfAboveAverageOneBits(candidates,lineLen)[position] test = 1 test <<= position candidates = [ c for c in candidates \

if ((c & test == test) ^ (not oneBitToggle)) ^ (not o2Toggle) ] position -= 1 # move right to the next bit return candidates[0]