• # Approach #1 Converting data type [Accepted]

Algorithm

1. convert `x`, `y` to binary representation with string type
2. (optional) filled with leading zeros
3. 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)
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

1. 5 / 2 = 2...1
2. 2 / 2 = 1...0
3. 1 / 2 = 0...1

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

e.g. 4

1. 4 / 2 = 2...0
2. 2 / 2 = 1...0
3. 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

1. convert to octal string prefixed with '0o'
• `oct` can convert integer to octal representation with string type
• `[2:]` create new string without prefix '0o'
2. 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
1. Plus least significant bit of i
2. 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)

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

e.g. 6 (110)

1. 6 > 1, calls f(3) + '0'
2. f(3): 3 > 1, calls f(1) + '1'
3. 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

1. XOR `x` and `y`
2. 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
``````

## 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
``````

#### & 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
``````

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

http://graphics.stanford.edu/~seander/bithacks.html

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
``````

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')
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.