[Leetcode] Bit Manipulation

Posted on | In , |

Introduction

Video: https://www.youtube.com/watch?v=NLKQEOgBAnw&t=189s

Two’s Complement

Notes: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

8-bit integer, Use first slot to represent the sign of the number. 0 => +, 1 => -

1
2
3
4
18  :  00010010 + ? = 00000000 
00010010 + 11101101  => 011111111
011111111 + 1 = 100000000
-18 :  11101101 + 1 = 11101110

Shifting

Logical & Arithmatic

1
2
3
4
5
6
7
8
00010111 => 23
left shift: <trash>00101110 => 46 = 23 * 2
right shift: 00001011<trash> => 11 = 23 / 2


11101000 => -23
Logical shift: left: 01110100 => 116 
Arithmatic shift: left: 11110100 => -12

Masks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0 & 0 = 0
0 & 1 = 0
1 & 1 = 1

0 | 0 = 0
0 | 1 = 1
1 | 1 = 1

0 ^ 0 = 0 # XOR: get exactly one of those to be 1
0 ^ 1 = 1
1 ^ 1 = 0

~ 0 = 1
~ 1 = 0

Get kth bit
  00101100
& 00100000 test if third slot is 1
= 00100000
Could be represented by: (x & (1<<k)) != 0

Set kth bit
  00101100
| 00100000
= 00101100 (x | (1<<k))

Clear kth bit
  00101100
& 11011111
= 00001100 (x & (~(1<<k)))

Parity Check
Parity checks are used to detect single bit errors in data storage and communication. The parity of a binary value is 1 if the number of 1s in the value is odd; otherwise it’s 0.

General Tricks

1
2
3
4
5
6
7
8
9
10
11
1. x & (x - 1) => x with its lowest set bit erased
  x:      00101100 
  x - 1:  00101011
  x&(x-1):00101000

2. x & ~(x - 1) => extracts the lowest set bit of x
  x:       00101100 
  ~(x - 1):11010100
  x&~(x-1):00000100

3. Cache results in an array-based lookup table

191. Number of 1 Bits

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

[Solution]
Use a mask from 000...01 to 1000...0 to test if any of the slots is 1

1
2
3
4
5
6
def hammingWeight(self, n):
    cnt = 0
    for i in range(32):
        if (1 << i) & n is not 0:
            cnt += 1
    return cnt

231. Power of Two

Leetcode: https://leetcode.com/problems/power-of-two/

1
2
3
4
5
6
def isPowerOfTwo(self, n):
    if n <= 0:
        return False
    if n & (n - 1) == 0:
        return True
    return False

190. Reverse Bits

1
2
3
4
5
6
def reverseBits(self, n):
    res = 0
    for _ in xrange(32):
        res = (res << 1) + (n & 1)
        n >>= 1
    return res

Find a closest integer with the same weight

Define the weight of a nonnegative integer x to be the number of bits that are set to 1.

[Solution]
Suppose we flip the bit at index k1 and flip the bit at index k2, k1 > k2. Then the absolute value of the difference between the original integer and the new one is 2^k1 - 2^k2. Since we must preserve the weight, we should make k1 as small as possible and k2 as close to k1.

In summary, the correct approach is to swap the two rightmost consecutive bits that differ.

43. Multiply Strings

Leetcode: https://leetcode.com/problems/multiply-strings/

[Solution] Iterate through x, adding 2^k*y to the result if the kth bit of x is 1. 2^k*y can be computed by left-shifting y by k.

1
2
3
4
5
6
7
8
9
10
11
def multiply(self, num1: str, num2: str) -> str:
    a = int(num1)
    b = int(num2)
    res = 0
    k = 0
    while a:
        if a & 1:
            res += b << k
        a >>= 1
        k += 1
    return str(res)

29. Divide Two Integers

[Solution]

  • Starting from k = 32, if 2^k y < x: x = x - 2^k y, res += 2^k
  • O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def divide(self, x: 'int', y: 'int') -> 'int':
    neg = False
    if x * y < 0:
        neg = True
    if x == 0:
        return 0
    x, y = abs(x), abs(y)
    k, res = 32, 0
    while x >= y:
        while y << k > x:
            k -= 1
        res += 1 << k
        x -= y << k
    if neg:
        return -res
    return min(max(-2147483648, res), 2147483647)

50. Pow(x, n)

Leetcode: https://leetcode.com/problems/powx-n/

1
2
3
4
5
6
7
8
9
10
def myPow(self, x: float, n: int) -> float:
    if n < 0:
        return 1.0/self.myPow(x, -n)
    res = 1.0
    while n:
        if n & 1:
            res *= x
        n >>= 1
        x *= x
    return res

393. UTF-8 Validation

Leetcode: https://leetcode.com/problems/utf-8-validation/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def validUtf8(self, data: 'List[int]') -> 'bool':
    mask2 = 1<<7
    cnt = 0
    for num in data:
        temp = num << 1
        if cnt > 4:
            return False
        if num & mask2 == 0: # 0xxxxxx
            if cnt > 1:
                return False
        else:
            if temp & mask2 != 0: # 110xxxxx
                if cnt > 1:
                    return False
                while num & mask2 != 0: # count how many 1s
                    num = num << 1 
                    cnt += 1
            else: # 10xxxxxx
                if cnt < 2:
                    return False
                cnt -= 1
                if cnt == 1:
                    cnt = 0
    return cnt < 2

136. Single Number

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

[Solution]

  • 0 ^ any = any
  • any ^ any = 0
1
2
3
4
5
def singleNumber(self, nums: List[int]) -> int:
    z = 0
    for num in nums:
        z = z ^ num
    return z

67. Add Binary

Leetcode: https://leetcode.com/problems/add-binary/

Solution: The key is the carry. 

1
2
3
4
5
6
7
8
def addBinary(self, A, B):
    res = []
    carry = 0
    while A or B or carry:
        carry += (A or [0]).pop() + (B or [0]).pop()
        res.append(carry & 1)
        carry = carry >> 1
    return res[::-1]

1073. Adding Two Negabinary Numbers

Leetcode: https://leetcode.com/problems/adding-two-negabinary-numbers/

Solution:
The carry can have three status: -1, 0, and 1. 

1
2
3
4
5
6
7
8
9
10
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
    carry = 0
    res = []
    while arr1 or arr2 or carry:
        carry += (arr1 or [0]).pop() + (arr2 or [0]).pop()
        res.append(carry & 1)
        carry = -(carry >> 1)
    while res and res[-1] == 0:
        res.pop()
    return res[::-1] or [0]

1017. Convert to Base -2

Leetcode: https://leetcode.com/problems/convert-to-base-2/

Solution: Convert to base 2 first, and then add -
https://en.wikipedia.org/wiki/Negative_base#Addition

1
2
3
4
5
6
7
8
9
10
11
12
13
def base2(self, N):
        res = ""
        while N:
            res = str(N & 1) + res
            N = N >> 1
        return res
    
def baseNeg2(self, N: int) -> str:
    res = ""
    while N:
        res = str(N & 1) + res
        N = - (N >> 1)
    return res or "0"

393. UTF-8 Validation

Leetcode: https://leetcode.com/problems/utf-8-validation/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def validUtf8(self, data):
    """
    :type data: List[int]
    :rtype: bool
    """
    def bit(d):
        res = ["0"] * 8
        i = 0
        while d:
            res[i] = str(d & 1)
            i += 1
            d >>= 1
            if i == 8:
                break
        return "".join(reversed(res))
    
    if not data:
        return True
    
    mask = (1 << 9) - 1
    first_two = (1 << 7) + (1 << 6)
    left = 0
    for dta in data:
        d = dta & mask
        if left:
            if left > 3:
                return False
            if (d & first_two) == (1 << 7):
                left -= 1
            else:
                return False
        elif d & (1 << 7):
            # count leading 1s
            i = 7
            msk = 1 << i
            while d & msk:
                i -= 1
                if i == 0:
                    left += 1
                    break
                msk = 1 << i
                left += 1
            if left > 1:
                left -= 1
        else:
            if d & 1 << 7:
                return False
    return left == 0