Thread: bit fields in C

I am working on a problem to write a function called bit_search(). It is supposed to take in three arguments, which I called
number
pattern
numberBits
The function should start from number's high order bit and work its way down the bits to see what bit is the start of the first match to what is in the low order bits of pattern. The number of bits to match is determined by numberBits.

My strategy in the following code ( I am open to better suggestions by the way ) is to rotate number's bit left, set the irrelevant bits of number to zero, and then see if number and pattern are equal. If so, I would return the value of a counter as the bit number which the first match occurred. My problem is I don't think I am setting the high order bits to zero correctly. I mean I am checking the numbers, and rotating seems to work. But I think I want to set 32 - 3 = 29 of high order bits to zero, so I start with 70fa0 in bits and I do

Code:

bits &= ~(0xfffffff8);

and it seems to work. But I may be testing for a match incorrectly since the pattern 5 emerges, but the == test does not match. Here is my code:

Code:

#include <stdio.h>
// Function to rotate an unsigned int left or right
unsigned int rotate (unsigned int value, int n)
{
  unsigned int result, bits;
//scale down the shift count to a defined range
  if ( n > 0 )
    n = n % 32;
  else
    n = -(-n % 32 );
  if  ( n == 0 )
    result = value;
  else if ( n > 0 ) { // left rotate
    bits = value >>  ( 32 -n );
    //printf("\nIf n is a positive value, we rotate left\n");
    //printf("Here is what is in bits %x\t\n",bits);
    //printf("Here is what is in value %x\t\n", value);
    //printf("Here is what is in n %d\t\n", n);
    result = value << n | bits;
    //printf ("Here is what result looks like: %x\t\n", result);
  }
  else { // right rotate
   n = -n;
    bits = value << ( 32 - n);
    result = value >> n | bits;
  }
  return result;
}
unsigned int bitpat_search ( unsigned int number, unsigned int pattern, int numberBits )
{
unsigned int rotatedValue, bits, index = 0;
printf("\nHere is what is in bits %x", bits);
int i;
printf("\nHere is what is in number before it was rotated:%x\t", number);
rotatedValue = rotate (number, numberBits);
bits = rotatedValue;
printf ("\nHere is what is in number %x\t after it was rotated by %x bits", rotatedValue, numberBits);
  for ( i=0; i<32; i++)
    {
      bits &= ~(0xfffffff8);
      printf ("\nHere is what is in number after high order bits are set to zero %x\t", bits);
      if (bits == pattern)
       index = 32 - i;
      rotatedValue = rotate (rotatedValue, numberBits);
      bits = rotatedValue;
printf("\nHere is what is in number: %x\t and rotatedValue after rotation: %x\t ", number, rotatedValue);
    }
//printf ("Here is what i went up to :%d", i);
return index;
}
/*******************************************Main Function*****************************************/
int main (void)
{
  unsigned int w1 = 0xabcdef00u, w2 = 0xffff1122u;
  unsigned int w3 = 0xe1f4, w4 = 0x5;
  printf ("Here is what w4 looks like at the start %x", w4);
  printf ("\nHere is what w3 looks like at the start %x", w3);
  int result;
  unsigned int rot3ff (unsigned int value, int n);
  unsigned int bitpat_search ( unsigned int number, unsigned int pattern, int numberBits );
  result = bitpat_search (w3, w4, 3);
  //printf ("%x\n", rotate (w1, 8));
  //printf ("%x\n", rotate (w1, -16));
  //printf ("%x\n", rotate (w2, 4));
  //printf ("%x\n", rotate (w2, -2));
  //printf ("%x\n", rotate (w1, 0));
  //printf ("%x\n", rotate (w1, 44));
  printf ("Here is the index :     %d\n", result);
  return 0;
}

Just an update; I figured it out. It seems to work. I just had not printed out the match.

You don't need the rotate stuff.

Code:

#include <stdio.h>

int bitpat_search(unsigned num, unsigned pat, unsigned n) {
    if (n == 0 || n > 32)
        return -1;

    unsigned mask = (1 << n) - 1;

    int i = 32 - n;
    for ( ; i >= 0; i--)
        if ((num >> i & mask) == pat)
            return i + n - 1;

    return -1;
}

// bit: 222211111111110000000000
//      321098765432109876543210
// num: 111000011111010000000000   0xe1f400
// pat:            101             0x5
// match at bit 12
int main(void) {
    unsigned num = 0xe1f400, pat = 0x5;
    int result = bitpat_search(num, pat, 3);
    printf("%d\n", result);
    return 0;
}

A little fancier:

Code:

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

#define NBITS (sizeof(unsigned) * CHAR_BIT)

int bitpat_search(unsigned num, unsigned pat, unsigned n) {
    if (n == 0 || n > NBITS)
        return -1;

    unsigned mask = (1 << n) - 1;

    int i = NBITS - n;
    for ( ; i >= 0; i--)
        if ((num >> i & mask) == pat)
            return i + n - 1;

    return -1;
}

void print_bits(unsigned val, int n) {
    unsigned mask = 1u << (n - 1);
    for ( ; mask; mask >>= 1)
        putchar(val & mask ? '1' : '0');
    putchar('\n');
}

int main(int argc, char **argv) {
    if (argc != 4) {
        fprintf(stderr, "Usage: bitpat num(hex) pat(hex) n(dec)\n");
        exit(EXIT_FAILURE);
    }

    unsigned num = strtol(argv[1], NULL, 16);
    unsigned pat = strtol(argv[2], NULL, 16);
    unsigned n   = strtol(argv[3], NULL, 10);

    int pos = bitpat_search(num, pat, n);
    if (pos == -1)
        printf("No match\n");
    else {
        printf("Match at %d\n", pos);

        print_bits(num, NBITS);
        for (int i = 0; i < (NBITS-1) - pos; i++)
            putchar(' ');
        print_bits(pat, n);
    }

    return 0;
}