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, =).
views:
521answers:
6
A:
Hi,
you could use the modulo operator. For example n = 4 and you have to ints x and y:
if((x%16) == (y%16)){ ....
Hope this helps you.
Nick
Nick
2009-09-13 11:40:55
8 is for n=3, not n=4.
Peter Mortensen
2009-09-13 11:56:00
whoops, thanks ;)
Nick
2009-09-13 12:13:26
You could use the modulo operator, but that would make people think you weren't really a C programmer. The bit masking solution is a much more idiomatic one in C. That fact that modulo is probably massively slower is a secondary concern.
Andrew Bainbridge
2009-09-13 15:22:16
And any compiler worth its salt translates modulo of a power of two to the appropriate mask. With the constraint that the number of bits desired is variable, this doesn't work so well, and the questioner needs to be directed to shift or mask explicitly.
Novelocrat
2009-09-13 21:02:51
+18
A:
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))
Guffa
2009-09-13 11:40:56
@leiz: your solution is very neat, but readability has its own value...
Roee Adler
2009-09-13 11:46:39
@leiz: That might be faster, but todays CPUs are not that linear, so you won't know without actually profiling it. Either way it's just micro-optimizing, and I would go with what's more readable.
Guffa
2009-09-13 11:50:19
And as pointed out on leiz's answer, GCC transforms this into leiz's answer anyway. Stick with readable.
GMan
2009-09-13 20:37:44
@juanduke - nothing in the question explicitly states that this has to be a general solution for an arbitrary number of bits.
Peter M
2009-09-13 11:59:35
The hexadecimal constants you show are not the lowest order bits. That's every 4th bit set in the lowest 16.
Novelocrat
2009-09-13 21:01:05
+4
A:
I think what need to do is xor the values and then use a mask. For example,
(a ^ b) & (( 1<<n ) - 1)
leiz
2009-09-13 11:41:16
Peter Mortensen
2009-09-13 12:04:02
Don't like this; it's far from clear what it does. Code is better when you can look at it and immediately perceive its function.
Blank Xavier
2009-09-13 12:17:06
GCC 4 will make that optimization for you anyway, when given Guffa's solution.
Andrew Bainbridge
2009-09-13 15:30:50
+7
A:
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.
Daniel Paull
2009-09-13 11:46:04
A problem with this approach is that the number of bits in an int is not specified in the language. It may be predictable for a certain compiler on a certain system, but the code is not portable.
Guffa
2009-09-13 12:53:04
@Peter: the questions shows the integers in the format of "xxxx1001", so I assumed an 8 bit integer. I defined m as "m is the total number of bits less the number you are interested in", so it would work for other sized integers too.
Daniel Paull
2009-09-14 00:00:35
Yeah, definitely takes more time than Guffa's answer, but since the asker seems to have some difficulty understanding bitmasks, I thought it would be clearer because this breaks it down in to little chunks where you just worry about one bit at a time.
Gordon Worley
2009-09-14 13:31:54