Bit manipulation

Posted on Edited on In , Views:

[Leetcode 136] Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

1
2
Input: nums = [2,2,1]
Output: 1

Example 2:

1
2
Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

1
2
Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

Solution:

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
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # hint: xor the same number results in 0
        #res = nums[0]
        #for i in range(1,len(nums)):
        #    res ^= nums[i]
        #return res

        return reduce(lambda res, num: res ^ num, nums)

        

    def singleNumber1(self, nums: List[int]) -> int:
        set1 = set()

        for num in nums:
            if num in set1:
                set1.remove(num)
            else:
                set1.add(num)

        return list(set1)[0]
        
    def singleNumber2(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums),2):
            if nums[i] != nums[i-1]:
                return nums[i-1]
        return nums[len(nums) - 1]

[Leetcode 190] Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Example 1:

1
2
3
Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

1
2
3
Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints:

  • The input must be a binary string of length 32

Solution:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            lastBit = n & 1
            n >>= 1
            res <<= 1
            res |= lastBit
            
        return res

[Leetcode 338] Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Example 1:

1
2
3
4
5
6
7
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

1
2
3
4
5
6
7
8
9
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

  • 0 <= n <= 105

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
    Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        for i in range(n+1):
            num = i
            if num == 0:
                res.append(0)
                continue
            
            count = 0
            while num:
              count += num & 1
              num >>= 1
            
            res.append(count)

        return res

[Leetcode 1318] Minimum Flips to Make a OR b Equal to c

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

1
2
3
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

1
2
Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

1
2
Input: a = 1, b = 2, c = 3
Output: 0

Constraints:

  • 1 <= a <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9

Solution:

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
class Solution:
    # e.g.
    # a = 8 (1000), c = 3 (0011), c = 5 (0101)
    def minFlips(self, a: int, b: int, c: int) -> int:
        res = 0
        while a or b or c:
            lastBit = c & 1 

            if lastBit:
                # flip a or b to have bit 1
                if not (a & 1 or b & 1):
                    res += 1
                   
            else:
                # flip a to have bit 0
                if a & 1:
                    res += 1

                # flip b to have bit 0
                if b & 1:
                    res += 1

            a >>= 1
            b >>= 1
            c >>= 1

        return res