Bit Manipulation (Part II)

II. LeetCode questions

1. Single Number

  • Diagram:
a^a = 0
a^0 = a
a^b^a = (a^a)^b = 0^b = b
a^b^c^a^c = (a^a)^(c^c)^b = 0^b = b
  • Code:
# Time O(N) Space O(1)
def singleNumber(self, nums: List[int]) -> int:
output = 0
for num in nums:
output ^= num
return output

2. Single Number II

  • Diagram:
Solution 1, using dictionay, time O(N) space O(N)Solution 2. using sort, time O(NlogN) space O(1)Solution 3. Using set, time O(N) space O(N)
a+a+a+b+b+b+c+c = 3a+3b+2c
Solution 4. using bitwise XOR, time O(N) space O(1)
a XOR a = 0,
0 XOR a = a
a XOR a XOR a XOR b XOR b XOR b XOR c XOR c = a XOR b XOR c
  • Code:
#Time O(N) Space O(1)
def singleNumber(self, nums: List[int]) -> int:

seen_once = 0
seen_twice = 0
for num in nums:
seen_once = seen_once ^ num & ~seen_twice
seen_twice = seen_twice ^ num & ~seen_once
return seen_once

3. Simple Number III

  • Diagram:
a XOR b, a or b, but not both
a XOR 0 = a
a XOR a = 0
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
a XOR b XOR a XOR c = 0 XOR b XOR c = b XOR c
x & (-x) to isolate the rightmost 1-bit.
x & (-x) keep the rightmost 1-bit and to set all the other bits to 0
Brain Kernighan's algorithm a & (a-1), turn off the rightmost 1-bit
  • Code:
    # Time O(N) Space O(1)
def singleNumber(self, nums: List[int]) -> List[int]:

if not nums: return []

a_xor_b = 0
for num in nums:
a_xor_b ^= num

rightmost_1_bit = a_xor_b & (- a_xor_b)

a = 0
for num in nums:
if num & rightmost_1_bit:
a ^= num
return [a, a_xor_b ^ a]

4. Power of two

a. Solution I, using a&(-a), to get the rightmost 1-bit

  • Diagram:
a&(-a), to get the rightmost 1-bit                    -
a = 4 = 0000 0100
~4 = 1111 1011
-4 = ~4+1 = 1111 1100
4&(-4) = 0000 0100
_
pow(2,0) = 1 = 0000 0001
pow(2,1) = 2 = 0000 0010
pow(2,2) = 4 = 0000 0100
pow(2,3) = 8 = 0000 1000
pow(2,4) = 16 = 0001 0000
if we get the rightmost 1-bit of above number, then we just get the number itselfso, if a & (a-1) == a, then a is power of two
  • Code:
# Time O(1) Space O(1)
def isPowerOfTwo(self, n: int) -> bool:
if not n or n < 1: return False
return n == n & (-n)

Solution II, using Brain Kernighan’s algorithm, to turn off the rightmost bit of 1

  • Diagram:
Brain Kernighan's algorithm, to turn off the rightmost bit of 1                         -
a = 4 ---> 0000 0100
a-1 = 3 ---> 0000 0011
a&(a-1) = 4&3 ---> 0000 0000
-
pow(2,0) = 1 = 0000 0001
pow(2,1) = 2 = 0000 0010
pow(2,2) = 4 = 0000 0100
pow(2,3) = 8 = 0000 1000
pow(2,4) = 16 = 0001 0000
if we turn off the rightmost bit of above number, then we got 0000 0000so, if a & (a-1) == 0, then a is power of two
  • Code:
#Time O(1) Space O(1)
def isPowerOfTwo(self, n: int) -> bool:

if not n or n<1: return False
return n & (n-1) == 0

Software Engineer