C - Need to compare `n` lowest bits of an int for

Question

C - Need to compare n lowest bits of an int for equality.

I.e. n = 4;

xxxx1001 == xxxx1001 (x is don't care)

I.e. n = 2; xxxxxx01 == xxxxxx01

Can't think of a nice way to do it without using masks, =).

Answer 1

I think what need to do is xor the values and then use a mask. For example,

(a ^ b) & (( 1<<n ) - 1)

Answer 2

If you really don't want to use masks (not that there is anything wrong with that!), then you could use a shift-left operator:

if( a << m == b << m )
{
}

where m is the total number of bits less the number you are interested in. That is, in the example in the question, m is 4 (ie, 8 - 4).

Edit: to be clear - I have assumed the question indicated an 8 bit integer given the format used (eg, xxxx1001), but the solution is general in that it caters for any sized integer. To determine the number of bits in the integer, use 8*sizeof(type), where type may be int, short, long, etc.

Answer 3

I will suppose the 4 low bits are equals
First use y=(a^b) to obtain this bit pattern (x means unknown)

xxxx0000

Then reverse the bit pattern with y=~y

xxxx1111

Then detect the first 0 with y^=(y+1)

xxx11111

Then shift n times to the right y>>=n

0000xxx1

If it's non nul then the lowest n bits were equal So my solution would be

int are_lowest_n_bits_of_a_and_b_equals(int n,int a, int b)
/* return 0 if not equal, or non zero if equal */
{
   int y=~(a^b);
   return (y^(y+1))>>n;
}

It seems to work even for n=number_of_bits(int) thanks to sign bit propagation in signed arithmetic right shift, but if ever it's UB, we can simply test for (a==b) in such edge case.

Answer 4

Create the mask from the number of bits:

int mask = (1 << bits) - 1;

Then you use that to compare the values:

if ((a & mask) == (b & mask))

Answer 5

What's wrong with masks?

(a & 0x1111) == (b & 0x1111)

Answer 6

Try this:

int i;
int theSame = 1;
for (i = 0; i < n; i++)
{
    if !(a >> i & 1) || !(b >> i & 1)
    {
        theSame = 0;
        break;
    }
}