Checking for a pattern of a number in C-CodePudding

I'm still new in C and I have to create a method that returns 0 or 1 if a number contains the binary pattern of the number decided as the pattern. For example, check_pattern(10, 5) returns 1 since 1010 contains the pattern 101.

The issue I'm having is when the pattern only contains one bit at 1, situations like 100 or 1000, where it disregards the least significant bits, and assumes the pattern's value is 1 instead of 4 or 8.

Here is the code I've created:

int check_pattern(int value, int pattern) {
    while ((pattern & 1) == 0)
        pattern >>= 1;
    int pattern_x = pattern, mask = 0;
    while (pattern > 0) {
        mask |= pattern;
        pattern >>= 1;
    }
    while (value >= pattern_x) {
        if ((value & mask) == pattern_x)
            return 1;
        value >>= 1;
    }
    return 0;
}

The code works when the least significant bit isn't 0 or when there are multiple bits of value 1.

int main() {
    size_t arr_size = 4;
    int values[4] = {10, 11, 12, 13}, patterns[4] = {5, 9, 6, 7};
    char *ans;
    for (int i = 0; i < arr_size; i  )
        printf("%d: %d contains pattern %d? %s\n", i 1, values[i], patterns[i], 
                     ans = check_pattern(values[i], patterns[i])==1? "True":"False");
    return 0;
}

The above code produces these results, which are correct:

1: 10 contains pattern 5? True
2: 11 contains pattern 9? False
3: 12 contains pattern 6? True
4: 13 contains pattern 7? False

But changing the patterns to these values patterns[4] = {4, 8, 4, 2}, the results are all wrong:

1: 10 contains pattern 4? True
2: 11 contains pattern 8? True
3: 12 contains pattern 4? True
4: 13 contains pattern 2? True

They should all be false, but since only the most significant bit is of value 1 they end up all true. I think the comparison in my code is only being made with the value 1 and not 100, not sure why.

I know I did something wrong, most likely related to my thought process, but I can't identify what it is.

Thank you very much for the help, I'll also listen to advice on how to improve the code overall!

CodePudding user response：

How I understand your question:

You want to take a pattern of 1's and 0's which starts with a 1, store it in int pattern and look after this pattern in int value

That is possible with this code:

#include "stdio.h"
#include "stdbool.h"
#include "stdlib.h"

bool check_pattern( int value, int pattern )
{
  if( pattern == 0 )
  {
    printf( "int pattern is 0: pattern not defined\n");
    exit(1);
  }

  int mask = 0;
  int pattern_x = pattern;
  while( pattern_x != 0 )
  {
    mask |= pattern_x;

    pattern_x >>=1;
  }

  while( value != 0 )
  {
    if( (value & mask ) == pattern )
    {
      return true;
    }
    value >>= 1;
  }

  return false;
}

note that negative values of int value and int pattern are in the two's complement representation

CodePudding user response：

If I understand the problem correctly and if I'm not mistaken , maybe this will work for you :

int check_pattern(int val , int pattern){
    int counter = pattern ; 
    int mask = 0 ; 
    mask = ~mask ; 
    while(counter){
        counter >>= 1 ; 
        mask <<= 1 ; 
    }
    mask = ~mask ; 
    do
         if((val & mask) == pattern)
         return 1 ; 
    while (val >>= 1) ; 
    return 0 ; 
}

This creates a variable initialized to 0xFFFFFFFF.

int mask = 0 ; 
mask = ~mask ;

This will count how many bits you have in the pattern variable before the MSB , in a mask ... your mask is gonna be in the form 0xFFF....000 :

while(counter){
    counter >>= 1 ; 
    mask <<= 1 ; 
}

Invert the mask so we have it in the form 0x000...FFF

mask = ~mask ;

Now , we shift our value to the right , & it with mask and checking if it's equal to the pattern.