# NOTES: EPI Ch4 Primitive Types

## Primitive Types

### 4.1 Parity

Parity fo a binary word is 1 if the number of 1s in the word is odd, o.w. is 0.

def parity(x):  # brute force
result = 0
while x:
result ^= x & 1
x >>= 1
return result  # O(n)

#------------------------ improve--------------------------#
# Trick: x & (x-1) equals x with its lowest set bit erased.#
# e.g. (00101100) & (00101011) = 00101000
#----------------------------------------------------------#

def parity_good(x):
resutl = 0
while x:
result ^= 1
x &= x-1  # drops lowest set bit of x
return result  # O(k) where k is the number of bits set (= number of 1's in the binary number)
## ex
parity(3)
0

### P4_1 count bits

count number of 1s in binary representation of an integer. (img source).

def count_bits(x):
num_bits = 0
while x:
num_bits += x & 1   # go through digit by digit
x >>= 1             # right shift 1 digit
return num_bits         # O(n)
def count_bits_recur(x):

# base case
if (x == 0):
return 0

else:
# if last bit set add 1 else