# Approach #1 Converting data type [Accepted]

**Algorithm**

- convert
`x`

,`y`

to binary representation with string type - (optional) filled with leading zeros
- compare each bit one by one

**Python**

```
def hammingDistance(self, x, y):
# convert decimal+integer to binary+string
y_bin_str = self.dec_to_bin(y)
x_bin_str = self.dec_to_bin(x)
# filled with leading zeros
while len(y_bin_str) != len(x_bin_str):
if len(y_bin_str) < len(x_bin_str):
y_bin_str = '0' + y_bin_str
elif len(y_bin_str) > len(x_bin_str):
x_bin_str = '0' + x_bin_str
# compare different bits
dif_bit_num = 0
for i in range(len(x_bin_str)):
if x_bin_str[i] != y_bin_str[i]:
dif_bit_num += 1
return dif_bit_num
def dec_to_bin(self, i):
if i == 0:
return '0'
i_str = ''
while i > 0:
if i % 2 == 1:
i_str = '1' + i_str
else:
i_str = '0' + i_str
i = int(i / 2)
return i_str
```

## 2 common way to convert decimal-integer to binary-string

#### % 2: get least significant bit

- Current quotient becomes next dividend
- When current quotient is equal to zero, ends it
- Take remainder from the bottom to the top

e.g. 5

- 5 / 2 = 2...1
- 2 / 2 = 1...0
- 1 / 2 = 0...1

Take remainder from the bottom to the top: `101`

e.g. 4

- 4 / 2 = 2...0
- 2 / 2 = 1...0
- 1 / 2 = 0...1

Take remainder from the bottom to the top: `100`

```
def dec_to_bin(i):
if i == 0:
return "0"
s = ''
while i > 0:
if i % 2 == 1:
s = '1' + s
else:
s = '0' + s
i = int(i / 2)
return s
```

#### & 1: check least significant bit is 1 or 0, because when least significant bit is 0, it means this number is power of 2

e.g. 4 (100)

4 & 1 = 100 & 001 = 000

e.g. 3 (11)

3 & 1 = 11 & 01 = 01

```
def dec_to_bin(i):
if i == 0:
return "0"
s = ''
while i > 0:
if i & 1 == 1:
s = "1" + s
else:
s = "0" + s
i = int(i/2)
return s
```

## 2 advanced way to convert decimal-integer to binary-string

#### Convert to other positional numeral system and concatenate together

- convert to octal string prefixed with '0o'
`oct`

can convert integer to octal representation with string type`[2:]`

create new string without prefix '0o'

- according to decimal number to concatenate proper octal string

```
def dec_to_bin(i):
s = ''
dec_to_oct = {'0': '000', '1': '001', '2': '010', '3': '011', '4': '100', '5': '101', '6': '110', '7': '111'}
for bit in oct(i)[2:]:
s += dec_to_oct[bit]
return s
```

#### Recursion

Base case:

If it only contains one bit, just return it

Recursive case:

- i & 1: get least significant bit of i
- 101 & 1 = 001 = 1
- 100 & 1 = 000 = 0

- i >> 1: (shift bits to right) proceed to next least significant bit of i
- 110 >> 1 = 11
- 100 >> 1 = 10

- Plus least significant bit of i
- make recursive call with shifting bits to right so that we can proceed to the next least significant bit

```
def dec_to_bin(i):
return str(i) if i <= 1 else dec_to_bin(i >> 1) + str(i & 1)
```

e.g. 5 (101)

- 5 > 1, calls f(2) + '1'
- (2): 2 > 1, calls f(1) + '0'
- f(1): 1 <= 1, return '1'

e.g. 6 (110)

- 6 > 1, calls f(3) + '0'
- f(3): 3 > 1, calls f(1) + '1'
- f(1): 1 <= 1, return '1'

**Complexity Analysis**

- Time complexity : $$O(n)$$.

`dec_to_bin`

is $$O(n)$$- it needs to iterate through whole bits: $$O(len(x)) = O(n)$$

- filling leading zeros is $$O(|len(x)-len(y)|)$$
`for`

loop used to compare is $$O(len(x)) = O(n)$$

- Space complexity : $$O(n)$$.

`x_bin_str`

, `y_bin_str`

are both $$O(n)$$

# Approach #2 Bit Manipulate [Accepted]

**Intuition**

To find out how many different bit, we can simply do `xor`

and calculate how many number of bits is 1.

**Algorithm**

- XOR
`x`

and`y`

- get how many number of bits is 1

**Python**

```
def hammingDistance(self, x, y):
# XOR x and y
x_xor_y = x ^ y
# calculate how many number of bits are 1
return self.get_ones_count(x_xor_y)
def get_total_ones(self, n):
'''
every time you perform the operation n & (n-1), a single 1 bit is erased
'''
total = 0
while n != 0:
n = n & (n - 1)
total += 1
return total
```

## 3 common way to calculate how many number of bits are 1?

#### iterate through loop with string type

```
total = 0
for i in range(len(bin_str)):
if bin_str[i] == 1:
total += 1
return total
```

#### & 1: check wether least significant bit is 1 each time

- e.g. 5 (101)

101 & 1 = 101 & 001 = 1 (least significant bit is 1)

- e.g. 4 (100)

100 & 1 = 100 & 001 = 0 (least significant bit is not 1)

```
total = 0
while num != 0:
if num & 1 == 1:
total += 1
num = num >> 1 # shift right to get next least significant bit
return total
```

#### n & (n-1): remove a single 1 bit each time

Least significant 1 bit of x will not on the original position after being subtracted by 1, so `AND`

both number causes this position to be zero

- e.g. xxxx10 (x is 1 or 0 doesn't matter because
*subtracting 1 only affect least significant 1 bit*)

xxxx10 & xxxx01 = xxxx00 (Least significant 1 bit is removed)

- e.g. xxxx01

xxxx01 & xxxx00 = xxxx00 (Least significant 1 bit is removed)

- e.g. xxxx11

xxxx11 & xxxx10 = xxxx10 (Least significant 1 bit is removed)

```
total = 0
while num != 0:
num = num & (num-1)
total += 1
return total
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.

You needs both bits of x and y to be compared, so time complexity is $$O(length of bits) = O(n)$$

- Space complexity : $$O(n)$$.

`x_xor_y`

is $$O(n)$$, although it can be avoided.

# Approach #3 Built-in function

**Java**

```
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
```

**Python**

```
def hammingDistance(self, x, y):
return bin(x^y).count('1')
```