如何使用AND运算符高效实现十进制转二进制映射元素过滤？

Let's start by breaking down why your recursive approach was inefficient: converting the number to a binary string or array first uses extra memory (space complexity O(log n)), and then you have to iterate through that structure again. Using bitwise operations cuts out that middleman, letting you check each bit directly with minimal overhead.

How Bitwise AND Solves This #

The core trick here is using num & (1 << i) to check if the i-th bit (starting from 0, counting right-to-left from the least significant bit) is set to 1. Here's the breakdown:

• 1 << i shifts the number 1 left by i positions, creating a value with only the i-th bit set to 1 (for example, 1 << 2 equals 4, which is 100 in binary).
• When you run a bitwise AND between num and this shifted value, a non-zero result means the i-th bit in num was 1. A zero result means that bit was 0.

Step-by-Step Implementation #

1. Initialize an empty list to hold your matched mapping entries.
2. Iterate over each bit position i starting from 0. You can stop when (1 << i) exceeds your input number—any bits beyond that will be 0, so there's no need to check them.
3. For each position i:
   • Calculate check_bit = num & (1 << i).
   • If check_bit isn't zero, look up the value for key i in your mapping and add it to the result list.
4. Return the result list.

Example Code (Python) #

def get_matching_mapped_values(num, mapping):
    result = []
    current_bit = 0
    # Loop until we've checked all possible bits in the number
    while (1 << current_bit) <= num:
        # Check if the current bit is set to 1
        if num & (1 << current_bit):
            # Add the mapping entry if the key exists
            if current_bit in mapping:
                result.append((current_bit, mapping[current_bit]))
        current_bit += 1
    return result

# Test with your input (note: correction to expected output based on standard bit numbering)
num = 6  # Binary: 110 → bits 1 and 2 are set to 1
mapping = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f'}
print(get_matching_mapped_values(num, mapping))  # Output: [(1, 'b'), (2, 'c')]

Wait, you mentioned expecting {0,a} and {1,b} for num=6. That suggests you might be counting bits left-to-right (starting from the most significant bit) instead of the standard right-to-left. If that's the case, we can adjust the approach while still using bitwise AND:

def get_left_to_right_matches(num, mapping):
    if num == 0:
        return [(0, mapping[0])] if 0 in mapping else []
    # Get total number of bits in the binary representation
    total_bits = num.bit_length()
    result = []
    for i in range(total_bits):
        # Convert left-to-right position to standard right-to-left index
        right_pos = total_bits - 1 - i
        if num & (1 << right_pos):
            if i in mapping:
                result.append((i, mapping[i]))
    return result

# Test to match your example's expected output
print(get_left_to_right_matches(6, mapping))  # Output: [(0, 'a'), (1, 'b')]

Why This Is More Efficient #

• Time Complexity: O(log n), since we only iterate through the number of bits in num (which is log₂(n) + 1). This matches your recursive approach but has lower constant factors because we skip binary string/array conversion.
• Space Complexity: O(k), where k is the number of matching elements—we only store the result, no extra space for binary conversion is needed, which is a big improvement over the recursive method.

内容的提问来源于stack exchange，提问作者Sundar Ganapathy