## Leetcode 20191225

The Operators:

x « y

Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.

x » y

Returns x with the bits shifted to the right by y places. This is the same as //‘ing x by 2**y.

x & y

Does a “bitwise and”. Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it’s 0.

x | y

Does a “bitwise or”. Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it’s 1.

~ x

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

x ^ y

Does a “bitwise exclusive or”. Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it’s the complement of the bit in x if that bit in y is 1.

Just remember about that infinite series of 1 bits in a negative number, and these should all make sense.

## Bitwise operators

### 191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/description/

```
class Solution:
def hammingWeight(self, n: int) -> int:
count, mask = 0, 0b1
for _ in range(32):
if n & mask != 0:
count += 1
mask <<= 1
return count
if __name__ == '__main__':
assert Solution().hammingWeight(0b00000000000000000000000000001011) == 3
```

**32 ms 12.8 MB**

### 136. Single Number

https://leetcode.com/problems/single-number/description/

```
class Solution:
def singleNumber(self, nums):
x = 0
for item in nums:
x = x ^ item
return x
if __name__ == '__main__':
assert Solution().singleNumber([4, 1, 2, 1, 2]) == 4
```

**88 ms 15 MB**

#### Alternative solutions:

```
class Solution:
def singleNumber(self, nums: List[int]) -> int:
import functools
return functools.reduce(lambda x, y: x ^ y, nums)
```

### 461. Hamming Distance

https://leetcode.com/problems/hamming-distance/

```
class Solution:
def hammingDistance(self, x, y):
raw, count, mask = x ^ y, 0, 1
for _ in range(32):
if raw & mask:
count += 1
mask <<= 1
return count
if __name__ == '__main__':
assert Solution().hammingDistance(1, 4) == 2
```

**24 ms 12.8 MB**