C语言练习：实现无符号整数中位模式查找函数bitpat_search

Alright, let's work through this bitpat_search() exercise from Kochan's Programming in C—it's a classic bitwise problem that really helps cement how bits work in C. Here's a step-by-step breakdown and implementation:

First, let's clarify exactly what the function needs to do (aligning with the standard exercise from the book):

• The function bitpat_search(source, pattern, n) takes an unsigned integer source, an unsigned integer pattern, and an integer n.
• We need to search source from the highest bit to the lowest for the rightmost n bits of pattern.
• If found, return the starting bit index (0-based, where the highest bit of source is at index sizeof(unsigned int)*8 - 1). If no match is found, return -1.

Before diving into code, let's outline the core logic and edge cases to handle:

• Invalid n values: If n is 0 or larger than the number of bits in unsigned int, return -1 immediately—these are invalid inputs.
• Isolate the target pattern: We only care about the rightmost n bits of pattern, so we'll use a bitmask to zero out any higher bits in pattern.
• Sliding window search: We'll slide an n-bit window across source starting from the highest bit. For each position, extract the n bits from source and compare them to our isolated pattern.

Here's a complete, portable implementation:

#include <stdio.h>
#include <stdlib.h>

int bitpat_search(unsigned int source, unsigned int pattern, int n) {
    const int UINT_BITS = sizeof(unsigned int) * 8;
    
    // Handle invalid n values
    if (n <= 0 || n > UINT_BITS) {
        return -1;
    }
    
    // Special case: n equals the full width of unsigned int
    if (n == UINT_BITS) {
        return (source == pattern) ? 0 : -1;
    }
    
    // Create a mask to isolate n bits, and apply it to pattern
    unsigned int pattern_mask = ~(~0U << n);
    unsigned int target_pattern = pattern & pattern_mask;
    
    // Slide the window from the highest possible position down to 0
    for (int shift = UINT_BITS - n; shift >= 0; shift--) {
        // Extract the n bits from source at current window position
        unsigned int current_bits = (source >> shift) & pattern_mask;
        
        // Check if we have a match
        if (current_bits == target_pattern) {
            // Return the starting index of the match (0-based from highest bit)
            return shift;
        }
    }
    
    // No match found
    return -1;
}

// Example test driver
int main() {
    // Test case 1: Match in highest 3 bits
    unsigned int source1 = 0b10110011; // 179 in decimal
    unsigned int pattern1 = 0b101;     // 5 in decimal
    int result1 = bitpat_search(source1, pattern1, 3);
    printf("Test 1 result: %d (expected 5)\n", result1);
    
    // Test case 2: Match in middle bits
    unsigned int source2 = 0b11001010; // 202 in decimal
    unsigned int pattern2 = 0b010;     // 2 in decimal
    int result2 = bitpat_search(source2, pattern2, 3);
    printf("Test 2 result: %d (expected 3)\n", result2);
    
    // Test case 3: No match
    unsigned int source3 = 0b11100011; // 227 in decimal
    unsigned int pattern3 = 0b001;     // 1 in decimal
    int result3 = bitpat_search(source3, pattern3, 3);
    printf("Test 3 result: %d (expected -1)\n", result3);
    
    return EXIT_SUCCESS;
}

• ~(~0U << n): Creates a mask with the rightmost n bits set to 1. Using ~0U ensures we're working with an unsigned value (avoids sign extension issues on signed integers).
• (source >> shift) & pattern_mask: Shifts source right by shift bits to bring the current window of n bits to the rightmost position, then applies the mask to isolate those bits.
• The loop starts at UINT_BITS - n (the shift needed to view the highest n bits of source) and decrements until shift reaches 0 (viewing the lowest n bits).

• Test 1: source1 is 0b10110011—the highest 3 bits are 0b101, which matches pattern1's rightmost 3 bits. The starting index is 5 (since UINT_BITS=8, 8-3=5).
• Test 2: source2 has 0b010 starting at bit 3 (bits 3-5 are 0b010), so the function returns 3.
• Test 3: There's no 3-bit sequence matching 0b001 in source3, so it returns -1.

内容的提问来源于stack exchange，提问作者Areg Sarvazyan