Leetcode 位计算

3095. 或值至少 K 的最短子数组 I

3097. Shortest Subarray With OR at Least K II

class Solution:def minimumSubarrayLength(self, nums: List[int], k: int) -> int:n = len(nums)bits = [0] * 30res = infdef calc(bits):return sum(1 << i for i in range(30) if bits[i] > 0)left = 0for right in range(n):for i in range(30):bits[i] += (nums[right] >> i) & 1while left <= right and calc(bits) >= k:res = min(res, right - left + 1)for i in range(30):bits[i] -= (nums[left] >> i) & 1left += 1return -1 if res == inf else res

2595. Number of Even and Odd Bits

class Solution:def evenOddBit(self, n: int) -> List[int]:res = [0, 0]i = 0while n:res[i] += n & 1n >>= 1i = i ^ 1return res

• n >>= 1: Performs a right bitwise shift on n
• i = i ^ 1: This cleverly toggles the index i between 0 and 1. The ^ operator is the bitwise XOR. Since i is either 0 or 1:
  If i is 0, 0 ^ 1 is 1.
  If i is 1, 1 ^ 1 is 0.

Binary representation of 8: 1000
Iterations:
Iteration 1:
n = 8 (1000)
n & 1 = 1000 & 0001 = 0000 = 0
res[0] = 0 + 0 = 0
n >>= 1 (n becomes 4, which is 0100)
i = 0 ^ 1 = 1Iteration 2:
n = 4 (0100)
n & 1 = 0100 & 0001 = 0000 = 0
res[1] = 0 + 0 = 0
n >>= 1 (n becomes 2, which is 0010)
i = 1 ^ 1 = 0Iteration 3:
n = 2 (0010)
n & 1 = 0010 & 0001 = 0000 = 0
res[0] = 0 + 0 = 0
n >>= 1 (n becomes 1, which is 0001)
i = 0 ^ 1 = 1Iteration 4:
n = 1 (0001)
n & 1 = 0001 & 0001 = 0001 = 1
res[1] = 0 + 1 = 1
n >>= 1 (n becomes 0, which is 0000)
i = 1 ^ 1 = 0
Loop terminates because n is now 0.Return value:
res = [0, 1]