Bit Manipulation

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

これもほぼ出されることないらしい分野だけど一応。

144. Single Number

Problem

You are given a non-empty array of integers nums. Every integer appears twice except for one.

Return the integer that appears only once.

You must implement a solution with O(n)O(n) runtime complexity and use only O(1)O(1) extra space.

Example 1:

Input: nums = [3,2,3]

Output: 2

Copy

Example 2:

Input: nums = [7,6,6,7,8]

Output: 8

Copy

Constraints:

• 1 <= nums.length <= 10000
• -10000 <= nums[i] <= 10000

Solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        
        return res

145. Number of 1 Bits

Problem

You are given an unsigned integer n. Return the number of 1 bits in its binary representation.

You may assume n is a non-negative integer which fits within 32-bits.

Example 1:

Input: n = 00000000000000000000000000010111

Output: 4

Copy

Example 2:

Input: n = 01111111111111111111111111111101

Output: 30

Copy

Solution

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n = n >> 1
        return count

146. Counting Bits

Problem

Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].

Return an array output where output[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 4

Output: [0,1,1,2,1]

Copy

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100

Constraints:

• 0 <= n <= 1000

Solution

class Solution:
    def countBits(self, n: int) -> List[int]:
        offset = 1
        i = 1
        dp = [0] * (n + 1)
        while i <= n:
            if i == offset * 2:
                offset *= 2
            dp[i] = dp[i - offset] + 1
            i += 1

        return dp

147. Reverse Bits

Problem

Given a 32-bit unsigned integer n, reverse the bits of the binary representation of n and return the result.

Example 1:

Input: n = 00000000000000000000000000010101

Output:    2818572288 (10101000000000000000000000000000)

Copy

Explanation: Reversing 00000000000000000000000000010101, which represents the unsigned integer 21, gives us 10101000000000000000000000000000 which represents the unsigned integer 2818572288.

Solution

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        
        for i in range(31, -1, -1):
            res += (n & 1) << i
            n = n >> 1
        
        return res

148. Missing Number

Problem

Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.

Follow-up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:

Input: nums = [1,2,3]

Output: 0

Copy

Explanation: Since there are 3 numbers, the range is [0,3]. The missing number is 0 since it does not appear in nums.

Example 2:

Input: nums = [0,2]

Output: 1

Copy

Constraints:

• 1 <= nums.length <= 1000

Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        total = sum(nums)
        index_total = 0
        for i in range(len(nums)+1):
            index_total += i
        return index_total - total

149. Sum of Two Integers

Problem

Given two integers a and b, return the sum of the two integers without using the + and - operators.

Example 1:

Input: a = 1, b = 1

Output: 2

Copy

Example 2:

Input: a = 4, b = 7

Output: 11

Copy

Constraints:

• -1000 <= a, b <= 1000

Solution

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

150. Reverse Integer

Problem

You are given a signed 32-bit integer x.

Return x after reversing each of its digits. After reversing, if x goes outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0 instead.

Solve the problem without using integers that are outside the signed 32-bit integer range.

Example 1:

Input: x = 1234

Output: 4321

Copy

Example 2:

Input: x = -1234

Output: -4321

Copy

Example 3:

Input: x = 1234236467

Output: 0

Copy

Constraints:

• -2^31 <= x <= 2^31 - 1

Solution

class Solution:
    def reverse(self, x: int) -> int:
        res = 0
        MIN = -2**31
        MAX = 2**31 - 1

        while x != 0:
            digit = int(math.fmod(x, 10))
            x = int(x / 10)

            if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):
                return 0
            
            if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
                return 0

            res = res * 10 + digit
        
        return res