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

[back]